Problem 270: Robotzi

Un grup de N roboți votează pentru acceptarea unei propuneri. Fiecare robot votează cu DA sau NU. Roboții vor să decidă dacă cel puțin jumătate dintre ei au votat DA.

Toți roboții stau în linie. Roboții se pot afla în diferite stări. Stările sunt elemente ale mulțimii {1, ..., 28, Y, N, Major, Minor}. La fiecare pas, robotul i se află într-o stare $\it S_i$ și trebuie să decidă în ce stare să treacă pentru pasul următor. Această decizie depinde doar de $\it S_{i−1}$ , $\it S_i$ și $\it S_{i+1}$ deoarece roboții pot să își vadă doar vecinii. Ei au un set comun de reguli pe care îl urmează (la un pas, toți roboții își vor schimba starea după acest set de reguli simultan). Cel mai din stânga, respectiv cel mai din dreapta robot văd starea X spre stânga, respectiv spre dreapta (această stare reprezintă un robot “lipsă”). La pasul 0 toți roboții se află fie în starea N (NU), fie în starea Y (DA). Ei urmează setul de reguli până când un robot declară că rezultatul este Major (cel puțin jumătate din voturi sunt DA) sau Minor (mai puțin de jumătate din voturi sunt DA). Dacă mai mulți roboți fac o declarație în același timp, cel mai din stânga are prioritate. De asemenea, roboții au o limită pentru numărul de iterații. Ei trebuie să ia o decizie până în acea limită.

Voi trebuie să determinați un set de reguli pentru ca roboții să decidă în mod corect dacă să accepte propunerea sau nu. Formatul de baza pentru reguli este următorul, observați cum în acest enunt, litere majuscule italice reprezintă o stare oarecare:

$\displaystyle \text{\it L \ M \ R \ → \ E}$

Un robot în starea $\it M$ al carui vecin spre stânga se află în starea $\it L$ și vecinul din dreapta în starea $\it R$ trece în starea $\it E$ . Puteți să folosiți caracterul ? ca wildcard. Acesta poate să înlocuiască orice stare dintre $\it L, M, R$ . De asemenea, puteți să folosiți mai multe stări separate prin /, fără spații (doar pentru $\it L, M, R$ ). De exemplu:

$\displaystyle \text{ ? \ 2/Y/10 \ X \ → \ Major }$

Aici, cel mai din dreapta robot (deoarece vecinul său spre dreapta se află în starea $\it X$ ), când starea lui este una dintre 2, Y sau 10, va declara majoritate. Dacă există mai multe reguli care se potrivesc pentru un robot, atunci prima va avea prioritate. De exemplu:

$\displaystyle \text{ 1 \ ? \ 3 \ → \ Major } \\ \text{ ? \ 2 \ 3/10 \ → \ 4 }$

Dacă un robot se află în starea 2, cu vecini în stările 1 (în stânga) și 3 (în dreapta), acest robot va declara majoritate deoarece regula corespunzătoare este prima. Atenție! Dacă un robot nu are nicio instrucțiune aplicabilă la un moment dat, se consideră a fi greșită soluția.

Date de ieșire

Trebuie să afișați setul de reguli, fiecare regulă pe câte o linie separată.

Restricții și precizări

1 ≤ N ≤ 1 500
Numărul maxim de iterații este 7 500.
Notă: Puteți selecta "Output Only" ca limbaj pentru a trimite doar setul de reguli sau puteți declara un șir de caractere în C++ pe mai multe rânduri astfel:

std::string longString = R""""( 
line1
line2
)"""";

Punctare

Punctajul pe test este înmulțit cu un coeficient S care este determinat în funcție de numărul de iterații efectuate și de o constantă T specifică fiecărui test:

Dacă NrIteratii ≤ T, atunci S = 1;
Dacă T < NrIteratii ≤ T + 7, atunci S = 0.85;
Dacă NrIteratii > T + 7, atunci $max \left(0.75 · \left (\frac{T +8}{NrIteratii} \right) ^ {0.85}, 0.2 \right)$ .

Subtask 1 (10 puncte)

N ≤ 10
T = N + 1

Subtask 2 (20 de puncte)

N ≤ 99
N este impar
T = N + 1

Subtask 3 (30 de puncte)

N ≤ 1 499
N este impar
$T = ⌊\frac{N}{2}⌋+3$

Subtask 4 (20 de puncte)

N ≤ 1 500
N este par.
$T = ⌊\frac{N}{2}⌋+3$

Subtask 5 (20 de puncte)

N ≤ 1 500
$T = ⌊\frac{N}{2}⌋+3$

Exemplu

stdin

În această problemă nu se citește nimic din input. În schimb, vă oferim chiar aici o ocazie de regăsire a eului.
Pe-un picior de plai,
Pe-o gură de rai,
Iată vin în cale,
Se cobor la vale,
...

stdout

Y Y ? -> Major
? Y Y -> Major
Y ? Y -> Major
Y/N Y/N Y/N -> Minor
? Y ? -> Y
? N ? -> N

Explicație

Exemplul dat este o secvenţă de instrucțiuni care reuşeşte să decidă corect rezultatul pentru N = 3.
Putem observa că primele 4 reguli pot fi folosite doar de robotul 2 (căci roboții 1 sau 3 “văd” un X), iar acel robot poate decide câştigătorul (căci N = 3). Observăm că regulile trebuie aplicate în ordine, cum e specificat în enunț. Celelalte 2 reguli sunt pentru roboții 1 sau 3.

Robotzi