Anna og Bruno eru fjárhættuspilameistarar. Þau munu spila leik við D-taro sem er gjafarinn í leiknum.

Í þessum leik dvelja Anna og Bruno í sitthvoru herberginu. Þau geta aðeins átt samskipti sín á milli með biluðu tæki. D-taro gefur Önnu heiltölu. Fyrir Önnu og Bruno er tilgangur leiksins að senda gefnu heiltöluna frá Önnu til Brunos með tækinu.

Þegar leikurinn hefst lýsir Anna í upphafi yfir heiltölu $m$ á bilinu $1$ til $2\,000$, báðar tölur meðtaldar. Síðan spila þau $Q$ umferðir. Umferð $i$ ($1\le i\le Q$) fer fram sem hér segir.

1. D-taro gefur Önnu heiltölu $A_i$.
2. Anna setur fylkin $s_i,t_i$ inn í tækið. Hvert stak í fylkjunum $s_i,t_i$ á að vera annaðhvort $0$ eða $1$. Fylkin $s_i,t_i$ eiga að hafa sömu lengd, og lengdin er á bilinu $1$ til $m$, báðar tölur meðtaldar.
3. Látum $u_i$ vera fylki sem fæst úr fylkjunum $s_i$ og $t_i$ með rifflustokkun (riffle shuffle, sjá að neðan). Þá sendir tækið $u_i$ til Brunos.
4. Bruno sendir heiltölu til D-taros. Ef þessi heiltala er sú sama og heiltalan $A_i$ sem D-taro gaf Önnu, vinna Anna og Bruno þessa umferð.

Skrifið forrit sem útfæra aðferðir Önnu og Brunos þannig að þau vinni allar $Q$ umferðirnar.

Rifflustokkun

Við segjum að fylki $Z$ fáist úr fylkjunum $X$ og $Y$ með rifflustokkun ef við getum skipt stökum fylkisins $Z$ í tvo hópa þannig að eftirfarandi tvö skilyrði séu uppfyllt.

• Fylkið sem samanstendur af stökunum í fyrri hópnum í sömu röð er jafnt fylkinu $X$.
• Fylkið sem samanstendur af stökunum í seinni hópnum í sömu röð er jafnt fylkinu $Y$.

Til dæmis fæst fylkið $Z=[1,1,1,0,0,0]$ úr $X=[1,1,0]$ og $Y=[1,0,0]$ með rifflustokkun vegna þess að fylkið sem samanstendur af fyrsta, öðru og fjórða staki $Z$ í sömu röð er fylkið $[1,1,0]$, og fylkið sem samanstendur af þriðja, fimmta og sjötta staki $Z$ í sömu röð er fylkið $[1,0,0]$.

Á hinn bóginn, ef $X=[1,1,0]$, $Y=[1,0,0]$ og $Z=[0,0,0,1,1,1]$, þá fæst fylkið $Z$ ekki úr $X$ og $Y$ með rifflustokkun.

Útfærsluatriði

Þú þarft að skila tveimur skrám.

Fyrri skráin er Anna.cpp. Hún á að útfæra aðferð Önnu. Hún á að útfæra eftirfarandi föll. Forritið á að bæta við Anna.h með forvinnsluskipuninni #include.

• int Declare()

  Kallað er á þetta fall einu sinni í upphafi.

  • Skilagildið er heiltalan $m$ sem Anna lýsir yfir.
  • Heiltalan $m$ á að vera á bilinu $1$ til $2\,000$, báðar tölur meðtaldar. Ef þetta skilyrði er ekki uppfyllt fær forritið þitt dóminn Wrong Answer [1].

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

  Eftir að kallað er á fallið Declare er kallað á þetta fall $Q$ sinnum. $i$-ta kallið ($1\le i\le Q$) á þetta fall samsvarar skrefi 1 og skrefi 2 í umferð $i$.

  • Viðfangið A er heiltalan $A_i$ sem D-taro gaf Önnu.
  • Skilagildið er parið af fylkjunum tveimur $s_i,t_i$ sem Anna setur inn í tækið.
  • Hvert stak í fylkjunum $s_i,t_i$ á að vera annaðhvort $0$ eða $1$. Ef þetta skilyrði er ekki uppfyllt fær forritið þitt dóminn Wrong Answer [2].
  • Lengdir beggja fylkjanna $s_i,t_i$ eiga að vera á bilinu $1$ til $m$, báðar tölur meðtaldar. Ef þetta skilyrði er ekki uppfyllt fær forritið þitt dóminn Wrong Answer [3].
  • Fylkin $s_i,t_i$ eiga að hafa sömu lengd. Ef þetta skilyrði er ekki uppfyllt fær forritið þitt dóminn Wrong Answer [4].

Seinni skráin er Bruno.cpp. Hún á að útfæra aðferð Brunos. Hún á að útfæra eftirfarandi fall. Forritið á að bæta við Bruno.h með forvinnsluskipuninni #include.

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

  Eftir að Anna setur fylkin inn í tækið er kallað á þetta fall einu sinni. Alls er kallað á þetta fall $Q$ sinnum. $i$-ta kallið ($1\le i\le Q$) á þetta fall samsvarar skrefi 3 og skrefi 4 í umferð $i$.

  • Viðfangið u er fylkið $u_i$ sem tækið sendi Bruno í umferð $i$.
  • Skilagildið er heiltalan sem Bruno sendir D-taro.
  • Skilagildið á að vera það sama og heiltalan $A_i$ sem D-taro gaf Önnu. Ef þetta skilyrði er ekki uppfyllt fær forritið þitt dóminn Wrong Answer [5].

Mikilvægar athugasemdir

• Forritið þitt getur útfært önnur föll til innri nota eða notað víðværar breytur (global variables). Innsendar skrár verða þýddar með yfirferðarforritinu (grader) og verða að einni keyranlegri skrá. Allar víðværar breytur og innri föll ættu að vera skilgreind í nafnlausu nafnarými (unnamed namespace) til að forðast árekstra við aðrar skrár. Þegar farið er yfir forritið verður það keyrt sem tvö ferli fyrir Önnu og Bruno. Ferli Önnu og ferli Brunos geta ekki deilt víðværum breytum.
• Forritið þitt má ekki nota staðalinntak né staðalúttak. Forritið þitt má ekki eiga samskipti við aðrar skrár með neinum hætti. Hins vegar má forritið þitt skrifa aflúsunarupplýsingar í staðalvilluúttak (standard error).

Þýðing og prufukeyrsla

Þú getur sótt safnskrá af vefsíðu keppninnar sem inniheldur sýnisyfirferðarforrit til að prófa forritið þitt. Safnskráin inniheldur einnig sýniskóðaskrá fyrir forritið þitt.

Sýnisyfirferðarforritið er skráin grader.cpp. Til að prófa forritið þitt skaltu setja grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h í sömu möppu og keyra eftirfarandi skipun til að þýða forritin þín.

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

Þegar þýðingin tekst verður keyranlega skráin grader búin til.

Athugið að raunverulega yfirferðarforritið er ólíkt sýnisyfirferðarforritinu. Sýnisyfirferðarforritið verður keyrt sem eitt ferli sem les inntaksgögn úr staðalinntaki og skrifar niðurstöðurnar í staðalúttak.

Inntak fyrir sýnisyfirferðarforritið

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

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

Úttak sýnisyfirferðarforritsins

Sýnisyfirferðarforritið skrifar eftirfarandi upplýsingar í staðalúttak (gæsalappir eru til skýringar).

• Ef forritið þitt er dæmt rétt skrifar það skilagildið $m$ úr fallinu Declare sem „Accepted: 2000“.
• Ef forritið þitt fær einhvern af dómunum Wrong Answer skrifar sýnisyfirferðarforritið tegundina sem „Wrong Answer [1]“.

Ef forritið þitt uppfyllir skilyrði fleiri en einnar tegundar af Wrong Answer tilkynnir sýnisyfirferðarforritið aðeins eina þeirra.

Þegar sýnisyfirferðarforritið er keyrt er rifflustokkunin fyrir hverja umferð reiknuð með gervitilviljunartölum. Niðurstöður þeirra breytast ekki milli keyrslna. Til að breyta fræi (seed) gervitilviljunartalnanna skaltu keyra sýnisyfirferðarforritið á eftirfarandi hátt.

./grader 2022

Fyrsta viðfangið á að vera heiltala.

Skorður

• $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$).

Undirverkefni

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

6. (60 stig) Engar viðbótarskorður. Fyrir þetta undirverkefni eru stigin þín reiknuð sem hér segir.

   • Látum $m^*$ vera hæsta gildi heiltalnanna $m$ sem Anna lýsir yfir í öllum prófunartilvikum þessa undirverkefnis.
   • Stigin þín eru sem hér segir.

Dæmi

Hér er sýnisinntak fyrir sýnisyfirferðarforritið og samsvarandi fallaköll.

Inntak 1

2
42
2000

Sýnisfallaköll

Í þessu sýnisinntaki eru $Q\ (=2)$ umferðir. Í umferð 1 gefur D-taro Önnu heiltöluna $A_1\ (=42)$. Í umferð 2 gefur D-taro Önnu heiltöluna $A_2\ (=2000)$.

Þetta sýnisinntak uppfyllir skorður allra undirverkefnanna.