VB2010 (Megoldás)
Címkék > Feladat

VB 2010

Forrás: Google Code Jam 2010

Vili a focivébé kiesés szakaszára érkezett meg Dél-Afrikába.

A kiesése szakaszban minden meccsen születik egy győztes, aki továbbjut, és egy vesztes, akik kiesik. Összesen 2^P csapat küzd ebben a szakaszban, őket a 0 ... 2^P - 1 számokkal azonosítjuk. A kieséses szakasz P fordulóból áll. Minden fordulóban minden bent maradt csapat pontosan egy meccset játszik. A párosítás az azonosítók szerint történik: a megmaradt csapatok közül a két legkisebb azonosítójú fog egymás ellen játszani, stb. Egy forduló összes meccsét le kell játszani, és csak utána kezdődhet a következő forduló.

Feladat

Segítsünk megtervezni Vilinek, melyik meccseket nézze meg. Ehhez Vili megadott egy listát, hogy melyik csapatot mennyire szereti. Pontosabban minden i csapathoz megadta, hogy ennek a csapatnak legfeljebb M[i] mérkőzéséről akar lemaradni.

Vili úgy akarja -- előre -- megvenni a jegyeket, hogy a későbbi eredményektől függetlenül teljesüljenek feltételei. Ezen felül szeretné a legolcsóbban megúszni a jegyvásárlást. Határozzuk meg, mennyi az a legkevesebb pénz, amiből teljesíthetők Vili elvárásai.

A jegyeket előre kell megvenni (még a vébé kezdete előtt), és előre ismert minden meccsre a jegy ára. A kis bemenetekben azonosak a jegyárak, a nagy bemeneteknél különbözhetnek.

Bemenet

Az első sorban a tesztesetek T száma van. Ezután T blokk következik, a tesztesetek. Minden tesztesethez megadjuk a fordulók P számát, a következő sorban az M[0], ..., M[2^P-1] feltételeket..

Ezután P sorban a megfelelő mérkőzések jegyára következik. (Az utolsó sorban egyetlen szám áll, a döntő jegyára.)

Kimenet

Minden kimeneti sor a minimálisan elköltendő összeget tartalmazza a megfelelő bemenethez.

Méretek

1 ≤ T ≤ 50
1 ≤ P ≤ 10
M minden eleme 0 és P közötti egész.

Kis bemenet

Minden jegyár 1.

Nagy bemenet

A jegyár 0 és 100000 közötti egész.

Példa

Tartozzon a korábbi ábrán látható jegyárakhozu, az alábbi táblázatban is megadott M = {1, 2, 3, 2, 1, 0, 1, 3} feltétel-halmaz. Az optimális stratégia a következő: mivel az 5-ös csapat egyetlen meccsét sem mulaszthatjuk el, megvesszük a jegyet 50, 400 és 800 áron (az 5-ös lehetséges meccseinek ára). Most a 0-ás kivételével minden további csapatra teljesülnek a feltételek. Legolcsóbb végül a 0-ás csapat 1. fordulós meccsére venni még jegyet 100 pénzért, így végül 1350 pénzt költöttünk a feltételeknek megfelelő jegyvásárlásra.

Input	Output
`2 2 1 1 0 1 1 1 1 3 1 2 3 2 1 0 1 3 100 150 50 90 500 400 800`	`Case #1: 2 Case #2: 1350`