俺の許嫁と幼なじみが修羅場すぎる | paizaオンラインハッカソン（POH）

Test case 1	Passed	Run time: 0.01 sec Step ： 1 step (Average step ： 316.32 step )
Test case 2	Passed	Run time: 0.01 sec Step ： 6 step (Average step ： 428.05 step )
Test case 3	Passed	Run time: 0.02 sec Step ： 137 step (Average step ： 1755.13 step )
Test case 4	Passed	Run time: 0.10 sec Step ： 186 step (Average step ： 2145.87 step )
Test case 5	Passed	Run time: 0.04 sec Step ： 126 step (Average step ： 1582.92 step )

* Test cases are run from 1 in order. If there is a test case that does not pass, the subsequent test case does not run (knockout system)

* The number of steps is the number it took to complete the 15 puzzle.

Step average ： 91.2 step It was a piece of cake!

100pt / in 100 pt scale, Language: C++

Rena "Indeed, Tatsuya!"
Minami "Good job! Tatsu"

Your skill level is over paiza rank S equivalent.

Look at the jobs board of rank S

You can choose a girl you like with your code!?

If it were you, who would you choose? Childhood friend, Minami or fiance, Rena!? Then, by selecting outcomes, what is the changing fate of Tatsuya…!?
Write a smart code with your favorite language(Java,C,C++C#,PHP,Ruby,Python,Perl,JavaScript). The submitted code will be tested by multiple test cases. You will get a score based on the number of successful answer, and running time.

We haveseveral problemsfor the story. Let's complete the all problem!