Problem A
Brenglaða Safn Tyrfings

Tyrfingur viðheldur gögnunum sínum á mjög brenglaðan máta. Í staðinn fyrir að geyma talnarununa sína í einni beinni hækkandi röð, þá hefur hann tilnefnt eitt gildið sem aðalgildið. Því næst hefur hann látið aðalgildið benda á eitt gildi sem er minna og eitt gildi sem er stærra og heyra þau undir aðalgildinu. Fyrir hvert gildi þar undir gerir hann hið sama, en ef ekkert gildi er til sem er minna eða stærra, þá benda þau ekki á neitt. Ef gildi $x$ bendir á minna gildi $y$ að þá eru öll gildi sem heyra undir $y$ minni en $x$. Ef gildi $x$ bendir á stærra gildi $y$ að þá eru öll gildi sem heyra undir $y$ stærri en $x$. Athugið einnig að ef $z$ heryrir undir $y$ og $y$ undir $x$ þá heyrir $z$ undir $x$.

Þú hefur fengið það verkefni að safna saman hver raðaði listinn af tölunum er sem Tyrfingur er að viðhalda. Vandamálið er að Tyrfingur skrifaði þetta ekki niður, heldur geymir hann þetta allt í hausnum sínum. Því þarftu að spyrja Tyrfing aftur og aftur til að fá upplýsingar skref fyrir skref. Enn fremur er talnarunan trúnaðarmál og þú mátt ekki sjá tölurnar. Því þarftu einfaldlega að leiðbeina Tyrfing um hvernig hann á að skrifa rununa niður á blað í hækkandi röð. Hann setur svo blaðið í umslag og innsiglar áður en hann lætur þig hafa það.

Í upphafi er Tyrfingur að hugsa um aðalgildið og getur þú leiðbeint honum með því að segja honum að skrifa gildið niður, hugsa næst um gildið sem er minna, gildið sem er stærra, eða að fara til baka og hugsa um gildið sem kom honum á gildið sem hann er að núverandi að hugsa um.

Gagnvirkni

Þetta er gagnvirkt verkefni. 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:

Forrit þitt skal ítrekað leiðbeina Tyrfingi með mörgum umferðum af samskiptum. Í hverri umferð skal forrit þitt framkvæma eina af eftirfarandi aðgerðum:

1. skrifa út p til að segja Tyrfingi að skrifa núverandi tölu niður,

2. skrifa út < til að segja Tyrfingi að hugsa núna um töluna sem er minni,

3. skrifa út > til að segja Tyrfingi að hugsa núna um töluna sem er stærri,

4. skrifa út ^ til að segja Tyrfingi að hugsa um töluna sem kom honum að núverandi tölu,

5. skrifa út ! til að tákna að Tyrfingur eigi að innsigla bréfið í umslagi núna.

Eftir hverja aðgerð getur komið svar frá yfirferðarforritinu sem forrit þitt skal lesa inn. Í hverri umferð, eftir að hafa skrifað út aðgerðina, skal forrit þitt lesa inn:

1. eina heiltölu sem er $1$ ef þetta allt er í lagi, og $0$ ef forrit þitt gerði mistök og á að hætta keyrslu samstundis,

2. eina heiltölu sem er $1$ ef aðgerðin tókst og gildið er til, og $0$ annars,

3. eina heiltölu sem er $1$ ef aðgerðin tókst og gildið er til, og $0$ annars,

4. eina heiltölu sem er $1$ ef aðgerðin tókst og gildið er til, og $0$ annars, sem gerist einungis fyrir aðalgildið,

5. ekkert og forrit þitt skal hætta keyrslu samstundis.

Þetta er gefið í sömu röð og samsvarandi aðgerðir að ofan.

Fjöldi gilda í rununni má tákna með $n$ og ávallt gildir að $1 \leq n \leq 25\, 000$. Mest máttu reyna að skipta um gildi $3n$ sinnum.

Vertu viss um að gera flush eftir hverja aðgerð, t.d., með

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

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

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

<

1

<

0

p

1

>

1

<

0

p

1

>

0

^

1

^

1

p

1

>

1

<

0

p

1

>

0

^

1

^

0

!