Kannastu við fyrirtækið Just Ordinary Inventions? Starfsemi þessa fyrirtækis snýst um að búa til „bara venjulegar uppfinningar“.

JOI-kun er að spila nýjasta leikinn sem Just Ordinary Inventions þróaði.

Þessi leikur felst í því að kanna dýflissu sem samanstendur af nokkrum herbergjum og nokkrum göngum. Göng tengja saman tvö ólík herbergi í dýflissunni og hægt er að fara um þau í báðar áttir. Fyrir sérhver tvö ólík herbergi eru í mesta lagi ein göng sem tengja þau, og engin göng eru þannig að báðir endar séu í sama herberginu. Ennfremur er vitað að hægt er að komast milli hvaða tveggja herbergja sem er í dýflissunni með því að nota einhvern fjölda ganga. Hvert herbergi er mjög líkt hinum, og ekki er hægt að greina á milli herbergja sem hafa jafnmörg útgöng bara með því að horfa á útlit herbergisins.

Í þessum leik er hvert herbergi búið merki og stalli til aðstoðar við könnunina. Hægt er að telja göngin sem liggja út úr herbergi sem 1., 2., ... göng út frá merkinu. Bygging dýflissunnar breytist ekki á meðan á leiknum stendur. Því munt þú alltaf koma í sama herbergið ef þú ferð úr sama herberginu eftir göngum með sama númeri. Stallurinn er skreyttur einum gimsteini sem leikmaðurinn getur breytt litnum á. Litur gimsteinsins er einn af lit 1, lit 2, ..., lit $X$, og í upphafi leiks er litur gimsteinsins í hverju herbergi litur 1. Litur gimsteinsins breytist ekki nema leikmaðurinn breyti honum.

JOI-kun áttaði sig á því að ef bygging þessarar dýflissu, þ.e. hvernig herbergin eru tengd með göngum, væri þekkt, væri auðvelt að klára þennan leik. En sama hversu mikið JOI-kun reyndi gat hann ekki ákvarðað byggingu dýflissunnar. Þess vegna hefur þú ákveðið að skrifa forrit til að ákvarða byggingu dýflissunnar fyrir hönd JOI-kun.

Verkefni

Búðu til forrit sem kannar dýflissuna og ákvarðar byggingu hennar. Hins vegar, þar sem JOI-kun vildi ekki að bygging dýflissunnar yrði opinberuð að fullu, má forritið ekki svara með byggingu dýflissunnar beint, heldur verður það að svara með gildinu á „hversu mörg pör af herbergjum eru til þannig að hægt sé að komast á milli þeirra með að lágmarki nákvæmlega $i$ göngum“ (pör þar sem röð herbergja er snúið við teljast sama parið) fyrir hverja heiltölu $i$ frá 1 til $R$.

Til að kanna dýflissuna færðu safn (library) sem framkvæmir eftirfarandi aðgerðir:

• Fá að vita hversu mörg göng liggja út úr núverandi herbergi.
• Fá að vita lit gimsteinsins á stallinum í núverandi herbergi.
• Breyta lit gimsteinsins á stallinum í núverandi herbergi í tiltekinn lit (einnig er hægt að tilgreina sama lit og núverandi lit). Eftir það skal velja ein göng sem liggja út úr herberginu og fara í annað herbergi um þau göng.
• Fá að vita hvaða númer síðustu notuðu göng höfðu meðal þeirra ganga sem liggja út úr núverandi herbergi.

Útfærsluatriði

Þú verður að skrifa eitt forrit sem útfærir aðferðina fyrir JOI-kun til að svara. Forritið verður að innihalda dungeon2.h.

Forritið verður að útfæra eftirfarandi fall:

• void Inspect(int R)
  • Kallað er á þetta fall nákvæmlega einu sinni í upphafi.
  • Viðfangið $R$ gefur til kynna að þú verðir að svara með gildinu á „hversu mörg pör af herbergjum eru til þannig að hægt sé að komast á milli þeirra með að lágmarki nákvæmlega $i$ göngum“ fyrir hverja heiltölu $i$ frá 1 til $R$.

Einnig verður þú að kalla á eftirfarandi fall til að svara spurningunum:

• void Answer(int D, int A)
  • Viðföngin $D$ og $A$ gefa til kynna að í þessu kalli sértu að svara því að „það séu $A$ pör af herbergjum sem hægt er að komast á milli með að lágmarki nákvæmlega $D$ göngum“.

Hins vegar verður kallið á Answer að uppfylla eftirfarandi skilyrði:

• $D$ verður að vera heiltala á milli 1 og $R$. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [1].
• Ekki má kalla á Answer oftar en einu sinni með sama viðfanginu $D$. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [2].
• Kalla verður á Answer nákvæmlega $R$ sinnum. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [3].
• $A$ verður að vera fjöldi para af herbergjum sem hægt er að komast á milli með að lágmarki nákvæmlega $D$ göngum. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [4].

Ef kall á Answer er dæmt rangt er hugsanlegt að afgangurinn af forritinu verði ekki keyrður.

Auk þess getur þú kallað á eftirfarandi föll í forritinu þínu:

• void Move(int I, int C)
  • Viðfangið $I$ er númer ganganna sem leikmaðurinn velur að fara um. Strax eftir þetta kall fer leikmaðurinn í annað herbergi um $I$-tu göngin sem liggja út úr núverandi herbergi.
  • Viðfangið $C$ gefur til kynna að lit gimsteinsins á stallinum í núverandi herbergi sé breytt í lit $C$ áður en farið er í hitt herbergið.

Hins vegar verður kallið á Move að uppfylla eftirfarandi skilyrði:

• Viðfangið $I$ verður að vera heiltala á milli 1 og $K$, þar sem $K$ er fjöldi ganga sem liggja út úr herberginu þar sem leikmaðurinn er staddur. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [5].
• Viðfangið $C$ verður að vera heiltala á milli 1 og $X$, þar sem $X$ er fjöldi gerða af gimsteinalitum. Gildið á $X$ er ákvarðað fyrir hvert undirverkefni. Ef þetta er ekki uppfyllt verður það dæmt sem Rangt [6].

• Ekki má kalla á Move oftar en 1,500,000 sinnum. Ef kallað er oftar á það verður það dæmt sem Rangt [7].

• int NumberOfRoads()

  • Þetta fall skilar fjölda ganga sem liggja út úr herberginu þar sem leikmaðurinn er staddur.

• int LastRoad()

  • Þetta fall skilar hvaða númer síðustu notuðu göng höfðu meðal þeirra ganga sem liggja út úr núverandi herbergi. Hins vegar, ef kallað er á þetta fall áður en kallað hefur verið á Move þótt ekki sé nema einu sinni, skilar það -1.

• int Color()

  • Þetta fall skilar lit gimsteinsins á stallinum í herberginu þar sem leikmaðurinn er staddur.

Eftir að búið er að kalla á fallið Inspect er svarið dæmt.

Þér er frjálst að útfæra önnur föll til innri nota eða skilgreina víðværar breytur. Hins vegar má lausnin þín ekki eiga í neinum samskiptum við staðalinntak/staðalúttak eða nokkrar aðrar skrár á nokkurn hátt.

Þýðing og keyrsla

Sýnisyfirferðarforrit (sample grader) fylgir í skjalasafninu sem hægt er að hala niður af keppnisvefnum. Þetta skjalasafn inniheldur einnig sýnishorn af skránni sem þú þarft að skila.

Sýnisyfirferðarforritið samanstendur af einni skrá, grader.c eða grader.cpp. Til að prófa forritið þitt skaltu keyra eftirfarandi skipanir:

• Fyrir C: gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm
• Fyrir C++: g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Ef þýðingin tekst verður til keyrsluskrá sem heitir grader.

Athugið að raunverulega yfirferðarforritið sem notað er við mat er ólíkt sýnisyfirferðarforritinu. Sýnisyfirferðarforritið keyrir sem eitt ferli sem les inntak úr staðalinntaki og skrifar niðurstöður í staðalúttak.

Inntak sýnisyfirferðarforrits

Sýnisyfirferðarforritið les eftirfarandi gögn úr staðalinntaki:

• 1. línan inniheldur heiltölurnar $N, X, R$ aðskildar með bili. Þetta táknar að það séu $N$ herbergi í dýflissunni: herbergi 1, herbergi 2, ..., herbergi $N$, að það séu $X$ gerðir af gimsteinalitum og að forritið þurfi að svara $R$ gildum.
• Í næstu $2N$ línum inniheldur $(2i - 1)$-ta línan ($1 \le i \le N$) heiltölu $D_i$, sem táknar að $D_i$ göng liggi út úr herbergi $i$. Lína $2i$ ($1 \le i \le N$) inniheldur $D_i$ heiltölur $T_{i1}, T_{i2}, \dots, T_{iD_i}$ aðskildar með bilum. Þetta táknar að ef farið er eftir $j$-tu göngunum ($1 \le j \le D_i$) sem liggja út úr herbergi $i$ komist maður í herbergi $T_{ij}$.
• Í næstu $R$ línum inniheldur $j$-ta línan ($1 \le j \le R$) heiltölu $A_j$. Þetta táknar að það séu $A_j$ pör af herbergjum sem hægt er að komast á milli með að lágmarki nákvæmlega $j$ göngum. Það er, fyrir hvert $j$ ($1 \le j \le R$), ef kallað er á Answer með viðfangið $D$ sem $j$ og viðfangið $A$ sem $A_j$, mun sýnisyfirferðarforritið dæma það rétt, en annars rangt.

Sýnisyfirferðarforritið kallar á fallið þitt þannig að upphafsstaðsetning leikmannsins sé í herbergi 1.

Úttak sýnisyfirferðarforrits

Þegar keyrslu forritsins lýkur eðlilega skrifar sýnisyfirferðarforritið eftirfarandi upplýsingar í eina línu í staðalúttak (gæsalappir eru ekki skrifaðar út í raun):

• Ef rétt, þá er fjöldi kalla á fallið Move skrifaður út sem Accepted : #move = 8.
• Ef rangt, þá er tegund villunnar skrifuð út sem Wrong Answer [1].

Skilyrði

Öll inntaksgögn uppfylla eftirfarandi skilyrði. Sjá kaflann 'Inntak sýnisyfirferðarforrits' fyrir merkingu $N, D_i, T_{ij}$.

• $2 \le N \le 200$
• $3 \le X \le 100$
• $1 \le R \le 200$
• $1 \le D_i \le N - 1$ ($1 \le i \le N$)
• $1 \le T_{ij} \le N$ og $T_{ij} \neq i$ ($1 \le i \le N, 1 \le j \le D_i$)
• $T_{i1}, T_{i2}, \dots, T_{iD_i}$ ($1 \le i \le N$) eru ólík.
• Fyrir hvert $i, j$ ($1 \le i \le N, 1 \le j \le D_i$) er til $k$ ($1 \le k \le D_{T_{ij}}$) þannig að $T_{T_{ij}k} = i$.
• Hægt er að komast milli hvaða tveggja herbergja sem er með því að nota einhvern fjölda ganga.

Undirverkefni

Í framhaldinu látum við $N$ vera fjölda herbergja og $M$ vera fjölda ganga í dýflissunni í inntaksgögnunum.

Undirverkefni 1 [17 stig]

Eftirfarandi skilyrði eru uppfyllt:

• $N \le 50$
• $M \le 100$
• $X = 100$

Undirverkefni 2 [27 stig]

Eftirfarandi skilyrði eru uppfyllt:

• $N \le 50$
• $M \le 100$
• $X = 3$

Undirverkefni 3 [56 stig]

• $X = 3$ er uppfyllt.

Í þessu undirverkefni ákvarðast stigin á eftirfarandi hátt:

• Látum $L$ vera hæsta gildið á eftirfarandi fyrir öll prófunartilvik í þessu undirverkefni:
  • $\frac{C}{M}$, þar sem $C$ er fjöldi kalla á Move.
• Í þessu tilviki eru stigin fyrir þetta undirverkefni:
  • Ef $L \le 14$, 56 stig.
  • Ef $14 < L \le 32$, $\lfloor 70 - L \rfloor$ stig.
  • Ef $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ stig.
  • Ef $64 < L$, 0 stig.

Hér táknar $\lfloor x \rfloor$ stærstu heiltölu sem er ekki stærri en $x$.

Dæmi

Inntak 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Úttak 1

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

Athugasemd

Fallaköllin í þessu dæmi eru ekki endilega merkingarbær köll.