|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||29||14||10||50.000%|
Alice and Bob are travelling in Italy. They are travelling by car and unfortunately they took a wrong turn. Now they are stuck in the city centre of Pisa. (You may know that you need an allowance to drive in the city centre, so they are at risk of getting a fine.) As they were not fully prepared for this, they have a map, but no GPS. The map lists all intersections. At each intersection you can go either left or right (you cannot go straight or take a U-turn, as many streets are one-way).
Of course, they paid attention when entering Pisa and tried to follow on the map. Unfortunately, Alice thinks they are at intersection A, while Bob believes they are now at intersection B. You can imagine this is quite a stressful situation. Instead of figuring out how to get out of Pisa, they want to know who is right first. On the map it is indicated from which intersections you can see the leaning tower of Pisa. So they believe they can conduct an experiment: drive a bit and take the same actions on the map starting from A and B. They can trace the route they drive on the map for both of their starting points. As soon as the tower of Pisa should be visible for one of them but not for the other, they can look out of the window to see who is right. You may assume exactly one of them is right.
Print the minimal number of turns it takes to show either person correct. If no experiment can tell whether Alice or Bob is correct, print “
3 1 2 1 2 1 0 2 0 0 1 0
2 0 1 1 1 1 0 0 0
3 1 2 1 2 0 2 0 1 0 1 1