NézetNyomtat

Pingvinek menetelése
Címkék > Feladat

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 $)

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

Tesztadatok