ГЖО 7-8 класс 2019 год

Задача G. Камень… Ножницы… Бумага...

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

$N + 1$ роботов будут участвовать в турнире по камень-ножницы-бумага и один из роботов ваш. В этом турнире каждый робот использует программу, представляющую собой серию ходов, каждый из которых должен быть одним из следующих: 'R'(камень), 'P'(бумага) или 'S'(ножницы). Бумага побеждает камень, камень побеждает ножницы, ножницы побеждает бумагу. Когда играет два робота, побеждает тот, кто первым сделал выигрышный ход. В начале каждый робот делает первый ход своей программы. Если ходы у них различны, один из них побеждает по правилам игры. Если ходы одинаковые, каждый робот выполняет следующий ход своей программы и т.д. Когда робот сделал последний ход своей программы и ему необходимо сделать следующий ход, то он делает первый ход своей программы. Если игра идет бесконечно долго, объявляется ничья. Вы случайном образом узнали программы своих $N$ соперников. Сделайте программу для своего робота, чтобы ваш робот мог победить любого другого робота.

Формат входного файла

В первой строке находится одно целое число $N(1 <= N <= 100)$ — количество ваших соперников. В следующих $N$ строках находятся по одной строке $C_i(1 <= |C_i| <= 100)$ — программы ваших соперников. $C_i$ состоит из букв 'R', 'P', 'S'.

Формат выходного файла

Если не существует победной программы для вашего робота, выведите "IMPOSSIBLE". Иначе, выведите победную программу для своего робота. Длина вашей программы не должна превосходить $10^4$. Гарантируется, что если ответ существует, то существует ответ длиной не более $10^4$. Если существует несколько ответов, выведите любой из них.

Примеры:

Вход

3
R
S
P

Ответ

IMPOSSIBLE

Вход

1
RP

Ответ

P

Вход

2
RP
S

Ответ

RPP

( Temirlan Satylkhanov )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define pb push_back
#define si size()

using namespace std;

const int inf = 2e9;

string a[110];
int now[110];
int ss[110];
bool used[110];

void rused(vector<int> b)
{
	for(int i = 0; i < b.si; ++i)
	{
		used[b[i]] = 1;
	}
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
    	cin >> a[i];
    	ss[i] = a[i].si;
	}
	string ans = "";
	//P-R-S-P
	for(int i = 0; i < 1e4; i++)
	{
		int r1 = 0, p1 = 0, s1 = 0;
		bool R = true, P = true, S = true;
		vector<int> r2, p2, s2;
		for(int j = 0; j < n; j++)
		{
			if(used[j])
				continue;
			if(a[j][now[j]] == 'R')
			{
				p1++;
				p2.pb(j);
				S = false;
			}
			if(a[j][now[j]] == 'P')
			{
				s1++;
				s2.pb(j);
				R = false;
			}
			if(a[j][now[j]] == 'S')
			{
				r2.pb(j);
				r1++;
				P = false;
			}
		}
		if(!R && !S && !P)
		{
			cout << "IMPOSSIBLE";
			return 0;
		}
		int mm[3];
		mm[0] = p1;
		mm[1] = s1;
		mm[2] = r1;
		sort(mm, mm + 3);
		reverse(mm, mm + 3);
		for(int j = 0; j < n; j++)
		{
			if(mm[j] == s1 && S)
		{
			ans += 'S';
			rused(s2);
			break;
		}
		if(mm[j] == p1 && P)
		{
			ans += 'P';
			rused(p2);
			break;
		}
		if(mm[j] == r1 && R)
		{
			ans += 'R';
			rused(r2);
			break;
		}
		}
		for(int j = 0; j < n; j++)
		{
			now[j]++;
			now[j] %= ss[j];
		}
		for(int j = 0; j < n; j++)
		{
			if(!used[j])
				break;
			if(used[j] && j == (n - 1))
			{
				cout << ans;
				return 0;
			}
		}
	}
	cout << "IMPOSSIBLE";
}

что в 3 тесте?