Anna ja Bruno ovat uhkapelimestareita. He pelaavat peliä D-taron kanssa, joka toimii pelin jakajana.

Tässä pelissä Anna ja Bruno oleskelevat eri huoneissa. He voivat viestiä keskenään vain rikkinäisen laitteen avulla. D-taro antaa Annalle kokonaisluvun. Annan ja Brunon tavoitteena tässä pelissä on lähettää annettu kokonaisluku Annalta Brunolle laitetta käyttäen.

Kun peli alkaa, Anna ilmoittaa aluksi kokonaisluvun $m$, joka on välillä $1$ ja $2\,000$, rajat mukaan lukien. Sen jälkeen he pelaavat $Q$ kierrosta. Kierros $i$ ($1\le i\le Q$) suoritetaan seuraavasti.

1. D-taro antaa Annalle kokonaisluvun $A_i$.
2. Anna syöttää taulukot $s_i,t_i$ laitteeseen. Taulukoiden $s_i,t_i$ jokaisen alkion tulee olla joko $0$ tai $1$. Taulukoilla $s_i,t_i$ tulee olla sama pituus, ja pituuden tulee olla välillä $1$ ja $m$, rajat mukaan lukien.
3. Olkoon $u_i$ taulukko, joka on saatu taulukoista $s_i$ ja $t_i$ lomitussekoituksella (riffle shuffle, katso alta). Tällöin laite lähettää taulukon $u_i$ Brunolle.
4. Bruno lähettää kokonaisluvun D-tarolle. Jos tämä kokonaisluku on sama kuin D-taron Annalle antama kokonaisluku $A_i$, Anna ja Bruno voittavat tämän kierroksen.

Kirjoita ohjelmat, jotka toteuttavat Annan ja Brunon strategiat siten, että he voittavat kaikki $Q$ kierrosta.

Lomitussekoitus

Sanomme, että taulukko $Z$ on saatu taulukoista $X$ ja $Y$ lomitussekoituksella, jos voimme jakaa taulukon $Z$ alkiot kahteen ryhmään siten, että seuraavat kaksi ehtoa täyttyvät.

• Ensimmäisen ryhmän alkioista samassa järjestyksessä muodostettu taulukko on yhtä suuri kuin taulukko $X$.
• Toisen ryhmän alkioista samassa järjestyksessä muodostettu taulukko on yhtä suuri kuin taulukko $Y$.

Esimerkiksi taulukko $Z=[1,1,1,0,0,0]$ on saatu taulukoista $X=[1,1,0]$ ja $Y=[1,0,0]$ lomitussekoituksella, koska taulukon $Z$ ensimmäisestä, toisesta ja neljännestä alkiosta samassa järjestyksessä muodostettu taulukko on $[1,1,0]$, ja taulukon $Z$ kolmannesta, viidennestä ja kuudennesta alkiosta samassa järjestyksessä muodostettu taulukko on $[1,0,0]$.

Toisaalta, jos $X=[1,1,0]$, $Y=[1,0,0]$ ja $Z=[0,0,0,1,1,1]$, taulukkoa $Z$ ei ole saatu taulukoista $X$ ja $Y$ lomitussekoituksella.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa kaksi tiedostoa.

Ensimmäinen tiedosto on Anna.cpp. Sen tulee toteuttaa Annan strategia. Sen tulee toteuttaa seuraavat funktiot. Ohjelman tulee sisällyttää otsikkotiedosto Anna.h esikääntäjädirektiivillä #include.

• int Declare()

  Tätä funktiota kutsutaan kerran pelin alussa.

  • Paluuarvo on Annan ilmoittama kokonaisluku $m$.
  • Kokonaisluvun $m$ tulee olla välillä $1$ ja $2\,000$, rajat mukaan lukien. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Kun funktiota Declare on kutsuttu, tätä funktiota kutsutaan $Q$ kertaa. Tämän funktion $i$-s kutsu ($1\le i\le Q$) vastaa kierroksen $i$ vaiheita 1 ja 2.

  • Parametri A on D-taron Annalle antama kokonaisluku $A_i$.
  • Paluuarvo on Annan laitteeseen syöttämien kahden taulukon $s_i,t_i$ muodostama pari.
  • Taulukoiden $s_i,t_i$ jokaisen alkion tulee olla joko $0$ tai $1$. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [2].
  • Molempien taulukoiden $s_i,t_i$ pituuksien tulee olla välillä $1$ ja $m$, rajat mukaan lukien. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [3].
  • Taulukoilla $s_i,t_i$ tulee olla sama pituus. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [4].

Toinen tiedosto on Bruno.cpp. Sen tulee toteuttaa Brunon strategia. Sen tulee toteuttaa seuraava funktio. Ohjelman tulee sisällyttää otsikkotiedosto Bruno.h esikääntäjädirektiivillä #include.

• long long Bruno(std::vector<int> u)

  Kun Anna on syöttänyt taulukot laitteeseen, tätä funktiota kutsutaan kerran. Yhteensä tätä funktiota kutsutaan $Q$ kertaa. Tämän funktion $i$-s kutsu ($1\le i\le Q$) vastaa kierroksen $i$ vaiheita 3 ja 4.

  • Parametri u on laitteen Brunolle kierroksella $i$ lähettämä taulukko $u_i$.
  • Paluuarvo on Brunon D-tarolle lähettämä kokonaisluku.
  • Paluuarvon tulee olla sama kuin D-taron Annalle antama kokonaisluku $A_i$. Jos tämä ehto ei täyty, ohjelmasi tuomitaan tuloksella Wrong Answer [5].

Tärkeitä huomautuksia

• Ohjelmasi voi toteuttaa muita funktioita sisäiseen käyttöön tai käyttää globaaleja muuttujia. Palautetut tiedostot käännetään yhdessä tarkistimen (grader) kanssa yhdeksi suoritettavaksi tiedostoksi. Kaikki globaalit muuttujat ja sisäiset funktiot tulee määritellä nimettömässä nimiavaruudessa (unnamed namespace), jotta vältetään ristiriidat muiden tiedostojen kanssa. Arvostelun aikana ohjelma suoritetaan kahtena prosessina, yhtenä Annalle ja yhtenä Brunolle. Annan prosessi ja Brunon prosessi eivät voi jakaa globaaleja muuttujia.
• Ohjelmasi ei saa käyttää standardisyötettä eikä standarditulostetta. Ohjelmasi ei saa viestiä muiden tiedostojen kanssa millään tavalla. Ohjelmasi voi kuitenkin tulostaa virheenkorjaustietoja standardivirhetulosteeseen (standard error).

Kääntäminen ja testiajo

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

Esimerkkitarkistin on tiedosto grader.cpp. Testataksesi ohjelmaasi aseta grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h samaan hakemistoon ja aja seuraava komento kääntääksesi ohjelmasi.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Kun käännös onnistuu, luodaan 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ä.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Esimerkkitarkistimen tuloste

Esimerkkitarkistin tulostaa seuraavat tiedot standarditulosteeseen (lainausmerkit selkeyden vuoksi).

• Jos ohjelmasi todetaan oikeaksi, se kirjoittaa funktion Declare paluuarvon $m$ muodossa ”Accepted: 2000”.
• Jos ohjelmasi tuomitaan joksikin Wrong Answer -tyypeistä, esimerkkitarkistin kirjoittaa sen tyypin muodossa ”Wrong Answer [1]”.

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

Kun esimerkkitarkistinta suoritetaan, kunkin kierroksen lomitussekoitus lasketaan näennäissatunnaislukujen avulla. Niiden tulokset eivät muutu eri suorituskertojen välillä. Vaihda näennäissatunnaislukujen siemenlukua suorittamalla esimerkkitarkistin seuraavalla tavalla.

./grader 2022

Ensimmäisen argumentin tulee olla kokonaisluku.

Rajoitukset

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Osatehtävät

1. (5 pistettä) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 pistettä) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 pistettä) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 pistettä) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 pistettä) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 pistettä) Ei lisärajoituksia. Tässä osatehtävässä pistemääräsi lasketaan seuraavasti.

   • Olkoon $m^*$ Annan ilmoittamien kokonaislukujen $m$ maksimi tämän osatehtävän kaikissa testitapauksissa.
   • Pistemääräsi on seuraava.

Esimerkit

Tässä on esimerkkisyöte esimerkkitarkistimelle ja sitä vastaavat funktiokutsut.

Syöte 1

2
42
2000

Esimerkkifunktiokutsut

Tässä esimerkkisyötteessä on $Q\ (=2)$ kierrosta. Kierroksella 1 D-taro antaa Annalle kokonaisluvun $A_1\ (=42)$. Kierroksella 2 D-taro antaa Annalle kokonaisluvun $A_2\ (=2000)$.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.