1104B.md (1208B)
1 Source: https://codeforces.com/problemset/problem/1104/B 2 3 B. Game with string 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 Two people are playing a game with a string $s$, consisting of lowercase latin letters. 22 23 On a player's turn, he should choose two consecutive equal letters in the string and delete them. 24 25 For example, if the string is equal to "xaax" than there is only one possible turn: delete "aa", so the string will become "xx". A player not able to make a turn loses. 26 27 Your task is to determine which player will win if both play optimally. 28 29 Input 30 31 The only line contains the string $s$, consisting of lowercase latin letters ($1 \leq |s| \leq 100\,000$), where $|s|$ means the length of a string $s$. 32 33 Output 34 35 If the first player wins, print "Yes". If the second player wins, print "No". 36 37 Examples 38 39 Input 40 41 ``` 42 abacaba 43 ``` 44 45 Output 46 47 ``` 48 No 49 ``` 50 51 Input 52 53 ``` 54 iiq 55 ``` 56 57 Output 58 59 ``` 60 Yes 61 ``` 62 63 Input 64 65 ``` 66 abba 67 ``` 68 69 Output 70 71 ``` 72 No 73 ``` 74 75 Note 76 77 In the first example the first player is unable to make a turn, so he loses. 78 79 In the second example first player turns the string into "q", then second player is unable to move, so he loses.