아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Архивы джедаев

시간 제한2초메모리 제한512 MB

요약
10^18개의 칸이 원형으로 놓인 제다이 기록보관소에서 일부 행성이 삭제되고 나머지가 회전해 다시 번호가 매겨졌다. 칸을 최대 10번 확인해 행성 x의 정보가 든 칸을 찾는다.
난이도

보통10점 중 7점

유형
이분 탐색, 구현, 수학
정답자
아직 제출이 없습니다

문제

В Далёкой-Далёкой Галактике 101810^{18} планет, и все они пронумерованы натуральными числами от 11 до 101810^{18}.

В Архивах джедаев были сохранены сведения о всех планетах Галактики: по кругу в огромном зале были расположены ячейки, пронумерованные против часовой стрелки от 1 до 101810^{18}. Исходно Архивы были устроены очень просто: в ячейке с номером ii хранились сведения о планете с номером ii. Поэтому, зная лишь номер планеты, всегда можно было легко найти информацию о ней.

Вот и Оби-Вану Кеноби понадобилось узнать координаты планеты Камино, которая имеет номер xx. Однако, заглянув в Архивы, он с удивлением обнаружил, что кто-то удалил из Архивов mm ячеек со сведениями о некоторых планетах. Кроме того, оставшиеся ячейки были заново пронумерованы, начиная с 11, против часовой стрелки (возможно, начиная не с той, с которой они нумеровались исходно), и теперь в ячейке с номером ii могут храниться сведения о совсем другой планете.

Оби-Ван в затруднении. Ему нужно срочно найти данные о планете Камино. Оби-Ван может проверить содержимое ячейки и узнать, данные о какой планете в ней находятся. У Оби-Вана мало времени, поэтому он может проверить содержимое не более чем десяти ячеек.

Помогите ему выяснить, в какой ячейке находятся данные о планете Камино, если, конечно, они не были удалены из Архивов.

힌트

В примере из Архива были удалены данные о планетах с номерами 1111, 1414 и 1515, а ячейки были перенумерованы, начиная с ячейки, содержащей сведения о планете с номером 1010.

예제1

  1. 예제 1

    입력
    16 3
    
    10
    
    12
    
    13
    
    16
    
    
    예상 출력
    
    ? 1
    
    ? 2
    
    ? 3
    
    ? 4
    
    ! 4