1553-C, *1200

Problem - 1553C - Codeforces

풀이

• 두 팀 $odd$와 $even$이 돌아가면서 승부차기를 한다
• $1$은 성공, $0$은 실패, $?$은 성공 또는 실패를 의미할 때, 최소 몇번의 킥을하게 되는가?

 

$O(1)$

승부차기에서 더 이상 킥을 해도 의미가 없는경우는
'지고 있는 팀이 남은 킥을 모두 성공해도 점수를 뒤집을 수 없을 때' 이다

따라서 킥의 횟수를 줄이려면 한쪽 팀이 유리하게 $?$를 바꿔야한다

i) $?$를 $odd$팀이 유리하게 바꿨을 때 최소 킥의 횟수
ii) $?$를 $even$팀이 유리하게 바꿨을 때 최소 킥의 횟수
를 각각 구하며 더 작은 값이 구하려는 값이다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int minimum_kicks(vector<char> &v)
{
    int odd_score = 0;
    int even_score = 0;
    int odd_remain = 5;
    int even_remain = 5;
    loop(i, 10){
        if(i%2) {
            if(v[i] == '1') odd_score++;
            odd_remain--;
        }
        else {
            if(v[i] == '1') even_score++;
            even_remain--;
        }
 
        if(odd_score > even_score && odd_score - even_score > even_remain) return i;
        if(even_score > odd_score && even_score - odd_score > odd_remain) return i;
    }
    return 10;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        vector<char> adven_even(11);
        vector<char> adven_odd(11);
 
        loop(i, 10){
            cin >> adven_even[i];
            adven_odd[i] = adven_even[i];
        }
 
        loop(i, 10){
            if(adven_even[i] == '?'){
                if(i%2 == 0) {
                    adven_even[i] = '1';
                    adven_odd[i] = '0';
                }
                else {
                    adven_even[i] = '0';
                    adven_odd[i] = '1';
                }
            }
        }
 
        cout << min(minimum_kicks(adven_even), minimum_kicks(adven_odd)) << endl;
    }
 
    return 0;
}cs