Revolver

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 128 MB
Avtor:
  • Nino Bašić
  • UPM 2019

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Padli ste v kremplje zlikovca Gennadyja (lik iz filma Limitless, ki ga odigra Andrew Howard), ki vas namerava izpustiti na prostost pod enim samim pogojem. Igrali boste rusko ruleto. Gennady vam je dal velik revolver, ki ima boben z n komorami. Pred vami je napolnil boben s k naboji, zato natančno veste, v katerih komorah so naboji. Pred začetkom morate boben zavrteti. Udarno kladivce se bo nahajalo nad neko naključno izbrano komoro (vsaka ima enako verjetnost, da bo izbrana). Revolver morate p-krat sprožiti. Po vsakem strelu se bo boben zavrtel za eno komoro naprej v smeri urinega kazalca. Ker je Gennady dobrosrčen zlikovec, vam je omogočil, da bo vsakem strelu naredite izbiro:

  • revolver lahko nemudoma še enkrat sprožite ali pa
  • ponovno zavrtite boben.

Kakšna je verjetnost, da boste izpuščeni na prostost, če igrate optimalno? Ugotoviti morate tudi, kaj je optimalna strategija, tj. kako ravnati po vsakem strelu: ali bomo boben ponovno zavrteli ali pa nemudoma sprožili še enkrat? Predpostavimo seveda, da prejšnji strel preživimo.

Vhodni podatki

V prvi vrstici se nahajajo celo število T, tj. število testnih primerov.

Vsak testni primer opisujeta po dve vrstici. V prvi vrstici sta števili n in p, ločeni s presledkom. V naslednji vrstici je niz dolžine n, sestavljen iz znakov '*' in '.'. Niz podaja položaje nabojev v bobnu revolverja po vrsti v smeri urinega kazalca. Znak '.' predstavlja prazno komoro, znak '*' pa komoro z nabojem. V nizu se znak '*' pojavi natanko k-krat.

Omejitve vhodnih podatkov

  • 1 \leq T \leq 1000
  • 1 \leq k < n \leq 100
  • 1 \leq p \leq 20

Izhodni podatki

Za vsak testni primer izpišite p vrstic. Prva vrstica naj vsebuje verjetnost preživetja. Vsaka od naslednjih p - 1 vrstic naj vsebuje niz 'ROLL' ali 'FIRE' (brez navednic), pri čemer naj bo v i-ti vrstici niz 'ROLL', če morate po i-tem strelu boben ponovno zavrteti in 'FIRE', če je boljše, da sprožite nemudoma.

Če obstaja več optimalnih strategij, je vseeno, katero izpišete. Sprejete bodo rešitve, katerih verjetnost se od pravilne rešitve razlikuje za največ 10^{-9}.

Primer

Vhod

3
6 2
...**.
8 5
.*.*.*.*
9 5
.****....

Izhod

0.5
FIRE
0.03125
ROLL
ROLL
ROLL
ROLL
0.14814814815
FIRE
ROLL
FIRE
FIRE

Komentar

V prvem primeru revolver sprožite dvakrat. Verjetnost, da boste po prvem strelu preživeli, je 2/3. Če streljate ponovno, je verjetnost, da preživite drugi strel, enaka 3/4. Če bi boben še enkrat zavrteli, bi bila verjetnost 2/3. Optimalno je, da streljamo ponovno, verjetnost preživetja obeh strelov pa je 1/2 = 0.5.

V drugem primeru morate boben vedno ponovno zavrteti, saj dveh zaporednih strelov ne bi preživeli.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task