svemir
Time limit1sMemory limit512 MB
Find an unknown cube in an N by N by N grid using at most 200 distance-comparison queries, each telling whether a move brought the ship closer to or farther from the target.
- Level
Medium6 of 10
- Topics
- Binary search, Geometry, Implementation, Brute force
- Solved
- No attempts yet
Problem
A space shuttle has lost its black box somewhere in the universe, and the crew is trying to find it as soon as possible.
The signal emitted by the box is not strong enough to determine its exact position. However, when the spaceship moves, the instruments can tell whether the signal from the box is now stronger or weaker than before, so the crew knows whether the spaceship is now closer to or further from the box.
The universe is a three-dimensional space consisting of NxNxN small cubes. Each cube is represented by three coordinates, all of which are positive integers less than or equal to N.
At the beginning, the spaceship is located in the cube (1,1,1), and the black box is at a different, unknown location.
Write a program that finds the black box (that is, moves the spaceship to the exact position of the black box) with at most 200 calls to the function Pomak.
Constraints
- 2 ≤ N ≤ 1,000,000,000