1093 - March of the Penguins
Time Limit : 30 Second
Memory Limit : 128 MB
Submission: 17
Solved: 8
- Description
- Somewhere near the south pole, a number of penguins are standing on a number of ice
floes. Being social animals, the penguins would like to get together, all on the same floe. The
penguins do not want to get wet, so they have use their limited jump distance to get together
by jumping from piece to piece. However, temperatures have been high lately, and the floes
are showing cracks, and they get damaged further by the force needed to jump to another
floe. Fortunately the penguins are real experts on cracking ice floes, and know exactly how
many times a penguin can jump off each floe before it disintegrates and disappears. Landing
on an ice floe does not damage it. You have to help the penguins find all floes where they
can meet.
- Input
- On the first line one positive number: the number of testcases, at most 100. After that per
testcase:
• One line with the integer N (1 <= N <= 100) and a floating-point number D (0 <= D <= 100 000), denoting the number of ice pieces and the maximum distance a penguin can
jump.
• N lines, each line containing xi, yi, ni and mi, denoting for each ice piece its X and Y
coordinate, the number of penguins on it and the maximum number of times a penguin
can jump off this piece before it disappears (−10 000 <= xi, yi <= 10 000, 0 <= ni <= 10,
1 <= mi <= 200).
- Output
- Per testcase:
• One line containing a space-separated list of 0-based indices of the pieces on which all
penguins can meet. If no such piece exists, output a line with the single number −1. - sample input
-
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
- sample output
-
1 2 4 -1
- hint
- source
- The 2007 ACM Northwestern European Programming Contest