codeforces-scrape

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

2104C.md (3327B)


      1 Source: https://codeforces.com/problemset/problem/2104/C
      2 
      3 C. Card Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Alice and Bob are playing a game. They have $n$ cards numbered from $1$ to $n$. At the beginning of the game, some of these cards are given to Alice, and the rest are given to Bob.
     22 
     23 Card with number $i$ beats card with number $j$ if and only if $i \gt j$, with one exception: card $1$ beats card $n$.
     24 
     25 The game continues as long as each player has at least one card. During each turn, the following occurs:
     26 
     27 1. Alice chooses one of her cards and places it face up on the table;
     28 2. Bob, seeing Alice's card, chooses one of his cards and places it face up on the table;
     29 3. if Alice's card beats Bob's card, both cards are taken by Alice. Otherwise, both cards are taken by Bob.
     30 
     31 A player can use a card that they have taken during one of the previous turns.
     32 
     33 The player who has no cards at the beginning of a turn loses. Determine who will win if both players play optimally.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 5000$) — the number of test cases.
     38 
     39 Each test case consists of two lines:
     40 
     41 * the first line contains a single integer $n$ ($2 \le n \le 50$) — the number of cards;
     42 * the second line contains $n$ characters, each either A or B. If the $i$-th character is A, then card number $i$ is initially given to Alice; otherwise, it is given to Bob.
     43 
     44 Additional constraint on the input: in each test case, at least one card is initially given to Alice, and at least one card is initially given to Bob.
     45 
     46 Output
     47 
     48 For each test case, output Alice if Alice wins with optimal play, or Bob if Bob wins. It can be shown that if both players play optimally, the game will definitely end in a finite number of turns with one of the players winning.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 8
     56 
     57 2
     58 
     59 AB
     60 
     61 2
     62 
     63 BA
     64 
     65 4
     66 
     67 ABAB
     68 
     69 4
     70 
     71 BABA
     72 
     73 3
     74 
     75 BAA
     76 
     77 5
     78 
     79 AAAAB
     80 
     81 5
     82 
     83 BAAAB
     84 
     85 6
     86 
     87 BBBAAA
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 Alice
     94 Bob
     95 Bob
     96 Bob
     97 Alice
     98 Alice
     99 Bob
    100 Alice
    101 ```
    102 
    103 Note
    104 
    105 In the first test case, Alice has only one card, and Bob has only one card. Since Alice's card beats Bob's card, she wins after the first turn.
    106 
    107 In the second test case, Alice has only one card, and Bob has only one card. Since Bob's card beats Alice's card, he wins after the first turn.
    108 
    109 In the third test case, there are two possible game scenarios:
    110 
    111 * if Alice plays the card $1$ on the first turn, Bob can respond with the card $2$ and take both cards. Then, Alice has to play the card $3$ on the second turn, and Bob will respond by playing the card $4$. Then, he wins;
    112 * if Alice plays the card $3$ on the first turn, Bob can respond with the card $4$ and take both cards. Then, Alice has to play the card $1$, and Bob can respond either with the card $2$ or the card $3$. Then, he wins.
    113 
    114 In the fourth test case, there are two possible game scenarios:
    115 
    116 * if Alice plays the card $2$ on the first turn, Bob can respond with the card $3$ and take both cards. Then, Alice has to play the card $4$ on the second turn, and Bob will respond by playing the card $1$. Then, he wins;
    117 * if Alice plays the card $4$ on the first turn, Bob can respond with the card $1$ and take both cards. Then, Alice has to play the card $2$, and Bob can respond either with the card $3$ or the card $4$. Then, he wins.