shunfurh 于 2017.09.07 11:54 提问

A Flea on a Chessboard

An infinite chessboard is obtained by extending a finite chessboard to the right and up infinitely. Each square of the chessboard is either black or white with the side of S milimeters, 0 < S <= 1000. The leftmost bottom square of the chessboard is black. A flea is positioned on the chessboard at the point (x, y) (given in milimeters) and makes jumps by jumping dx milimeters to the right and dy milimeters up, 0 < dx, dy, that is, a flea at position (x, y) after one jump lands at position (x+dx, y+dy).

Given the starting position of the flea on the board your task is to find out after how many jumps the flea will reach a white square. If the flea lands on a boundary between two squares then it does not count as landing on the white square. Note that it is possible that the flea never reaches a white square.

Input

Each test case consists of one line of input containing five non-negative numbers separated by white space and giving integers S, x, y, dx, and dy. An input line containing five zeroes follows the last test case.

Output

For test case print one line of output in the format shown in the sample.

Sample Input

10 2 3 3 2
100 49 73 214 38
25 0 0 5 25
407 1270 1323 1 1
18 72 6 18 6
407 1270 1170 100 114
0 0 0 0 0

Sample Output

After 3 jumps the flea lands at (11, 9).
After 1 jumps the flea lands at (263, 111).
The flea cannot escape from black squares.
After 306 jumps the flea lands at (1576, 1629).
The flea cannot escape from black squares.
After 0 jumps the flea lands at (1270, 1170).

1个回答

caozhy      2017.09.22 08:34

POJ1728 A flea on a chessboard

POJ 1728 A flea on a chessboard
A flea on a chessboardTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 1509 Accepted: 491DescriptionAn infinite chessboard is obtained by extending a finit
UVA 10620 - A Flea on a Chessboard（鸽笼原理）
UVA 10620 - A Flea on a Chessboard 题目链接 题意：给定一个跳蚤位置和移动方向，现在在一个国际象棋棋盘上，左下角为黑格，一个格子为s*s，判断能否移动到白格子，问要移动多少次才能到白格，边界不算白格。 思路：利用鸽笼原理落在黑格子和边界上的一共有（s + 1)^2个点，也就是说，如果形成循环，周期肯定在这之内，所以可以不断去模拟跳格子，直到踩到白
UVa10620 - A Flea on a Chessboard(模拟问题)
An infinite chessboard is obtained by extending a finite chessboard to the right and up infinitely. Each square of the chessboard is either black or white with the side of S milimiters, 0 S x, y)
hdu 1564 Play a game （博弈 奇偶规律）
Play a gameTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2322 Accepted Submission(s): 1865Problem Description New Year is Coming! ailyan
Sicily 2683. Alice and Bob
ConstraintsTime Limit: 1 secs, Memory Limit: 256 MBDescriptionBob is very famous because he likes to play games. Today he puts a chessboard in the desktop, and plays a game with Alice. The size of the
HDU 1564 Play a game（巴什博弈）

Codeforces 961C Chessboard（将碎了的、染色乱了的棋盘碎片拼一起）

【CodeForces】445A - DZY Loves Chessboard（dfs）

1016: Roliygu and Yilan