CF1921E.Eat the Chip
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Alice and Bob are playing a game on a checkered board. The board has h rows, numbered from top to bottom, and w columns, numbered from left to right. Both players have a chip each. Initially, Alice's chip is located at the cell with coordinates (xa,ya) (row xa, column ya), and Bob's chip is located at (xb,yb). It is guaranteed that the initial positions of the chips do not coincide. Players take turns making moves, with Alice starting.
On her turn, Alice can move her chip one cell down or one cell down-right or down-left (diagonally). Bob, on the other hand, moves his chip one cell up, up-right, or up-left. It is not allowed to make moves that go beyond the board boundaries.
More formally, if at the beginning of Alice's turn she is in the cell with coordinates (xa,ya), then she can move her chip to one of the cells (xa+1,ya), (xa+1,ya−1), or (xa+1,ya+1). Bob, on his turn, from the cell (xb,yb) can move to (xb−1,yb), (xb−1,yb−1), or (xb−1,yb+1). The new chip coordinates (x′,y′) must satisfy the conditions 1≤x′≤h and 1≤y′≤w.
Example game state. Alice plays with the white chip, Bob with the black one. Arrows indicate possible moves.
A player immediately wins if they place their chip in a cell occupied by the other player's chip. If either player cannot make a move (Alice—if she is in the last row, i.e. xa=h, Bob—if he is in the first row, i.e. xb=1), the game immediately ends in a draw.
What will be the outcome of the game if both opponents play optimally?
爱丽丝和鲍勃正在一个方格棋盘上进行一场游戏。棋盘有 h 行(从上到下编号)和 w 列(从左到右编号)。双方各持有一枚棋子。初始时,爱丽丝的棋子位于坐标为 (xa,ya) 的格子(第 xa 行、第 ya 列),鲍勃的棋子位于 (xb,yb)。保证两枚棋子的初始位置不重合。双方轮流行动,爱丽丝先行。
在爱丽丝的回合中,她可将她的棋子向下移动一格,或向右下对角线移动一格,或向左下对角线移动一格。而鲍勃则可在他的回合中将他的棋子向上移动一格,或向右上对角线移动一格,或向左上对角线移动一格。不允许走出棋盘边界。
更形式化地:若爱丽丝在她回合开始时位于坐标为 (xa,ya) 的格子,则她可将棋子移至以下三格之一:(xa+1,ya)、(xa+1,ya−1) 或 (xa+1,ya+1);而鲍勃在他回合开始时若位于 (xb,yb),则可将棋子移至 (xb−1,yb)、(xb−1,yb−1) 或 (xb−1,yb+1)。新坐标 (x′,y′) 必须满足 1≤x′≤h 且 1≤y′≤w。
游戏状态示例。爱丽丝使用白色棋子,鲍勃使用黑色棋子。箭头表示可能的走法。
若某位玩家将其棋子移动至对方棋子所在的格子,则该玩家立即获胜。若任一玩家无法移动(爱丽丝无法移动当且仅当她位于最后一行,即 xa=h;鲍勃无法移动当且仅当他位于第一行,即 xb=1),则游戏立即以平局结束。
若双方均采取最优策略,游戏结果将如何?
输入格式
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. This is followed by the description of the test cases.
Each test case consists of a single line containing six integers h, w, xa, ya, xb, yb (1≤xa,xb≤h≤106, 1≤ya,yb≤w≤109) — the dimensions of the board and the initial positions of Alice's and Bob's chips. It is guaranteed that either xa=xb or ya=yb.
It is guaranteed that the sum of h over all test cases does not exceed 106.
每个测试包含多个测试用例。第一行包含一个整数 t(1≤t≤104),表示测试用例的数量。随后是各测试用例的描述。
每个测试用例由一行组成,包含六个整数 h、w、xa、ya、xb、yb(1≤xa,xb≤h≤106,1≤ya,yb≤w≤109),分别表示棋盘的尺寸以及爱丽丝和鲍勃的棋子的初始位置。保证满足 xa=xb 或 ya=yb 中至少一个成立。
保证所有测试用例中 h 的总和不超过 106。
输出格式
For each test case, output "Alice" if Alice wins, "Bob" if Bob wins, and "Draw" if neither player can secure a victory. You can output each letter in any case (lowercase or uppercase). For example, the strings "bOb", "bob", "Bob", and "BOB" will be accepted as Bob's victory.
对于每个测试用例,若 Alice 获胜,则输出 “Alice”;若 Bob 获胜,则输出 “Bob”;若双方均无法确保获胜,则输出 “Draw”。字母大小写不限(即小写或大写均可)。例如,字符串 “bOb”、“bob”、“Bob” 和 “BOB” 均被视为 Bob 获胜的有效输出。
输入输出样例
输入#1
12 6 5 2 2 5 3 4 1 2 1 4 1 1 4 1 3 1 1 5 5 1 4 5 2 4 4 1 1 4 4 10 10 1 6 10 8 10 10 2 6 10 7 10 10 9 1 8 1 10 10 8 1 10 2 10 10 1 1 2 1 10 10 1 3 4 1 10 10 3 1 1 1
输出#1
Alice Bob Draw Draw Draw Alice Draw Draw Bob Alice Alice Draw
输入解题思路,AI测评打分。不知道怎么写?