Problem F
Pizzastrengur

Mynd fengin af wikipedia.com

Í dag er leikjadagur hjá Tommapizzu þannig að Georg og félagar ætla að panta sér pizzu. Leikurinn virkar þannig að starfsmenn Tommapizzu velja sér leyniorð sem inniheldur einungis stafina {“P”, “I”, “Z”, “A”} og segja Georgi og félögum hvað það er langt. Ef Georg og félagar ná að giska á leyniorðið í að hámarki $m$ tilraunum þá fá þeir pizzuna frítt! Georg og félagar mega giska á styttri orð en þá segja starfsmenn Tommapizzu hvort orðið sé forskeyti af leyniorðinu. Getur þú hjálpað Georgi og félögum að giska á rétt orð þannig að þeir fái pizzuna frítt?

Orð $A$ er forskeyti af orði $B$ ef $B$ byrjar á $A$. Til dæmis er “PIZ” forskeyti af “PIZZA” en “ZZA” er ekki forskeyti af “PIZZA”.

Gagnvirkni

Þetta er gagnvirkt vandamál. Lausnin þín verður keyrð á móti gagnvirkum dómara sem les úttakið frá lausninni þinni og skrifar í inntakið á lausninni þinni. Þessi gagnvirkni fylgir ákveðnum reglum:

Dómarinn skrifar fyrst út heiltölu $n$ ($1 \leq n \leq 10^4$), lengd leyniorðsins $S$ sem inniheldur bara stafina {“P”, “I”, “Z”, “A”}.

Næst giskar lausnin þín á streng $P$ sem má innihalda 1 til $n$ stafi. Loks svarar dómarinn:

• Ef $P$ er ekki forskeyti af $S$ þá svarar dómarinn 0.

• Ef $P$ er forskeyti af $S$ þá svarar dómarinn 1.

• EF $P = S$ þá svarar dómarinn 2 og lausnin þín á að hætta að giska.

Vertu viss um að gera flush eftir hvert gisk, t.d., með

• print(..., flush=True) í Python,

• cout << ... << endl; í C++,

• System.out.flush(); í Java.

Með dæminu fylgir tól til þess að hjálpa við að prófa lausnina þína.

Stigagjöf

5

ZAP

0

PIZ

1

PIZZA

2