2181B.md (1948B)
1 Source: https://codeforces.com/problemset/problem/2181/B 2 3 B. Battle of Arrays 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 1024 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Alice and Bob play a turn-based game. Initially, Alice has an array $a$ of $n$ positive integers, and Bob has an array $b$ of $m$ positive integers. The players take turns, with Alice moving first. 22 23 On a player's turn, they must choose one element $x$ from their own array and the maximal element $y$ from their opponent's array. Then they perform the following operation: 24 25 * If $y \leq x$: the element $y$ is destroyed (removed from the opponent's array). 26 * If $y \gt x$: the element $y$ is decreased by $x$ (the value of $y$ becomes $y - x$). 27 28 A player wins if, after their move, the opponent's array becomes empty. 29 30 Assuming both players play optimally, determine the winner. 31 32 Input 33 34 Each input contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). 35 36 The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$) — the sizes of Alice's and Bob's arrays respectively. 37 38 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — Alice's array. 39 40 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le 10^9$) — Bob's array. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ and the sum of $m$ over all test cases does not exceed $10^5$. 43 44 Output 45 46 For each test case, print the name of the winner of the game if both players follow the optimal strategy: "Alice" or "Bob". 47 48 Example 49 50 Input 51 52 ``` 53 2 54 55 1 1 56 57 70 58 59 90 60 61 2 3 62 63 30 30 64 65 20 20 40 66 ``` 67 68 Output 69 70 ``` 71 Alice 72 Bob 73 ``` 74 75 Note 76 77 In the first test Alice moves and decreases Bob's element by $70$, so it becomes $20$. Then Bob moves and decreases Alice's element by $20$, so it becomes $50$. Finally, Alice moves, destroys Bob's element, and wins.