PC összeszerelés
ACM, 2007, Észak-nyugat
Egy számítógépet szeretnénk részekből összerakni. Van rá valamennyi pénzünk, és szeretnénk a legjobb minőséget összehozni. Az összeszerelt gép minőségét a leggyengébb minőségű alkatrész határozza meg, ezt kell maximalizálnunk úgy, hogy ne lépjük túl az összeget, ami rendelkezésre áll.
Feladat
Írj programot, ami kiszámítja, mi a legjobb minőség, ami az adott pénzből elérhető! Minden alkatrész típusból pontosan egy kell a gépbe, és a gép minősége egyenlő a leggyengébb minőségű alkatrész minőségével. ("Leggyengébb láncszem.")
Bemenet
A bemenet elő sora a tesztesetek számát adja meg. Minden teszteset első sora két számot tartalmaz: a választható alkatrészek n számát (1 és 1000 között), továbbá a rendelkezésre álló pénzt (1 és 1000000000 között). Ezután n sorban a megvehető alkatrészek következnek "típus név ár minőség" formában. Az ár 1 és 1000000 közé esik a minőség 1 és 1000000000 közé. A típus és a név legfeljebb 20 hosszú karakterláncok, amelyek betűket, számjegyeket és aláhúzásjelet tartalmazhatnak.
Kimenet
A kimenet minden tesztesetre egy számot adjon meg, az összerakható legjobb minőségű PC minőségét.
Példa
Bemenet
1
18 800
processor 3500_MHz 66 5
processor 4200_MHz 103 7
processor 5000_MHz 156 9
processor 6000_MHz 219 12
memory 1_GB 35 3
memory 2_GB 88 6
memory 4_GB 170 12
mainbord all_onboard 52 10
harddisk 250_GB 54 10
harddisk 500_FB 99 12
casing midi 36 10
monitor 17_inch 157 5
monitor 19_inch 175 7
monitor 20_inch 210 9
monitor 22_inch 293 12
mouse cordless_optical 18 12
mouse microsoft 30 9
keyboard office 4 10
18 800
processor 3500_MHz 66 5
processor 4200_MHz 103 7
processor 5000_MHz 156 9
processor 6000_MHz 219 12
memory 1_GB 35 3
memory 2_GB 88 6
memory 4_GB 170 12
mainbord all_onboard 52 10
harddisk 250_GB 54 10
harddisk 500_FB 99 12
casing midi 36 10
monitor 17_inch 157 5
monitor 19_inch 175 7
monitor 20_inch 210 9
monitor 22_inch 293 12
mouse cordless_optical 18 12
mouse microsoft 30 9
keyboard office 4 10
Kimenet
Az előző bemenetre a válasz: 9