codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.