codeforces-scrape

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

1527B1.md (2661B)


      1 Source: https://codeforces.com/problemset/problem/1527/B1
      2 
      3 B1. Palindrome Game (easy version)
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The only difference between the easy and hard versions is that the given string $s$ in the easy version is initially a palindrome, this condition is not always true for the hard version.
     22 
     23 A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.
     24 
     25 Alice and Bob are playing a game on a string $s$ (which is initially a palindrome in this version) of length $n$ consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.
     26 
     27 In each turn, the player can perform one of the following operations:
     28 
     29 1. Choose any $i$ ($1 \le i \le n$), where $s[i] =$ '0' and change $s[i]$ to '1'. Pay 1 dollar.
     30 2. Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.
     31 
     32 Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.
     33 
     34 The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.
     35 
     36 Input
     37 
     38 The first line contains a single integer $t$ ($1 \le t \le 10^3$). Then $t$ test cases follow.
     39 
     40 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^3$).
     41 
     42 The second line of each test case contains the string $s$ of length $n$, consisting of the characters '0' and '1'. It is guaranteed that the string $s$ is a palindrome and contains at least one '0'.
     43 
     44 Note that there is no limit on the sum of $n$ over test cases.
     45 
     46 Output
     47 
     48 For each test case print a single word in a new line:
     49 
     50 * "ALICE", if Alice will win the game,
     51 * "BOB", if Bob will win the game,
     52 * "DRAW", if the game ends in a draw.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 2
     60 4
     61 1001
     62 1
     63 0
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 BOB
     70 BOB
     71 ```
     72 
     73 Note
     74 
     75 In the first test case of the example,
     76 
     77 * in the $1$-st move Alice has to perform the $1$-st operation, since the string is currently a palindrome.
     78 * in the $2$-nd move Bob reverses the string.
     79 * in the $3$-rd move Alice again has to perform the $1$-st operation. All characters of the string are '1', game over.
     80 
     81 Alice spends $2$ dollars while Bob spends $0$ dollars. Hence, Bob always wins.