Решение задачи Камень-ножницы-бумага с ограничениями с Codeforces

Без пояснения   Просмотров: 19


Пусть n — некоторое положительное целое число, а a,b,c — некоторые неотрицательные целые числа такие, что a+b+c=n.

Алиса и Боб собираются сыграть в камень-ножницы-бумага n раз. Алиса знает последовательность жестов, которые будет играть Боб. Однако она должна сыграть камень ровно a раз, бумагу — ровно b раз, а ножницы — ровно c раз.

Обратите внимание, что хоть игра и называется камень-ножницы-бумага, для синхронизации с английским названием все обозначения идут в порядке камень-бумага-ножницы.

Алиса выигрывает, если она побеждает Боба хотя бы в ⌈n2⌉ (n2, округленное вверх до ближайшего целого) раундах, иначе — проигрывает.

Напоминаем, что в камень-ножницы-бумага:

камень побеждает ножницы;
бумага побеждает камень;
ножницы побеждают бумагу.
Ваша задача — по заданной последовательности жестов, которые будет играть Боб, и по числам a,b,c, определить, может ли Алиса выиграть. И если может, то найти некоторую последовательность жестов, которая приведет Алису к победе.

Если существует несколько решений, выведите любое из них.

Код

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);ios_base::sync_with_stdio(0);
    int q,n,a,b,c;
    cin>>q;
    while(q--){
        cin >> n >> a >> b >> c;
        string s;
        cin>>s;
        string t(n, ' ');
        int wins = 0;
        for (int i = 0; i < n; i++){
            if(s[i] == 'R' and b > 0){
                t[i] = 'P'; 
                b--;
                wins++;
            }  
            if(s[i]=='P' and c>0){t[i]='S';c--;wins++;}
            if(s[i]=='S' and a>0){t[i]='R';a--;wins++;}
        }
        for (int i=0;i<n;i++){
            if(t[i]!=' ')continue;
            if(s[i]=='R'){if(a>0){t[i]='R';a--;}else t[i]='S';}
            if(s[i]=='P'){if(b>0){t[i]='P';b--;}else t[i]='R';}
            if(s[i]=='S'){if(c>0){t[i]='S';c--;}else t[i]='P';}
        }
        if(wins >= (n + 1) / 2)
            cout << "YES\n" << t << '\n';
        else 
            cout << "NO\n";
    }
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться