Pingvinek menetelése
ACM, 2007, Észak-nyugat
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\le x, y \le 10000, 0\le db \le 10, 1 \le m \le 200 $)
($-10000\le x, y \le 10000, 0\le db \le 10, 1 \le m \le 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
| pingvin.be | pingvin.ki |
|
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 |