Programozás‎ > ‎Feladatok‎ > ‎

Pingvinek menetelése

A pingvinek társas lények, ezért szeretnek egy jégtáblán gyülekezni. Nem szeretnének vizesek lenni, ezért korlátozott hosszúságú ugrásaik segítségével közlekednek a jégtáblák között. Sajnos a globális felmelegedés miatt a jégtáblák repedeznek, a pingvinek tudják, hányszor szabad elugrani egy jégtábláról, mielőtt darabokra reped és elsüllyed. Az nem rongálja a jégtáblát, amikor a pingvin "ráérkezik", csak az, amikor elugrik róla.
 

Feladat

Írj programot, ami megadja, hogy melyik jégtáblákon találkozhatnak a pingvinek!

Bemenet

Az első sor a tesztesetek száma. Ezután minden teszteset a következőket tartalmazza: Egy sorban N (a jégtáblák száma, max 100) és D (a maximális ugrási távolság, valós, legfeljebb 100000). Ezután N sorban a jégtáblák leírása "x y db m" alakban, ahol x és y a jégtábla koordinátái, 0-tól kezdve, db a kezdetben a jégtáblán lévő pingvinek száma, m pedig az az érték, ahányadik elrugaszkodás után elsüllyed a jégtábla. (-10000≤x,y≤10000,0≤db≤10,1≤m≤200)

Kimenet

Minden tesztesethez azon jégtáblák (0-tól kezdődően indexelt) sorszámát kell megadni, ahol találkozhatnak a pingvinek. Ha nincs ilyen jégtábla, akkor egy -1 szerepeljen a kiment megfelelő sorában.

Példa

Bemenet  Kimenet
2
5 3.5
1 1 1 1
2 3 0 1
3 5 1 1
5 1 1 1
5 4 0 1
3 1.1
-1 0 5 10
0 0 3 9
2 0 1 1
1 2 4
-1



Tesztadatok

Címkék

A feladat forrása: ACM, 2007, Észak-nyugat
Algoritmusok: maximális folyam meghatározása

megoldás