Under construction

Still being built. Things may change

AK47

Time limit4.7sMemory limit1024 MB

Summary
Find the two treasure zones among N zones in a row using at most 47 range queries, where a query reacts only when exactly one treasure lies in the range.
Level

Medium7 of 10

Topics
Binary search, Bit manipulation, Implementation
Solved
No attempts yet

문제

Gunshots ring out every night in a neighborhood where NN zones are lined up in a row. Two different zones hold treasure, and the rest have bombs installed. Isaac needs money to send his mother to a nursing home, so he decides to steal both treasures. Entering a zone with a bomb sets it off, so Isaac must pinpoint the exact two zones that hold the treasures.

The treasures react to screams. Grandma can make a scream whose sound reaches a contiguous range of zones in the row. A treasure reacts only when exactly one treasure lies within the range the sound reaches. If no treasure is there, nothing reacts and no reaction is felt. If both treasures are there, their reactions overlap and no reaction is felt.

Grandma can make at most 47 screams. Help Grandma so Isaac can steal both treasures.

Examples1

  1. Example 1

    Input
    1
10

X

O

X

X

O

X
    Expected output
    

AK 2 9

AK 1 4

AK 1 2

AK 3 3

AK 5 7

AK 5 6

! 4 7