Spilaleikur einn, sem sagður er vera prófsteinn á greind, nefnist „Kang“. Í þessum leik hefur hvert spil stigagildi sem er jákvæð heiltala. Í upphafi færð þú $N$ spil í hendi, og að auki liggja $M$ spil á grúfu upp á borðinu í röð frá vinstri til hægri, þar sem þú sérð stig allra spilanna — bæði þeirra sem þú fékkst í hendi og þeirra sem liggja á borðinu. Síðan getur þú dregið fleiri spil af borðinu í $k$ umferðum, þar sem þú verður að draga eitt spil í einu í röð frá vinstri til hægri. Eftir að hafa dregið spil í hverri umferð getur þú kastað spilum úr hendi 1 sinni — hversu mörgum spilum sem er í hendi sem hafa sömu stig. Þú þarft að skipuleggja leik þinn þannig að eftir að hafa dregið spil af borðinu og kastað spilum úr hendi í fullar $k$ umferðir hafi spilin sem eftir eru í hendi sem minnsta heildarstigatölu.

Lítum á eftirfarandi dæmi:

Ef þú ert í upphafi með fimm spil með stigin $6, 3, 9, 6, 3$ og spilin sem liggja á borðinu hafa stigin $4, 6, 9, 6$ frá vinstri til hægri:

Tilfellið $k = 1$: Ef þú getur aðeins dregið 1 spil af borðinu, þá verða stig spilanna sem þú ert með $6, 3, 9, 6, 3, 4$ þegar þú dregur fyrsta spilið. Síðan getur þú valið að kasta spilum með sömu stig 1 sinni. Besta leiðin er að velja að kasta 2 spilum með stig jöfn $6$, þannig að heildarstig spilanna sem eftir eru verði sem minnst, eða $3 + 9 + 3 + 4 = 19$.

Tilfellið $k = 2$: Ef þú getur dregið 2 spil af borðinu er besta leiðin: eftir að hafa dregið fyrsta spilið með stig jöfn $4$ velur þú að kasta einu spili með stig jöfn $9$. Spilin sem eftir eru í hendi hafa stigin $6, 3, 6, 3, 4$. Síðan, þegar þú dregur 2. spilið með stig jöfn $6$, getur þú kastað 3 spilum með stig jöfn $6$, sem gerir það að verkum að spilin sem eftir eru hafa minnstu heildarstig sem jafngilda $3 + 3 + 4 = 10$.

Tilfellið $k = 3$: Ef þú getur dregið 3 spil af borðinu er besta leiðin: þegar þú dregur fyrsta spilið verða stig spilanna í hendi $6, 3, 9, 6, 3, 4$. Síðan getur þú valið spil með sömu stig til að kasta 1 sinni, og besta leiðin er að kasta báðum (2) spilunum með stig jöfn $3$, þannig að eftir í hendi verða spilin $6, 9, 6, 4$. Síðan, þegar þú dregur 2. spilið með stig jöfn $6$, getur þú kastað 3 spilum með stig jöfn $6$, þannig að í hendi verða spilin $9, 4$. Og þegar þú dregur í 3. sinn spil með stig jöfn $9$, getur þú kastað báðum (2) spilunum með stig jöfn $9$, sem gerir heildarstig spilanna sem eftir eru að $4$.

Tilfellið $k = 4$: Ef þú getur dregið 4 spil af borðinu er besta leiðin: eftir að hafa dregið fyrsta spilið með stig jöfn $4$, veldu að kasta einu spili með stig jöfn $4$, þannig að eftir í hendi verði spil með stigin $6, 3, 9, 6, 3$. Síðan í 2. drætti hefur spilið stig jöfn $6$; besta leiðin er að kasta báðum (2) spilunum með stig jöfn $3$, þannig að eftir í hendi verði $6, 9, 6, 6$. Í 3. drætti hefur spilið stig jöfn $9$; veldu að kasta báðum (2) spilunum með stig jöfn $9$. Og þegar síðasta spilið með stig jöfn $6$ er dregið getur þú kastað 4 spilum með stig jöfn $6$. Þetta kast leiðir til þess að engin spil verða eftir í hendi, sem þýðir að heildarstig spilanna eru $0$.

Verkefni þitt (Your Task)

Finndu „minnstu summu stiga spilanna sem eftir eru í hendi“ að loknum $k$ umferðum þegar $k = 1, 2, 3, \ldots, M$.

Þetta dæmi er með öðruvísi forritunarsniði en venjulega, sem verður notað í sjálfri keppninni. Vinsamlegast skoðaðu aftasta hluta þessa dæmis varðandi notkunarleiðbeiningar.

Útfærsluatriði

Þú þarft að skrifa eftirfarandi fall:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

með eftirfarandi stikum:

• $A$ er fylki af lengd $N$ sem tilgreinir númer spilanna í hendi í upphafi.
• $B$ er fylki af lengd $M$ sem tilgreinir númer spilanna sem liggja á borðinu, í röð frá vinstri til hægri.
• Fallið verður að skila fylki $C$ af lengd $M$ sem táknar minnstu mögulegu summu stiga spilanna í hendi eftir $k$ umferðir þegar $k = 1, 2, 3, \ldots, M$.

Til dæmis, ef $A = [6, 3, 9, 6, 3]$ og $B = [4, 6, 9, 6]$, þá verður fallið að skila fylkinu $[19, 10, 4, 0]$.

Skorður

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ fyrir hvert $i$ þar sem $1 \le i \le N$
• $1 \le B[i] \le 10^9$ fyrir hvert $i$ þar sem $1 \le i \le M$

Undirverkefni

Athugasemd

Leiðbeiningar um forritun

Í þessu dæmi er aðferðin við að skrifa forritið og senda það inn í yfirferðarkerfið (Grader) frábrugðin hinu almenna forritunarsniði þar sem keppandinn þarf að skrifa bæði lestur inntaks og útskrift úttaks. Í þessu dæmi þarf keppandinn aðeins að skrifa nauðsynlegan reiknihluta inni í tilgreinda fallinu. Inntaksgögnin verða aðgengileg í gegnum stika fallsins og niðurstöðum útreikninganna skal einnig skilað í gegnum fallið, án þess að keppandinn þurfi að skrifa lestur inntaks eða útskrift úttaks.

Keppandinn fær nokkrar skrár eins og lýst er hér að neðan; keppandinn þarf aðeins að breyta einni skrá eins og dæmið tilgreinir og senda þá skrá inn í kerfið:

• grader.cpp er aðalskráin sem sér um að lesa inntak og skrifa úttak.
• kang.cpp er skráin þar sem keppandinn þarf að skrifa útreikninga sína og er sú skrá sem keppandinn sendir inn í kerfið (í skránni kang.cpp má ekki vera fallið main(), en önnur föll eru leyfð).
• run_cpp.sh er skrá sem keppandinn getur keyrt til að keyra allt forritið.
• compile_cpp.sh er skrá sem keppandinn getur keyrt til að þýða (compile) forritið.

Keppandinn fær .zip skrá sem hægt er að hlaða niður úr kerfinu; þegar hún er afþjöppuð (extract) eru allar 4 skrárnar í henni. Keppandinn ætti að nota ritil (text editor) eða IDE til að breyta skránni kang.cpp og þýða eða keyra forritið með því að kalla á compile_cpp.sh eða run_cpp.sh.

Þegar keppandinn kallar á skrána run_cpp.sh til að keyra forritið mun forritið virka eins og tilgreint er í skránni grader.cpp, en kaflinn „Lýsing á grader-skránni“ útskýrir virkni þeirrar skrár.