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
2004-2016 BDG algoritmus szakkör