【题解】Game With Telephone Numbers

A telephone number is a sequence of exactly 1111 digits such that its first digit is 8.

Vasya and Petya are playing a game. Initially they have a string ss of length nn (nn 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 ss becomes 11. If the resulting string is a telephone number, Vasya wins, otherwise Petya wins.

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).Input

The first line contains one integer nn (13≤n<10513≤n<105, nn is odd) — the length of string ss.

The second line contains the string ss (|s|=n|s|=n) consisting only of decimal digits.Output

If Vasya has a strategy that guarantees him victory, print YES.

Otherwise print NO.

13
8380011223344

output

YES

input

15
807345619350641

output

NO

Note

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.

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.

这道题在做的时候卡了我很久，一直没有思路，想了想其实就是这样的一个问题：

1、手机号首位为8，数字长度为11位。总的字符串长度位数位奇数。也就是说，每个玩家操作的次数相等，都是(n-11)/2次

2、V在游戏中是先手，那么在游戏之中，一定是P进行最后一次操作，然后就定胜负。

题目问的是，何种情况下，V才有十足的胜算，也就是说，游戏一开始，他就知道自己赢定了。

那么问题就转化成了：经过V在字符串的前面取（n-11)/2次的不为8的字符的操作，以及P在字符串中取前(n-11)/2个字符8之后，在字符串的第1位是不是字符8？

这样子思考的话，就可以比较快速的解出这道题目

以下是网站上题解的代码

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    cin >> n >> s;
    int cnt1 = (n - 11) / 2;
    int cnt2 = cnt1;
    string res = "";
    for(int i = 0; i < n; ++i){
        if(s[i] == '8'){
            if(cnt1 > 0) --cnt1;
            else res += s[i];
        }
        else{
            if(cnt2 > 0) --cnt2;
            else res += s[i];
        }
    }
    
    if(res[0] == '8') cout << "YES\n";
    else cout << "NO\n";
	return 0;
}

我的方法和网站上的不太一样，我的没有那么直观，但是其实思路是一样的。

#include<iostream>
#include<string>
using namespace std;


int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int js=0;
    int jss=0;
    bool is_ok = false;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='8')
            js++;
        else{
            jss++;
        }
        if(js==(n-11)/2+1)
        {
            if(jss>(n-11)/2)
                cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
            is_ok=true;
            break;
        }
    }
    if(!is_ok) cout<<"NO"<<endl;

}

网站上的方法是真的进行了分别删除字符串的前(n-11)/2个为‘8’和不为‘8’的字符的操作

而我这个是查找第(n-11)/2+1个‘8’，那么假设它前面的所有’8’都已经被删掉了，然后对于这个’8’，它前面还有jss个非8的字符。如果jss<(n-11)/2，那么就意味着，V可以把这个8前面的所有字符都删掉，那么就能确保自己赢得游戏。

比完赛之后思考了一下，的确我这个方法感觉就是绕了一个大弯，其实这道题只要抓住本质是，为了确保在当前输入情况下，V一定能赢得比赛，那么V就要采取不删除8的策略，把8移动到头部。而P要尽量使得V不能赢得比赛，所以他要采取尽可能地删掉头部的8，防止V把8移动到头部。