VB 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 2P csapat küzd ebben a szakaszban, őket a 0 ... 2P - 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[2P-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.
|
|
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
|
Tesztadatok
Bemenetek
Kimenetek
