Editorialist : Sudheera Y S
Problem Link : ZIO 2014 Problem 2
Prerequisites : cycles , pattern
Problem statement :
A person starts from some city and he travels in cycles of
bus → train → plane → plane → plane → bus → train ( each of them is a journey )
and the table of the routes are given. Find out in which city he will end up after completing n journeys
Idea :
As the cycles of the journeys are fixed , we can find out → starting from any city where he will reach after doing the above fixed cycle ( total 7 journeys )
Let us find out where he is going to end after doing 7 journey from each city
S → source
D → Destination
Each of the source - destination is 7 journeys. Lets define this as 1 trip
1 TRIP = 7 JOURNEYS
If we find out after how many trips , we come back to the same source city , then we can just divide it by those many times and we can finally find the destination
Suppose we start from 0 , complete 1 trip , end at … 7 , start at 7 , complete 1 trip , end at … 8 , start at 8 , complete 1 trip , end at … 11 , start at 11 , complete 1 trip , end at … 9 , start at 9 , complete 1 trip , end at … 3 , start at 3 , complete 1 trip , end at 2 , start at 2 , complete 1 trip , end at… 0
YAY !
We have reached 0 after 7 trips i.e 7*7 = 49 journeys
Now , let us take 9 and do the same thing ,
start from 9 , complete 1 trip , end at … 3 , start at 3 , complete 1 trip , end at … 2 , start at 2 , complete 1 trip , end at … 0 , start at 0 , complete 1 trip , end at … 7 , start at 7 , complete 1 trip , end at … 8 , start at 8 , complete 1 trip , end at 11 , start at 11 , complete 1 trip , end at… 9
We have now also gone through the same route !!
IT DOESN’T MATTER IF WE START AT 0 , 9 , 3 , 2 , 7 , 8 , 11 but we end up following the same route !
So ( 0,7,8,11,9,3,2) is a cycle , no matter in which city we start , we will take exactly 7 trips or 49 journeys to end up in the same city again !
But we havent even visited 1,10,4,5,6
Let us start from 1 :
start from 1 , complete 1 trip , end at … 10 , start at 10 , complete 1 trip , end at … 4 , start at 4 , complete 1 trip , end at … 5 , start at 5 , complete 1 trip , end at … 6 , start at 6 , complete 1 trip and end up at 1
AGAIN !
In 5 trips or 35 journeys we have ended up in the same city
Now let us do for 6 :
start from 6 , complete 1 trip , end at … 1 , start at 1 , complete 1 trip , end at … 10 , start at 10 , complete 1 trip , end at … 4 , start at 4 , complete 1 trip , end at … 5 , start at 5 , complete 1 trip and end up at 6 i.e the starting city
As we had done earlier , we are following the same route doesn’t matter which city we are starting from and we take exactly 5 trips or 35 journeys to end up in the same city
So (1,10,4,5,6) is our another cycle. We will take 5 trips or 35 journeys
Now after done this much , let us do the subtasks and it would be very simple
Subtask A :
Source - 2 , No. Journeys - 103
2 is in the first cycle , so it would take 49 journeys to end up in 2
103 when divides by 49 leaves a remainder of 5
So we have to complete 5 more journeys starting from 2. Let us refer back to our table. 2ND city source city , 5 journeys i.e city after the taking the plane 3 times and we reach 7nth city , therefore the answer is 7
Source - 6 , No. Journeys - 103
6 is in the second cycle , so it would take 35 journeys to end up in 6
103 when divides by 35 leaves a remainder of -2 ( 35*3 = 105 , so we can go back 2 steps FROM 6 )
So we have to go back 2 journeys starting from 1. Let us refer back to our table. We have to search for 6 in the destination and see which is 2 journeys behind it and that would be our answer. We see that in the 5th city , after completing one trip we end up in 6th city , therefore from the 5th city we have to do 7-2 = 5 journeys i.e the city after taking the third plane which is 1 , therefore our answer is 1
Answer : 7 , 1
Subtask B :
Source - 0 , number of journeys 159
We see that 0 is in the first cycle , therefore we will end up in 0th city after 49 journeys . 159 when divided by 49 leaves a remainder of 12. That is starting from 0 , 1 trip and 5 journeys ( 7 + 5)
Starting from 0 , after completing 1 trip we end up in 7 and after completing 5 journeys ( after the third plane ) from 7 , we will end up in 11
Therefore our answer is 11
Source - 10 , number of journeys 159
We see that 10 is in the second cycle , therefore we will end up in 10th city after 35 journeys . 159 when divided by 35 leaves a remainder of 19. That is starting from 10 , 2 trips and 5 journeys ( 14 + 5)
Starting from 10 , after completing 1 trip we end up in 4 and after completing 1 trip from 4 we end up in 5 , and from 5 after completing 5 journeys ( after the third plane ) , we will end up in 1
Therefore our answer is 1
Answer : 11 , 1
Subtask C :
Source - 4 , number of journeys - 207
We see that 4 is in the second cycle , therefore we will end up in 4 city after 35 journeys . 207 when divided by 35 leaves a remainder of -3 ( 35*6 = 210 ).
So we have to go back 3 journeys starting from 4. Let us refer back to our table. We have to search for 4 in the destination and see which is 3 journeys behind it and that would be our answer. We see that in the 10th city , after completing one trip we end up in 4th city , therefore from the 10nt row , from the destination we have to go back 3 journeys i.e the destination after completing the second plane and that is 4 , therefore our answer is 4
Source - 7 , number of journeys - 207
We see that 7 is in the first cycle , therefore we will end up in 7th city after 49 journeys . 207 when divided by 49 leaves a remainder of 11. That is starting from 7 , 1 trip and 4 journeys ( 7 + 4)
Starting from 7 , after completing 1 trip we end up in 8 and after completing 5 journeys ( after the third plane ) from 8 , we will end up in 11
Therefore our answer is 11
Answer : 4 , 11
Hope you understood
