Fişierul intrare/ieşire:rps.in, rps.outSursăONI 2013, Baraj
AutorAndrei GrigoreanAdăugată descipianusFMI Ciprian Olariu scipianus
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rps

Dezamăgită de rezultatul de la ONI 2013, Miruna s-a gîndit să îşi încerce norocul la campionatul mondial de ”Rock – Paper – Scissors”. Pentru cei care nu sunt familiarizaţi cu jocul, regulile sunt următoarele:

  • Întotdeauna se vor înfrunta direct doi jucători.
  • Pentru a decide învingătorul unei runde, cei doi vor face anumite gesturi în acelaşi timp folosindu-şi mîinile:
    • Palma întinsă reprezintă hîrtia.
    • Două degete întinse reprezintă foarfecele.
    • Pumnul strîns reprezintă piatra.
  • Piatra bate foarfecele, foarfecele bat hîrtia, iar hîrtia bate piatra.
  • În cazul în care ambii jucători fac aceeaşi alegere, runda se termină remiză.

La această ediţie a campionatului mondial organizatorii vor să evite pe cît posibil confruntările care se termină remiză. Drept urmare au decis ca orice meci să se joace în maximum K runde: va fi declarat cîştigător primul jucător care reuşeşte să cîştige o rundă. Dacă în toate cele K runde cei doi fac aceleaşi alegeri, atunci confruntarea dintre ei este declarată remiză. O victorie valorează W puncte, o remiză D puncte, iar o înfrîngere nu schimbă punctajul total al unui concurent. Sistemul de joc este sub formă de campionat, ceea ce înseamnă că Miruna se va înfrunta pe rînd cu toţi ceilalţi N concurenţi.

Spre deosebire de celelalte competiţii de ”Rock – Paper – Scissors” din lume, la acest campionat mondial jucătorii nu au voie să facă alegerile în mod aleator. În schimb, înainte de începutul campionatului, ei trebuie să prezinte juriului o serie de exact K opţiuni pentru cele K runde, urmînd ca în fiecare confruntare să facă aceleaşi alegeri. Practic, membrii juriului vor şti rezultatul oricărei confruntări încă dinaintea startului campionatului.

Fiind o fiinţă matinală, asemenea concurenţilor de la ONI 2013, Miruna se trezeşte de dimineaţă în ziua concursului şi ajunge prima la locul desfăşurării probei. Folosindu-şi farmecele ei nemaipomenite, Miruna poate să citescă minţile adversarilor săi. De fiecare dată cînd un alt concurent soseşte la locul desfăşurării probei ea poate afla seria de K opţiuni pe care acesta le va prezenta juriului. Folosindu-se de aceste informaţii, Miruna vrea să găsească o strategie care să îi maximizeze scorul.

Din nefericire, Miruna nu cunoaşte numărul total N al concurenţilor înscrişi la probă, aşa că de fiecare dată cînd soseşte un nou concurent, ea îşi regîndeşte strategia optimă care îi maximizează scorul (adică să obţină cât mai multe puncte în confruntarea cu acei concurenţi care au ajuns deja la locul desfăşurării probei). Vouă vi se cere să implementaţi un program care să o ajute pe Miruna.

Cerinţă

Se dau N liste de lungime K, reprezentînd opţiunile concurenţilor în ordinea în care aceştia sosesc la proba de concurs. Fiecare listă va fi formată din caracterele R, P şi S cu următoarea semnificaţie:

  • R – piatră (rock)
  • P – hîrtie (paper)
  • S – foarfece (scissors)

Programul vostru va afişa tot N liste de lungime K, formate din caracterele R, P şi S, reprezentînd strategia optimă a Mirunei la fiecare moment de timp cînd soseşte un concurent nou. În cazul în care există mai multe strategii optime, trebuie să o afişaţi pe cea minim lexicografică.

Date de intrare

Fişierul de intrare rps.in se vor afla numerele N, K, W şi D, cu semnificaţia din enunţ. Următoarele N linii vor conţine câte un şir de lungime K format din caracterele R, P şi S, reprezentînd opţiunile concurenţilor.

Date de ieşire

În fişierul de ieşire rps.out se vor afişa N linii, fiecare conţinând răspunsul cerut la fiecare moment de timp.

Restricţii

  • 1 ≤ N, K
  • 1 ≤ N * K ≤ 1.000.000
  • -1000 ≤ W, D ≤ 1000
  • Mirunei îi place doar î din i.

Exemplu

rps.inrps.out
4 3 2 1
RSP
PPP
SSP
SRR
PPP
PPS
PPS
RRP

Explicaţie

Strategiile din fişierul de ieşire îi garantează Mirunei scorurile 2, 4, 4 şi 6. Acestea sunt scorurile maxime care pot fi obţinute, iar soluţiile prezentate sunt minime din punct de vedere lexicografic.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content