This page is still under construction.

Parts of this page are still being built. What you see may change.

Hotter-colder

Time limit1sMemory limit256 MB

Summary
An interactive problem: locate a hidden point in a d-dimensional integer grid using at most 100d queries that only report whether the latest Chebyshev distance got smaller or larger.
Level

Hard8 of 10

Topics
Binary search, Implementation, Math, Geometry
Solved
No attempts yet

Problem

This is an interactive task.

Small Tuple and her brother Kortesh live happily in their dd-dimensional world. Today they came up with an idea to play hide-and-seek, and Kortesh will be the first seeker. As finding people in large-dimensional worlds is usually quite a difficult task, they decided to use their walkie-talkies for communication. Moreover, each of them took their GPS receivers.

Tuple hid in one of the points of the Hypercube Forest and is not going to move until Kortesh finds him. The forest is a hypercube with its side equal to rr; it contains all dd-dimensional points whose coordinates are integers from [0,r][0, r]. Kortesh walks round the forest and once in a time uses his walkie-talkie and tells Tuple his current location. Then, Tuple responds with a single word: hotter if Kortesh came closer to Tuple since their last (i.e., the most recent) communication, or colder otherwise.

Given dd-dimensional points p,x,yp, x, y, Tuple says that xx is closer to pp than yy if [ \max_{i = 1, 2, \ldots, d} |x_i - p_i| < \max_{i = 1, 2, \ldots, d} |y_i - p_i|. ]

Unfortunately, Kortesh forgot to charge his walkie-talkie and the battery will allow him only for 100d100d communications. Help him find his sister before he loses the ability to contact her.

Examples1

  1. Example 1

    Input
    2 2
    ? 2 2
    ? 0 0
    ? 1 1
    ? 2 2
    ! 2 2
    
    Expected output
    colder
    colder
    hotter
    hotter