The problem goes like this: You have a book with n ( n<=10^7 ) pages. You can flip exactly X pages to the right and exactly Y pages to the left. If you're initially on page 1, what is the minimum number of moves to go from page 1 to page A? (**100 test cases**)
You can find the problem Here( UVA 11312- Flipping Frustration ).
I will be very thankful if you provide me with a solution.
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
BFS? Just treat it like an usual shortest path problem.
I tried BFS. But since it has 100 test cases, I got TLE.
Use GCD!
Could you please elaborate?
I believe you just treat it as a linear diophantine equation, use the extended euclidian algorithm to get solutions (where both counts are positive), then minimize their sum.
See this:linear diophantine equations for more details
how to use gcd?
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).