AE2B - (K,N)-Knight
Bytean chess is one of the most peculiar variants of chess in the world. Playing each match is a major difficulty, because the game is played on an infinite chessboard. The basic ability learnt by young enthusiasts of Bytean chess is considering all possible situations on a chessboard after millions of moves. To perform this, they need to know whether a given chess piece can get from one given square to another one.
The most powerful chess piece in Bytean chess is a (K, N)-knight. Its moves resemble the moves of a knight in traditional chess. Each of its moves consists of: either moving K squares vertically and afterwards N squares horizontally, or moving N squares vertically and afterwards K squares horizontally. The knight from traditional chess can therefore be thought of as (2, 1)-knight or (1, 2)-knight.
The task is to verify, for two given squares of the chessboard, if a (K, N)-knight can get from the first square to the second one (the number of necessary moves is not important).
Input
The first line of the standard input contains one integer T (1 ≤ T ≤ 20000) denoting the number of test cases. Each of the following T lines contains a description of a single test case in the form of six integers K, N, x1, y1, x2, y2 (0 ≤ K, N ≤ 109, K + N > 0, -109 ≤ x1, y1, x2, y2 ≤ 109) separated by single spaces. K and N describe the possible moves of the knight. The knight starts its movement in square (x1, y1). We would like to check if it can get to square (x2, y2).
Output
For each test case exactly one line should be written to the standard output. It should contain a word TAK (meaning YES) or NIE (meaning NO) depending on whether a (K, N)-knight starting from square (x1, y1) can get to square (x2, y2).
Example
For the input data:
3 2 1 0 0 3 3 1 1 1 1 1 2 1 0 2 3 4 6
the correct result is:
TAK NIE TAK
Task author: Jakub Onufry Wojtaszczyk.
hide comments
Vladimir Kirichenkoff:
2021-07-29 17:04:53
If you're getting WA, please, ensure that first 2 cases are solved correctly. |
|
Vladimir Kirichenkoff:
2021-07-29 17:00:23
To solve this task, perform the next steps:
|
|
vincecao:
2017-12-18 12:07:23
WA for several times and don't know why :(
|
|
krist7599555:
2016-12-20 13:16:29
so sadly for case K==0 && N==0 |
|
Bhavik:
2014-02-16 12:34:44
knight tour problem...:) |
|
ওয়াসী (Wasi):
2013-07-16 08:16:51
Is there any chance of getting WA instead of TLE while the code actually gets TLE?
|
|
unXled:
2012-06-27 05:04:10
take care of dividing by zero..costed me lot of SIGFPE.... |
|
nitish_goyal28:
2011-07-24 07:35:48
more test cases please... |
|
Ankit Gupta:
2011-06-23 13:31:21
my submission id is 5282393
|
Added by: | Race with time |
Date: | 2009-05-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Algorithmic Engagements 2009 |