BubbleRobots
Somewhere in space and time, the never-ending battle between the Good and the Evil is taking place. So far the Evil is winning on the eastern and northern front. The Good is retreating under heavy ionic fire and black hole grenades. Luckily, the Good stumbled upon an abandoned robot factory, the Good’s last and only hope…
Unfortunately, most of the robots the Good has found are rusty and broken. They are all out of function, sitting on a long straight assembly line. All robots have lasers that could be used either as a weapon or for communication with other robots. After quick inspection, it turns out that every robot can be repaired. Once a robot is repaired, it will repair and communicate with all robots within its laser scope. The repaired robots will in turn do the same. After two robots establish communication, the robot with smaller laser scope increases its scope to match the laser scope of the other robot. Robot’s laser scope can be increased more than once.
The goal is to repair enough robots for the Good to defeat the Evil (although this may not always be possible). Since repair is lengthy and energy consuming, the Good has time to manually repair only one initial robot. Also, some robots are more damaged than others meaning their repair is more energy consuming. To save energy, the Good needs to choose the least damaged robot which is capable of repairing enough robots to defeat the Evil.
Next n lines contain information about robots: each line contains three real numbers pi , di , ei , with 0 ≤ pi , di , ei ≤ 1000000000000 and with most one digit after decimal place, where pi is position , di is laser scope and ei is energy required to repair robot i manually.
Input:
3 2
1.2 10 5.3
5 1.54 1
13 10 3.14Output:
3.140000 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.