Egy műsorban guglerek (a Gugli cég alkalmazottjai) táncolnak. A tácosokat hárotagú zsüri értékeli, minden táncos három egész pontszámot kap, 0 és 10 között. A zsüri tagjainak eléggé hasonló az ízlése, ezért meglepő, ha egy táncos kapott két olyan pontszámot, amelyek különbsége 2. (Olyan soha nem történik, hogy 2-nél nagyobb lenne a különbség.) Pédául (8, 8, 8) és (7, 8, 7) nem meglepő, (6, 7, 8) és (6, 8, 8) meglepő, (7, 6, 9) pedig nem fordulhat elő. A gugler összpontszáma a három pontszám összege. A legjobb eredmény pedig a három pontszám maximuma. Az érdekel minket, hogy a guglerek összpontszámának ismeretében hány táncos legjobb eredménye lehet legalább p. Például legyen hat táncos, a következő összpontokkal: 29, 20, 8, 18, 18, 21. Tudjuk, hogy két meglapő eredmény volt. Szeretnénk tudni, hogy hány gugler legjobb eredménye érte el a 8 pontot. Lehettek volna például ezek a pontszámok: 10 9 10 6 6 8 (*) 2 3 3 6 6 6 6 6 6 6 7 8 (*) (*) jelöli a meglepő eredményeket. Ekkor három gugler ért el 8 vagy több pontot.
FeladatÍrjunk programot, ami a guglerek összpontszámának és a meglepő pontszámok számának ismeretében megadja, hogy hány táncos legjobb eredménye lehet legalább p.
BemenetAz első sorban a tesztesetek T száma van, ezután T eset következik. Minden teszteset egyetlen - szóközökkel elválasztott - sorból áll, és egész számokat tartalmaz. Az első szám N, a guglerek száma, a második S a meglepő eredmények száma, a harmadik p, a megadott küszöbérték. Ezután N darab ti egész következik, a guglerek összpontszáma.
KimenetMinden tesztesetre írjuk ki, hogy legfeljebb hány guglernek lehet a legjobb eredménye nagyobb vagy egyenlő, mint p. Méretek1 <= T <= 100 0 <= S <= N 0 <= p <= 10 0 <= ti <= 30 Legalább S a ti értékek közül 2 és 28 közé esik. Kis bemenet: 1 <= N <= 3, nagy bemenet: 1 <= N <= 100. Példa
Tesztadatoksmall.in large.in small.out large.out CímkékA feladat forrása: Google Code Jam 2012 Qualification Round
Algoritmusok: mohó algoritmus
megoldás |
Programozás > Feladatok >