ŠIOM — Game

Laiko ribojimas: 3s

Atminties ribojimas: 256MB

Duomenų failas: ejoi_2017_game.in

Rezultatų failas: ejoi_2017_game.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Game

Alisa ir Bobas žaidžia tokį žaidimą: Duota sveikųjų teigiamų skaičių seka, sudaryta iš N skaičių ir visi skaičiai joje yra mažesni arba lygūs N. Sekos elementai sunumeruoti nuo 1 iki N. Sekoje gali būti sutampančių skaičių. Žaidimo pradžioje sudaroma aibė S, į kurią įtraukiami pirmieji P sekos narių. Atkreipkite dėmesį, kad S gali būti ir multi-aibė, t. y. joje gali būti sutampančių elementų.
Žaidėjai ėjimus atlieka paeiliui, o pirmoji pradeda Alisa. Pradiniu momentu abu žaidėjai turi po 0 taškų.
Ėjimai atliekami taip:

Žaidėjas, kurio eilė atlikti ėjimą, parenka vieną skaičių iš aibės S, jį prideda prie savo taškų skaičiaus ir išima iš aibės.
Kairiausias nepanaudotas sekos narys, jei toks yra, įdedamas į aibę S. Kitaip sakant pirmuoju ėjimu į aibę įtraukiamas (P+1)-asis sekos narys, antruoju ėjimu įtraukiamas (P+2)-asis sekos narys ir t.t. Jei visi sekos nariai jau buvo panaudoti aibėje šis punktas praleidžiamas.

Žaidimas tęsiamas, kol aibė S tampa tuščia. Laikykime, kad abu žaidėja žaidžia optimaliai, t. y. daro geriausius įmanomus ėjimus, kad surinktų daugiausiai taškų. Žaidimo rezultatas gaunamas iš Bobo surinktų taškų atėmus Alisos surinktus taškus.

Užduotis

Parašykite programą, kuri duotai N skaičių sekai sužaistų K skirtingų žaidimų. Skirtinguose žaidimuose skiriasi pradinis sekos narių skaičius aibėje.

Pradiniai duomenys

Iš pirmosios standartinės įvesties eilutės perskaitomi du tarpu atskirti sveikieji teigiami skaičiai N ir K. Antrojoje eilutėje pateikiama žaidimui reikalinga seka: N tarpais atskirtų sveikųjų teigiamų skaičių $a_1,a_2,\\dots,a_N$ . Trečiojoje eilutėje pateikiama K sveikųjų teigiamų tarpais atskirtų skaičių $p_1,p_2,\\dots,p_K$ . Kiekvienas šių skaičių nusako i-tąjį žaidimą (čia i = 1, 2, ..., K). Skaičius pi reiškia, kad žaidžiant žaidimą i-ąjį kartą žaidimo pradžioje į aibę bus įtraukiami pirmieji $p_i$ sekos narių.

Rezultatai

Į standartinį išvedimą programa turi išvesti K eilučių ir kiekvienoje eilutėje turi būti po vieną sveikąjį skaičių – atitinkamo žaidimo rezultatą. I-ojoje eilutėje turi būti įrašytas i-ojo žaidimo rezultatas. Žaidimai pradiniuose duomenys sunumeruoti nuo 1 iki K.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
5 2 2 4 2 3 5 4 3	2 6

Ribojimai

$1\\leqN\\leq100000$
$1\\leqK\\leq2000$
$K\\leqN$
$1\\leqa_i\\leqN$ visiems i = 1, 2, …,N
$1\\leqp_i\\leqN$ visiems i = 1, 2, …,K