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).