Triangle Card Game

AtCoder

IDarc170_d

Time2000ms

Memory256MB

Difficulty—

Alice and Bob will play a game. Initially, Alice and Bob each have $N$ cards, with the $i$\-th card of Alice having the integer $A_i$ written on it, and the $i$\-th card of Bob having the integer $B_i$ written on it. The game proceeds as follows: * Prepare a blackboard with nothing written on it. * Alice eats one of her cards and writes the integer from the eaten card on the blackboard. * Next, Bob eats one of his cards and writes the integer from the eaten card on the blackboard. * Finally, Alice eats one more of her cards and writes the integer from the eaten card on the blackboard. If it is possible to form a (non-degenerate) triangle with the side lengths of the three integers written on the blackboard, Alice wins; otherwise, Bob wins. Determine who wins when both players act optimally. Solve each of the $T$ given test cases. ## Constraints * $1 \leq T \leq 10^5$ * $2 \leq N \leq 2 \times 10^5$ * $1 \leq A_i, B_i \leq 10^9$ * All input values are integers. * The sum of $N$ over all test cases in a single input is at most $2 \times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ Each case is given in the following format: $N$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$ [samples]

Samples

Input #1

3
3
1 2 3
4 5 6
4
6 1 5 10
2 2 4 5
10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

Output #1

Bob
Alice
Alice

In the first test case, for example, the game could proceed as follows:

*   Alice eats the card with $2$ written on it and writes $2$ on the blackboard.
*   Bob eats the card with $4$ written on it and writes $4$ on the blackboard.
*   Alice eats the card with $1$ written on it and writes $1$ on the blackboard.
*   The numbers written on the blackboard are $2, 4, 1$. There is no triangle with side lengths $2, 4, 1$, so Bob wins.

For this test case, the above process is not necessarily optimal for the players, but it can be shown that Bob will win if both players act optimally.

API Response (JSON)

{
  "problem": {
    "name": "Triangle Card Game",
    "description": {
      "content": "Alice and Bob will play a game. Initially, Alice and Bob each have $N$ cards, with the $i$\\-th card of Alice having the integer $A_i$ written on it, and the $i$\\-th card of Bob having the integer $B_i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc170_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob will play a game.\nInitially, Alice and Bob each have $N$ cards, with the $i$\\-th card of Alice having the integer $A_i$ written on it, and the $i$\\-th card of Bob having the integer $B_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments