[The problem appeared in TopCoder SRM 594 (Div-2, Level-1)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12811
Fox Ciel is now in high school. The seats in her classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right).
At the beginning, Ciel can choose any of the seats. Then, at the end of each week Ciel will shift one row to the back and one column to the right, wrapping around whenever necessary. Formally, if her current seat is in row r and column c, then her seat next week will be the one in row ((r+1) modulo n) and column ((c+1) modulo m).
Fox Ciel now wonders whether she can sit in all the seats in the classroom if she follows the above procedure. As we already mentioned, she can start in any of the seats. Also, she can attend the school for as many weeks as she wants to. Return “Possible” if she can sit in all the seats and “Impossible” otherwise.
Parameters: int, int
Method signature: String ableTo(int n, int m)
1. n will be between 2 and 10, inclusive.
2. m will be between 2 and 10, inclusive.
Very simple, if you use a set. While moving to the next cell, we have to check that if she has already visited that cell or not. And repeat the procedure for all possible start points (ableTo_slow function).
Now we can improve it, when starting the next run of checking if we put a condition that only start if the start point is already not part of any previous visited points (ableTo function).