Anna ja Bruno ovat arkeologeja. He tutkivat raunioita Iranissa.

Heidän tehtävänsä ovat seuraavat: Anna vierailee raunioilla ja löytää muinaisesineitä, ja Bruno analysoi tulokset perusleirissä.

Heidän tutkimuksensa on suunniteltu kestämään $Q(=1\,000)$ päivää. Joka päivä Anna lähettää tulokset Brunolle viestintälaitteen avulla. Kunkin päivän tulos ilmaistaan kokonaislukuna $X$.

Anna voi käyttää viestintälaitetta vain kerran päivässä. Se voi lähettää pituuden $N(=150)$ jonon, joka koostuu luvuista $0$ tai $1$.

Laite oli kuitenkin rikki. Pituuden $N$ jonossa on useita rikkoutuneita kohtia. Rikkoutuneessa kohdassa laite lähettää aina arvon $0$ riippumatta todellisesta asetetusta arvosta. Kun Anna lähettää jonon, hän näkee rikkoutuneiden kohtien sijainnit. Bruno ei kuitenkaan tiedä niitä. Rikkoutuneiden kohtien sijainnit ja rikkoutuneiden kohtien lukumäärä voivat muuttua joka päivä.

On olemassa vaara, että heidän tutkimuksensa viivästyy. Koska olet ehdolla kilpailijaksi Iranissa järjestettävään kansainväliseen ohjelmointikilpailuun, Anna ja Bruno pyytävät sinua kirjoittamaan ohjelman, joka lähettää heidän tutkimuksensa tulokset.

Tehtävä

Kirjoita kaksi ohjelmaa, jotka toteuttavat Annan ja Brunon välisen viestinnän.

• Kun annetaan jonon pituus $N$, lähetettävä kokonaisluku $X$, rikkoutuneiden kohtien lukumäärä $K$ ja rikkoutuneiden kohtien sijainnit $P$, ensimmäinen ohjelma asettaa Annan lähettämän jonon $S$.
• Kun annetaan Brunon vastaanottama jono $A$, toinen ohjelma palauttaa kokonaisluvun $X$.

Kohdassa, jossa viestintälaite toimii, jonolla $S$ ja jonolla $A$ on sama arvo. Rikkoutuneessa kohdassa jonossa $A$ on aina arvo $0$ riippumatta jonon $S$ arvoista.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa kaksi samalla ohjelmointikielellä kirjoitettua tiedostoa.

Ensimmäinen tiedosto on joko Anna.c tai Anna.cpp. Tämä tiedosto asettaa Annan lähettämän jonon ja toteuttaa seuraavan funktion. Ohjelman tulee sisällyttää otsikkotiedosto Annalib.h.

• void Anna( int N, long long X, int K, int P[] )

  Jokaisessa testitapauksessa tätä funktiota kutsutaan $Q=1\,000$ kertaa.

  • Parametri N on lähetettävän jonon pituus.
  • Parametri X on lähetettävä kokonaisluku.
  • Parametri K on rikkoutuneiden kohtien lukumäärä.
  • Parametri P[] on pituuden $K$ jono, joka kuvaa rikkoutuneiden kohtien sijainnit.

  Funktiossa Anna on kutsuttava seuraavaa funktiota.

  • void Set( int pos, int bit )

    Tämä funktio asettaa yhden bitin viestintälaitteen lähettämään jonoon $S$.

    • Parametri pos on asetettavan kohdan sijainti. pos on oltava kokonaisluku väliltä $0$ ja $N-1$, rajat mukaan lukien. Huomaa, että sijainnit numeroidaan alkaen luvusta $0$. Jos funktiota kutsutaan tämän välin ulkopuolella olevalla parametrilla, ohjelmasi tulkitaan vääräksi vastaukseksi: Wrong Answer[1]. Tätä funktiota ei saa kutsua useammin kuin kerran samalla parametrilla pos. Jos sitä kutsutaan useammin kuin kerran samalla parametrilla, ohjelmasi tulkitaan vääräksi vastaukseksi: Wrong Answer[2].
    • Parametri bit on jonon pos:nteen kohtaan asetettava arvo. Parametrin bit arvon on oltava joko $0$ tai $1$. Jos funktiota kutsutaan muilla parametreilla, ohjelmasi tulkitaan vääräksi vastaukseksi: Wrong Answer[3].

  Funktiota Set on kutsuttava täsmälleen $N$ kertaa funktiossa Anna. Kun funktio Anna päättyy, jos funktion Set kutsujen lukumäärä poikkeaa luvusta $N$, ohjelmasi tulkitaan vääräksi vastaukseksi: Wrong Answer[4].

  Ohjelmasi suoritus lopetetaan, jos Annan tekemä funktiokutsu katsotaan virheelliseksi.

Toinen tiedosto on joko Bruno.c tai Bruno.cpp. Tämä tiedosto palauttaa tutkimustulosta ilmaisevan kokonaisluvun ja toteuttaa seuraavan funktion. Ohjelman tulee sisällyttää otsikkotiedosto Brunolib.h.

• long long Bruno( int N, int A[] )

  Jokaisessa testitapauksessa tätä funktiota kutsutaan $Q=1\,000$ kertaa.

  • Parametri N on Brunon vastaanottaman jonon pituus.
  • Parametri A on pituuden $N$ kokonaislukujono. Se on Brunon vastaanottama jono.
  • Funktion Bruno on palautettava luvun $X$ arvo ja annettava se paluuarvonaan (return).

Arvostelumenettely

Arvostelu suoritetaan seuraavalla tavalla. Jos ohjelmasi tulkitaan vääräksi vastaukseksi (Wrong Answer), sen suoritus lopetetaan välittömästi.

1. Aseta cnt = 0.
2. Kutsu funktiota Anna kerran.
3. Olkoon $S$ funktion Anna asettama jono. Aseta jonossa $S$ arvo $0$ taulukon $P$ osoittamiin kohtiin, jolloin saadaan jono $A$. Kutsu funktiota Bruno kerran parametrilla $A$.
4. Aseta cnt = cnt +1. Jos $\mathrm{cnt}<Q$, siirry kohtaan (2). Jos $\mathrm{cnt}=Q$, siirry kohtaan (5).
5. Ohjelmasi pisteytetään.

Tärkeitä huomautuksia

• Suoritusaika ja muistinkäyttö lasketaan Arvostelumenettelyn kohdille (1), (2), (3), (4).
• Ohjelmasi ei saa tuottaa Wrong Answer -tulosta funktiokutsussa Anna kohdassa (2) tai Bruno kohdassa (3). Ohjelmasi on suoritettava ilman ajonaikaista virhettä (runtime error).
• Ohjelmasi voi toteuttaa muita funktioita sisäiseen käyttöön tai käyttää globaaleja muuttujia. Palautetut ohjelmat käännetään yhdessä tarkistimen (grader) kanssa yhdeksi suoritettavaksi tiedostoksi. Kaikki globaalit muuttujat ja sisäiset funktiot tulee määritellä static-määreellä muiden tiedostojen kanssa syntyvien ristiriitojen välttämiseksi. Koska Annan ja Brunon ohjelmat suoritetaan arvosteltaessa 2 erillisenä prosessina, ne eivät voi jakaa globaaleja muuttujia.
• Prosessin aikana kumpaakin funktioista Anna ja Bruno kutsutaan $Q=1\,000$ kertaa. Ohjelmiesi käyttämät muuttujat tulee alustaa asianmukaisesti.
• Ohjelmasi ei saa käyttää standardisyötettä eikä standarditulostetta. Ohjelmasi ei saa kommunikoida muiden tiedostojen kanssa millään menetelmällä.

Kääntäminen ja koekäyttö

Voit ladata kilpailun verkkosivulta arkistotiedoston, joka sisältää esimerkkitarkistimen (sample grader) ohjelmasi testaamista varten. Arkistotiedosto sisältää myös esimerkkilähdekooditiedoston ohjelmallesi.

Esimerkkitarkistin koostuu yhdestä lähdekooditiedostosta, joka on joko grader.c tai grader.cpp. Jos ohjelmasi ovat esimerkiksi Anna.c ja Bruno.c tai Anna.cpp ja Bruno.cpp, voit kääntää ohjelmasi suorittamalla seuraavat komennot.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Kun käännös onnistuu, syntyy suoritettava tiedosto grader.

Huomaa, että varsinainen tarkistin eroaa esimerkkitarkistimesta. Esimerkkitarkistin suoritetaan yhtenä prosessina, joka lukee syötetiedot standardisyötteestä ja kirjoittaa tulokset standarditulosteeseen.

Esimerkkitarkistimen syöte

Esimerkkitarkistin lukee seuraavat tiedot standardisyötteestä.

• Ensimmäisellä rivillä on kokonaisluku $Q$.
• Sen jälkeen annetaan $Q$ kyselyn tiedot.

• Kunkin kyselyn tiedot koostuvat kahdesta rivistä seuraavasti.

  • Ensimmäisellä rivillä on kolme välilyönnein erotettua kokonaislukua $N$, $X$, $K$. Tämä tarkoittaa, että lähetettävän jonon pituus on $N$, Annan lähettämä kokonaisluku on $X$ ja rikkoutuneita kohtia on $K$.
  • Toisella rivillä on $K$ välilyönnein erotettua kokonaislukua $P_0,P_1,\cdots,P_{K-1}$. Tämä tarkoittaa, että jokaisella $i$ ($0\le i\le K-1$) jonon $P_i$:s kohta on rikki.

Esimerkkitarkistimen tuloste

Kun ohjelma päättyy onnistuneesti, esimerkkitarkistin kirjoittaa seuraavat tiedot standarditulosteeseen. (Lainausmerkkejä ei todellisuudessa tulosteta.)

• Jos ohjelmasi tulkitaan vääräksi vastaukseksi (Wrong Answer), esimerkkitarkistin tulostaa sen tyypin muodossa “Wrong Answer [1],” ja ohjelmasi suoritus lopetetaan.
• Jos mitään funktion Anna kutsua ei tulkita vääräksi vastaukseksi, esimerkkitarkistin tulostaa “Accepted” sekä luvun $L^*$ arvon. Luvun $L^*$ arvon selitys löytyy kohdasta Osatehtävät.

Jos ohjelmasi täyttää useamman kuin yhden Wrong Answer -tyypin ehdot, esimerkkitarkistin ilmoittaa niistä vain yhden.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

• $Q=1000$.
• $N=150$.
• $0\le X\le 1\,000\,000\,000\,000\,000\,000$.
• $1\le K\le 40$.
• $0\le P_i\le N-1$ ($0\le i\le K-1$).
• $P_i<P_{i+1}$ ($0\le i\le K-2$).

Osatehtävät

• Olkoon $L^*$ seuraavan arvon minimi yli kaikkien tämän tehtävän testitapausten.

  • Suurin kokonaisluku $L\le40$, jolla Bruno vastaa jokaisessa kyselyssä, jossa $K\le L$, oikean luvun $X$ arvon.

• Tämän tehtävän pistemäärä lasketaan seuraavalla tavalla:

  • Jos $L^*=0$, pistemäärä on 0 pistettä.
  • Jos $1\le L^*\le14$, pistemäärä on 8 pistettä.
  • Jos $15\le L^*\le37$, pistemäärä on $(L^*-15)\times2+41$ pistettä.
  • Jos $38\le L^*\le40$, pistemäärä on $(L^*-38)\times5+90$ pistettä.

Esimerkit

Tässä on esimerkkisyöte tarkistimelle ja sitä vastaavat funktiokutsut. Huomaa, että seuraava esimerkki ei täytä tämän tehtävän rajoituksia, koska $Q=2$, $N=3$.

Syöte 1

2
3 14 1
2
3 9 2
0 1

Esimerkkikutsut

Tässä funktioiden Anna(...), Bruno(...), Anna(...), Bruno(...) parametrit ovat seuraavat.