305807: CF1091H. New Year and the Tricolore Recreation
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
New Year and the Tricolore Recreation
题意翻译
Alice和Bob玩游戏。给定$n,f$,表示有$n$行的棋盘,每行有三个棋子。Alice每次可以选择一行将该行左边的一个或两个棋子往右移动$d$步,Bob每次可以选择一行将该行右边的一个或两个棋子往左移动$d$步。 要求移动时一个棋子不能跨越另一个棋子,且$d$是质数或两个质数的乘积,且$d\neq f$。求出Alice和Bob分别作为先手时,谁能赢。 $n\leq10^5$,坐标绝对值$\leq10^5$。题目描述
Alice and Bob play a game on a grid with $ n $ rows and infinitely many columns. In each row, there are three tokens, blue, white and red one. Before the game starts and after every move, the following two conditions must hold: - Any two tokens are not in the same cell. - In each row, the blue token is to the left of the white token, and the red token is to the right of the white token. First, they pick a positive integer $ f $ , whose value is valid for the whole game. Second, the starting player is chosen and makes his or her first turn. Then players take alternating turns. The player who is unable to make a move loses. During a move, a player first selects an integer $ k $ that is either a prime number or a product of two (not necessarily distinct) primes. The smallest possible values of $ k $ are thus $ 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, \dots $ . Furthermore, $ k $ must not be equal to the previously picked integer $ f $ . Each turn, a move is performed in exactly one of the rows. If it is Alice's turn, she chooses a single blue token and moves it $ k $ cells to the right. Alternatively, she may move both the blue and the white token in the same row by the same amount $ k $ to the right. On the other hand, Bob selects a single red token and moves it $ k $ cells to the left. Similarly, he may also move the white and the red token in the corresponding row by $ k $ to the left. Note that Alice may never move a red token, while Bob may never move a blue one. Remember that after a move, the two conditions on relative positions of the tokens must still hold. Both players play optimally. Given the initial state of the board, determine who wins for two games: if Alice starts and if Bob starts.输入输出格式
输入格式
The first line contains a two integers $ n $ and $ f $ ( $ 1 \leq n \leq 10^5 $ , $ 2 \leq f \leq 2 \cdot 10^5 $ ) — the number of rows and the forbidden move, respectively. Each of the next $ n $ lines contains three integers $ b_i $ , $ w_i $ , $ r_i $ ( $ -10^5 \leq b_i < w_i < r_i \leq 10^5 $ ) — the number of column in which the blue, white and red token lies in the $ i $ -th row, respectively.
输出格式
Output two lines. The first line should contain the name of the winner when Alice starts, and the second line should contain the name of the winner when Bob starts.
输入输出样例
输入样例 #1
1 6
0 3 9
输出样例 #1
Alice
Bob
输入样例 #2
1 2
0 3 9
输出样例 #2
Alice
Bob
输入样例 #3
10 133
-248 -193 -187
97 101 202
-72 67 91
23 89 215
-129 -108 232
-223 -59 236
-99 86 242
-137 -109 -45
-105 173 246
-44 228 243
输出样例 #3
Bob
Alice