Programozás‎ > ‎Feladatok‎ > ‎

Tánc a guglerekkel

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.

Bemenet

Az 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. 

Kimenet

Minden tesztesetre írjuk ki, hogy legfeljebb hány guglernek lehet a legjobb eredménye nagyobb vagy egyenlő, mint p.

Méretek

1 <= 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

Bemenet  Kimenet
4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21
Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3



Tesztadatok

small.in    large.in    small.out    large.out

Címkék

A feladat forrása: Google Code Jam 2012 Qualification Round
Algoritmusok: mohó algoritmus

megoldás