Anna og Bruno eru fornleifafræðingar. Þau eru að rannsaka rústir í Íran.

Verkefni þeirra eru eftirfarandi: Anna heimsækir rústir og uppgötvar fornminjar, en Bruno greinir niðurstöðurnar í grunnbúðunum.

Rannsókn þeirra er áætluð í $Q(=1\,000)$ daga. Á hverjum degi sendir Anna niðurstöðurnar til Brunos með samskiptatæki. Niðurstaða hvers dags er táknuð sem heiltala $X$.

Anna getur aðeins notað samskiptatækið einu sinni á dag. Það getur sent runu af lengd $N(=150)$ sem samanstendur af $0$ eða $1$.

Hins vegar var það bilað. Það eru nokkrir bilaðir staðir í rununni af lengd $N$. Á biluðum stað sendir það alltaf gildið $0$ óháð því gildi sem raunverulega var stillt. Þegar Anna sendir runu getur hún séð staðsetningar biluðu staðanna. En Bruno þekkir þær ekki. Staðsetningar biluðu staðanna og fjöldi þeirra getur breyst á hverjum degi.

Hætta er á að rannsókn þeirra tefjist. Þar sem þú ert kandídat í að taka þátt í alþjóðlegri forritunarkeppni í Íran biðja Anna og Bruno þig um að skrifa forrit sem sendir niðurstöður rannsóknar þeirra.

Verkefni

Skrifið tvö forrit sem sjá um samskiptin á milli Önnu og Brunos.

• Gefið lengd rununnar $N$, heiltöluna sem á að senda $X$, fjölda bilaðra staða $K$ og staðsetningar biluðu staðanna $P$, stillir fyrra forritið rununa $S$ sem Anna sendir.
• Gefið rununa $A$ sem Bruno móttekur, endurheimtir seinna forritið heiltöluna $X$.

Á stað þar sem samskiptatækið virkar hafa runan $S$ og runan $A$ sama gildi. Á biluðum stað hefur runan $A$ alltaf gildið $0$ óháð gildunum í rununni $S$.

Útfærsluatriði

Þú þarft að skila tveimur skrám sem skrifaðar eru í sama forritunarmáli.

Fyrri skráin er annaðhvort Anna.c eða Anna.cpp. Þessi skrá stillir runu sem Anna sendir og útfærir eftirfarandi fall. Forritið ætti að innihalda Annalib.h.

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

  Fyrir hvert prófunartilvik er kallað á þetta fall $Q=1\,000$ sinnum.

  • Stikinn N er lengd rununnar sem á að senda.
  • Stikinn X er heiltalan sem á að senda.
  • Stikinn K er fjöldi bilaðra staða.
  • Stikinn P[] er runa af lengd $K$ sem lýsir staðsetningum biluðu staðanna.

  Í fallinu Anna verður að kalla á eftirfarandi fall.

  • void Set( int pos, int bit )

    Þetta fall stillir bita í rununni $S$ sem samskiptatækið á að senda.

    • Stikinn pos er staðsetning staðarins sem á að stilla. pos verður að vera heiltala á milli $0$ og $N-1$, báðar meðtaldar. Athugið að staðsetningarnar eru taldar frá $0$. Ef kallað er á fallið með stika utan þessa bils telst forritið þitt vera Wrong Answer[1]. Ekki er leyfilegt að kalla á þetta fall oftar en einu sinni með sama stika pos. Ef kallað er á það oftar en einu sinni með sama stika telst forritið þitt vera Wrong Answer[2].
    • Stikinn bit er gildið sem stillt er í pos-ta sæti rununnar. Gildið á bit verður að vera annaðhvort $0$ eða $1$. Ef kallað er á fallið með öðrum stikum telst forritið þitt vera Wrong Answer[3].

  Kalla verður á fallið Set nákvæmlega $N$ sinnum í fallinu Anna. Þegar fallið Anna lýkur keyrslu, ef fjöldi skipta sem kallað var á fallið Set er annar en $N$, telst forritið þitt vera Wrong Answer[4].

  Forritið þitt er stöðvað ef fallakallið frá Önnu telst ógilt.

Seinni skráin er annaðhvort Bruno.c eða Bruno.cpp. Þessi skrá endurheimtir heiltöluna sem lýsir niðurstöðum rannsóknarinnar og útfærir eftirfarandi fall. Forritið ætti að innihalda Brunolib.h.

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

  Fyrir hvert prófunartilvik er kallað á þetta fall $Q=1\,000$ sinnum.

  • Stikinn N er lengd rununnar sem Bruno móttekur.
  • Stikinn A er heiltöluruna af lengd $N$. Þetta er runan sem Bruno móttekur.
  • Fallið Bruno verður að endurheimta gildið á $X$ og skila því.

Matsaðferð

Matið fer fram á eftirfarandi hátt. Ef forritið þitt telst vera Wrong Answer er það stöðvað samstundis.

1. Setja cnt = 0.
2. Kalla einu sinni á fallið Anna.
3. Látum $S$ vera rununa sem fallið Anna stillti. Í rununni $S$, setjum gildið $0$ í staðsetningarnar í $P$ og fáum þannig rununa $A$. Kalla einu sinni á fallið Bruno með stikann $A$.
4. Setja cnt = cnt +1. Ef $\mathrm{cnt}<Q$, fara í (2). Ef $\mathrm{cnt}=Q$, fara í (5).
5. Forritið þitt verður stigagjafað.

Mikilvægar tilkynningar

• Keyrslutími og minnisnotkun eru reiknuð fyrir liði (1), (2), (3), (4) í Matsaðferð.
• Forritið þitt má ekki teljast Wrong Answer í fallakallinu á Anna í (2) eða Bruno í (3). Forritið þitt verður að keyra án keyrsluvillu (runtime error).
• Forritið þitt getur útfært önnur föll til innri nota eða notað víðværar breytur. Innsend forrit verða þýdd (compiled) saman við prófarann (grader) og verða að einni keyranlegri skrá. Allar víðværar breytur og innri föll ættu að vera skilgreind sem static til að forðast árekstra við aðrar skrár. Þar sem forrit Önnu og Brunos verða keyrð sem 2 aðskilin ferli þegar þau eru metin geta þau ekki deilt víðværum breytum.
• Í ferlinu er kallað á hvort fallanna Anna og Bruno $Q=1\,000$ sinnum. Breytur sem forritin þín nota ættu að vera upphafsstilltar á viðeigandi hátt.
• Forritið þitt ætti ekki að nota staðalinntak og staðalúttak. Forritið þitt ætti ekki að eiga samskipti við aðrar skrár með neinum hætti.

Þýðing og prófunarkeyrsla

Þú getur halað niður safnskrá af vefsíðu keppninnar sem inniheldur sýnisprófara (sample grader) til að prófa forritið þitt. Safnskráin inniheldur einnig sýniskóðaskrá fyrir forritið þitt.

Sýnisprófari samanstendur af einni frumkóðaskrá sem er annaðhvort grader.c eða grader.cpp. Til dæmis, ef forritin þín eru Anna.c og Bruno.c, eða Anna.cpp og Bruno.cpp, keyrir þú eftirfarandi skipanir til að þýða forritin þín.

• 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

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

Athugið að raunverulegi prófarinn er ólíkur sýnisprófaranum. Sýnisprófarinn verður keyrður sem eitt ferli sem les inntaksgögn af staðalinntaki og skrifar niðurstöðurnar á staðalúttak.

Inntak fyrir sýnisprófarann

Sýnisprófarinn les eftirfarandi gögn af staðalinntaki.

• Fyrsta línan inniheldur heiltölu $Q$.
• Síðan eru gefnar upplýsingar um $Q$ fyrirspurnir.

• Upplýsingar um hverja fyrirspurn samanstanda af tveimur línum sem hér segir.

  • Fyrri línan inniheldur þrjár heiltölur $N$, $X$, $K$ aðskildar með bili. Þetta þýðir að lengd rununnar sem á að senda er $N$, heiltalan sem Anna á að senda er $X$ og það eru $K$ bilaðir staðir.
  • Seinni línan inniheldur $K$ heiltölur $P_0,P_1,\cdots,P_{K-1}$ aðskildar með bili. Þetta þýðir að fyrir hvert $i$ ($0\le i\le K-1$) er $P_i$-ti staðurinn í rununni bilaður.

Úttak sýnisprófarans

Þegar forritið lýkur keyrslu með eðlilegum hætti skrifar sýnisprófarinn eftirfarandi upplýsingar á staðalúttak. (Gæsalappirnar eru ekki skrifaðar í raun.)

• Ef forritið þitt telst vera Wrong Answer skrifar sýnisprófarinn tegund þess á eftirfarandi formi “Wrong Answer [1],” og forritið þitt er stöðvað.
• Ef ekkert fallakall á Anna telst vera Wrong Answer skrifar sýnisprófarinn “Accepted” og gildið á $L^*$. Fyrir gildið á $L^*$, sjá Undirverkefni.

Ef forritið þitt fellur undir margar tegundir af Wrong Answer tilkynnir sýnisprófarinn aðeins eina þeirra.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

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

Undirverkefni

• Látum $L^*$ vera lágmark eftirfarandi gildis yfir öll prófunartilvik þessa verkefnis.

  • Stærsta heiltalan $L\le40$ þannig að fyrir sérhverja fyrirspurn með $K\le L$ svarar Bruno réttu gildi á $X$.

• Stigafjöldi þessa verkefnis er reiknaður á eftirfarandi hátt:

  • Ef $L^*=0$, eru stigin 0 stig.
  • Ef $1\le L^*\le14$, eru stigin 8 stig.
  • Ef $15\le L^*\le37$, eru stigin $(L^*-15)\times2+41$ stig.
  • Ef $38\le L^*\le40$, eru stigin $(L^*-38)\times5+90$ stig.

Dæmi

Hér er sýnisinntak fyrir prófarann og samsvarandi fallaköll. Athugið að eftirfarandi dæmi uppfyllir ekki takmarkanir þessa verkefnis vegna þess að $Q=2$, $N=3$.

Inntak 1

2
3 14 1
2
3 9 2
0 1

Sýnisköll

Hér eru stikarnir fyrir Anna(...), Bruno(...), Anna(...), Bruno(...) sem hér segir.