Tunnetko yrityksen nimeltä Just Ordinary Inventions? Tämän yrityksen toimialana on luoda "ihan tavallisia keksintöjä".

JOI-kun pelaa Just Ordinary Inventionsin kehittämää uusinta peliä.

Tässä pelissä tutkitaan luolastoa, joka koostuu useista huoneista ja useista käytävistä. Käytävä yhdistää kaksi eri huonetta luolastossa, ja sitä pitkin voi kulkea molempiin suuntiin. Minkä tahansa kahden eri huoneen välillä on enintään yksi niitä yhdistävä käytävä, eikä ole olemassa käytäviä, joiden molemmat päät olisivat samassa huoneessa. Lisäksi tiedetään, että minkä tahansa kahden luolaston huoneen välillä voidaan kulkea käyttämällä joitakin käytäviä. Jokainen huone muistuttaa suuresti muita huoneita, eikä huoneita, joista lähtee yhtä monta käytävää, voida erottaa toisistaan pelkästään huoneen ulkonäköä katsomalla.

Tässä pelissä tutkimisen helpottamiseksi jokaisessa huoneessa on merkki ja jalusta. Huoneesta lähtevät käytävät voidaan laskea merkin perusteella 1., 2., ... käytäväksi. Luolaston rakenne ei muutu pelin aikana. Näin ollen, jos liikut samasta huoneesta käyttäen samannumeroista käytävää, saavut aina samaan huoneeseen. Jalustalla on koristeena yksi jalokivi, jonka väriä pelaaja voi muuttaa. Jalokiven väri on jokin väreistä 1, 2, ..., $X$, ja pelin alkaessa jokaisen huoneen jalokiven väri on väri 1. Jalokiven väri ei muutu, ellei pelaaja muuta sitä.

JOI-kun tajusi, että jos tämän luolaston rakenne, eli se, miten huoneet ovat yhteydessä toisiinsa käytävillä, tunnettaisiin, peli olisi helppo läpäistä. Yrityksistään huolimatta JOI-kun ei kuitenkaan pystynyt selvittämään luolaston rakennetta. Siksi olet päättänyt kirjoittaa ohjelman, joka selvittää luolaston rakenteen JOI-kunin puolesta.

Tehtävä

Laadi ohjelma, joka tutkii luolastoa ja selvittää sen rakenteen. Koska JOI-kun ei kuitenkaan halunnut luolaston rakenteen paljastuvan kokonaan, ohjelma ei saa vastata suoraan luolaston rakennetta, vaan sen täytyy vastata jokaiselle kokonaisluvulle $i$ välillä 1 ... $R$ arvo "kuinka monta sellaista huoneparia on, joiden välillä pääsee kulkemaan käyttäen vähintään täsmälleen $i$ käytävää" (parit, joissa huoneiden järjestys on vaihdettu, katsotaan samaksi pariksi).

Luolaston tutkimista varten käytössäsi on kirjasto, joka suorittaa seuraavat toiminnot:

• Kertoo, kuinka monta käytävää nykyisestä huoneesta lähtee.
• Kertoo nykyisen huoneen jalustalla olevan jalokiven värin.
• Muuttaa nykyisen huoneen jalustalla olevan jalokiven värin annetuksi väriksi (voit antaa myös saman värin kuin nykyinen väri). Sen jälkeen valitaan yksi huoneesta lähtevä käytävä ja siirrytään sitä pitkin toiseen huoneeseen.
• Kertoo, monesko nykyisestä huoneesta lähtevistä käytävistä viimeksi käytetty käytävä oli.

Toteutuksen yksityiskohdat

Sinun tulee kirjoittaa yksi ohjelma, joka toteuttaa JOI-kunin vastausmenetelmän. Ohjelman on sisällytettävä otsikkotiedosto dungeon2.h.

Ohjelman tulee toteuttaa seuraava aliohjelma:

• void Inspect(int R)
  • Tätä aliohjelmaa kutsutaan täsmälleen kerran alussa.
  • Parametri $R$ ilmaisee, että sinun täytyy vastata jokaiselle kokonaisluvulle $i$ välillä 1 ... $R$ arvo "kuinka monta sellaista huoneparia on, joiden välillä pääsee kulkemaan käyttäen vähintään täsmälleen $i$ käytävää".

Lisäksi sinun täytyy kutsua seuraavaa aliohjelmaa vastataksesi kysymyksiin:

• void Answer(int D, int A)
  • Parametrit $D$ ja $A$ ilmaisevat, että vastaat tässä kutsussa "on olemassa $A$ huoneparia, joiden välillä pääsee kulkemaan käyttäen vähintään täsmälleen $D$ käytävää".

Aliohjelman Answer kutsun on kuitenkin täytettävä seuraavat ehdot:

• $D$:n on oltava kokonaisluku välillä 1 ... $R$. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [1].
• Aliohjelmaa Answer ei saa kutsua useammin kuin kerran samalla parametrilla $D$. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [2].
• Aliohjelmaa Answer on kutsuttava täsmälleen $R$ kertaa. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [3].
• $A$:n on oltava niiden huoneparien lukumäärä, joiden välillä pääsee kulkemaan käyttäen vähintään täsmälleen $D$ käytävää. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [4].

Jos Answer-kutsu tuomitaan vääräksi, ohjelman suoritusta ei välttämättä jatketa sen jälkeen.

Lisäksi voit kutsua ohjelmassasi seuraavia aliohjelmia:

• void Move(int I, int C)
  • Parametri $I$ on sen käytävän numero, jota pitkin pelaaja valitsee kulkea. Välittömästi tämän kutsun jälkeen pelaaja siirtyy toiseen huoneeseen käyttäen nykyisestä huoneesta lähtevää $I$:ttä käytävää.
  • Parametri $C$ ilmaisee, että nykyisen huoneen jalustalla olevan jalokiven väri muutetaan väriksi $C$ ennen huoneesta poistumista.

Aliohjelman Move kutsun on kuitenkin täytettävä seuraavat ehdot:

• Parametrin $I$ on oltava kokonaisluku välillä 1 ... $K$, missä $K$ on siitä huoneesta lähtevien käytävien lukumäärä, jossa pelaaja parhaillaan on. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [5].
• Parametrin $C$ on oltava kokonaisluku välillä 1 ... $X$, missä $X$ on jalokiven värivaihtoehtojen lukumäärä. Arvo $X$ on määritelty kullekin osatehtävälle. Jos tämä ei toteudu, suoritus tuomitaan vääräksi: Incorrect [6].

• Aliohjelmaa Move saa kutsua enintään 1,500,000 kertaa. Jos sitä kutsutaan useammin, suoritus tuomitaan vääräksi: Incorrect [7].

• int NumberOfRoads()

  • Tämä funktio palauttaa siitä huoneesta lähtevien käytävien lukumäärän, jossa pelaaja parhaillaan on.

• int LastRoad()

  • Tämä funktio palauttaa tiedon siitä, monesko nykyisestä huoneesta lähtevistä käytävistä viimeksi käytetty käytävä oli. Jos tätä funktiota kutsutaan ennen kuin aliohjelmaa Move on kutsuttu kertaakaan, se palauttaa arvon -1.

• int Color()

  • Tämä funktio palauttaa sen huoneen jalustalla olevan jalokiven värin, jossa pelaaja parhaillaan on.

Kun aliohjelman Inspect kutsu päättyy, vastaus arvioidaan.

Voit vapaasti toteuttaa muita aliohjelmia sisäiseen käyttöön tai määritellä globaaleja muuttujia. Palautuksesi ei kuitenkaan saa millään tavoin käyttää vakiosyötettä tai vakiotulostetta eikä käsitellä mitään tiedostoja.

Kääntäminen ja suorittaminen

Kilpailusivustolta ladattavassa paketissa on malliarvostelija (sample grader). Tämä paketti sisältää myös mallin tiedostosta, joka sinun tulee palauttaa.

Malliarvostelija koostuu yhdestä tiedostosta, grader.c tai grader.cpp. Voit testata ohjelmaasi suorittamalla seuraavat komennot:

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

Jos kääntäminen onnistuu, syntyy suoritettava tiedosto nimeltä grader.

Huomaa, että varsinaisessa arvioinnissa käytettävä arvostelija poikkeaa malliarvostelijasta. Malliarvostelija toimii yhtenä prosessina, joka lukee syötteen vakiosyötteestä ja kirjoittaa tulokset vakiotulosteeseen.

Malliarvostelijan syöte

Malliarvostelija lukee vakiosyötteestä seuraavat tiedot:

• 1. rivillä on välilyönnein erotetut kokonaisluvut $N, X, R$. Tämä tarkoittaa, että luolastossa on $N$ huonetta (huone 1, huone 2, ..., huone $N$), jalokivien värejä on $X$ erilaista, ja ohjelman on vastattava $R$ arvoa.
• Seuraavilla $2N$ rivillä, rivillä $(2i - 1)$ ($1 \le i \le N$) on kokonaisluku $D_i$, joka ilmaisee, että huoneesta $i$ lähtee $D_i$ käytävää. Rivillä $2i$ ($1 \le i \le N$) on $D_i$ välilyönnein erotettua kokonaislukua $T_{i1}, T_{i2}, \dots, T_{iD_i}$. Tämä tarkoittaa, että kulkemalla huoneesta $i$ lähtevää $j$:ttä käytävää ($1 \le j \le D_i$) päädytään huoneeseen $T_{ij}$.
• Seuraavilla $R$ rivillä, rivillä $j$ ($1 \le j \le R$) on kokonaisluku $A_j$. Tämä tarkoittaa, että on olemassa $A_j$ huoneparia, joiden välillä pääsee kulkemaan käyttäen vähintään täsmälleen $j$ käytävää. Toisin sanoen, jos jokaisella $j$ ($1 \le j \le R$) aliohjelmaa Answer kutsutaan parametrilla $D$ arvolla $j$ ja parametrilla $A$ arvolla $A_j$, malliarvostelija tuomitsee vastauksen oikeaksi, ja muussa tapauksessa vääräksi.

Malliarvostelija kutsuu aliohjelmaasi siten, että pelaajan alkusijainti on huone 1.

Malliarvostelijan tuloste

Kun ohjelman suoritus päättyy normaalisti, malliarvostelija tulostaa vakiotulosteeseen yhdelle riville seuraavat tiedot (lainausmerkkejä ei todellisuudessa tulosteta):

• Jos vastaus on oikein, funktion Move kutsujen lukumäärä tulostetaan muodossa Accepted : #move = 8.
• Jos vastaus on väärin, virheen tyyppi tulostetaan muodossa Wrong Answer [1].

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot. Katso suureiden $N, D_i, T_{ij}$ merkitys kohdasta 'Malliarvostelijan syöte'.

• $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$ ja $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$) ovat erisuuria.
• Jokaiselle $i, j$ ($1 \le i \le N, 1 \le j \le D_i$) on olemassa sellainen $k$ ($1 \le k \le D_{T_{ij}}$), että $T_{T_{ij}k} = i$.
• Minkä tahansa kahden huoneen välillä voidaan kulkea käyttämällä joitakin käytäviä.

Osatehtävät

Olkoon seuraavassa $N$ syötetiedoissa olevien luolaston huoneiden lukumäärä ja $M$ käytävien lukumäärä.

Osatehtävä 1 [17 pistettä]

Seuraavat ehdot pätevät:

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

Osatehtävä 2 [27 pistettä]

Seuraavat ehdot pätevät:

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

Osatehtävä 3 [56 pistettä]

• Ehto $X = 3$ pätee.

Tässä osatehtävässä pistemäärä määräytyy seuraavasti:

• Olkoon $L$ seuraavan lausekkeen suurin arvo yli kaikkien tämän osatehtävän testitapausten:
  • $\frac{C}{M}$, missä $C$ on Move-kutsujen lukumäärä.
• Tällöin tämän osatehtävän pistemäärä on:
  • Jos $L \le 14$, 56 pistettä.
  • Jos $14 < L \le 32$, $\lfloor 70 - L \rfloor$ pistettä.
  • Jos $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ pistettä.
  • Jos $64 < L$, 0 pistettä.

Tässä $\lfloor x \rfloor$ tarkoittaa suurinta kokonaislukua, joka ei ylitä lukua $x$.

Esimerkit

Syöte 1

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

Tuloste 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)

Huomautus

Tämän esimerkin funktiokutsut eivät välttämättä ole mielekkäitä kutsuja.