루미 알고리즘

#1540다이아Where's Waldo?

PO 2022 훈련 캠프코딩출제 Joakim Blikstad영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

There is a hidden permutation P_1,P_2,…,P_N of length N, which is guaranteed to be generated uniformly at random. The permutation contains the numbers 1, 2, 3, …, N exactly once each in some unknown order.

You can choose positions l and r, and ask queries of the form: “What is the sum of P_l + P_{l+1} + … + P_r”?

Your task is to find the position of the number 1 in P using as few queries as possible. You will score points based on how few queries you use.

Interaction

Your program should first read two integers on a line, T and N. T is the number of rounds your program will be run, and N is the length of P.

Then there will be T rounds:

When a round begins, you may start asking questions. Output a line with “? a b” to ask for the sum of the numbers between positions a and b (1 ≤ a ≤ b ≤ N).

After each query, your program should read an integer: the sum of the values in the interval.

Once you have found the position where the number 1 is located, output a line of the form “! i”, where i is the index such that P_i = 1. After you output this, the next round begins.

Make sure to flush the output after each query, otherwise you may get a Time Limit Exceeded. In C++, this can be done with, for example, cout << flush or fflush(stdout); in Python with stdout.flush(); and in Java with System.out.flush().

Scoring

Your program will be tested on a single test case, with N = T = 1000.

If any round gives the wrong answer, the submission will be judged as Wrong Answer.

Let M be the number of queries your program makes across all T rounds. You will receive min(100, 220 - M/2500) points. If you get negative points, it will count as zero.

In other words, if you use more than 550,000 queries, you get 0 points, and if you use 300,000 or fewer queries, you get 100 points. In between, the score increases linearly.

출처 표기

출처: Programmeringsolympiaden 2022년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.