codeforces-scrape

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

1155B.md (1714B)


      1 Source: https://codeforces.com/problemset/problem/1155/B
      2 
      3 B. Game with Telephone Numbers
      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 A telephone number is a sequence of exactly $11$ digits such that its first digit is 8.
     22 
     23 Vasya and Petya are playing a game. Initially they have a string $s$ of length $n$ ($n$ is odd) consisting of digits. Vasya makes the first move, then players alternate turns. In one move the player must choose a character and erase it from the current string. For example, if the current string 1121, after the player's move it may be 112, 111 or 121. The game ends when the length of string $s$ becomes 11. If the resulting string is a telephone number, Vasya wins, otherwise Petya wins.
     24 
     25 You have to determine if Vasya has a winning strategy (that is, if Vasya can win the game no matter which characters Petya chooses during his moves).
     26 
     27 Input
     28 
     29 The first line contains one integer $n$ ($13 \le n \lt 10^5$, $n$ is odd) — the length of string $s$.
     30 
     31 The second line contains the string $s$ ($|s| = n$) consisting only of decimal digits.
     32 
     33 Output
     34 
     35 If Vasya has a strategy that guarantees him victory, print YES.
     36 
     37 Otherwise print NO.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 13
     45 8380011223344
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 YES
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 15
     58 807345619350641
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 NO
     65 ```
     66 
     67 Note
     68 
     69 In the first example Vasya needs to erase the second character. Then Petya cannot erase a character from the remaining string 880011223344 so that it does not become a telephone number.
     70 
     71 In the second example after Vasya's turn Petya can erase one character character 8. The resulting string can't be a telephone number, because there is no digit 8 at all.