시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB109000.000%

문제

This is an interactive problem!

Hora is a traditional Romanian and Moldovan folk dance in which participants join hands and form a large circle...

At the 8th European Junior Olympiad in Informatics, $N$ participants started dancing hora, where $N$ is a positive, even integer. The number of boys is equal to the number of girls. The organizers assigned a circular index to every participant in the hora. The indexes start from $0$ and continue consecutively in increments of $1$, up to $N - 1$. This means that participants with indexes $0$ and $N - 1$ are neighbors, and that each participant’s index is one greater than that of their previous neighbor. Please refer to the Examples section for visualizing such a configuration.

You don't know exactly which participants are girls and which participants are boys, since you are participating in the competition right now! However, you can make calls to the testing system. Each call consists of two integers $L$ and $R$ such that $0 ≤ L < N$ and $0 ≤ R < N$. The response will contain an integer - the number of boys on the continuous circular interval from $L$ to $R$ in our circle. In particular:

  • If $L ≤ R$, then the answer will consider the continuous circular interval of participants with indexes $L,L + 1, \dots ,R - 1,R$.
  • If $R < L$, then the answer will consider the continuous circular interval of participants with indexes $L,L + 1…N - 1, 0, \dots , R - 1,R$.

You are given an integer $K$ ($1 ≤ K ≤ N$). Your task is to find a continuous circular interval of length $K$ in our circle for which the absolute difference between the number of boys and girls is as small as possible. More formally, you are asked to implement a procedure that returns an integer $S$ ($0 ≤ S < N$) such that a continuous circular interval of length $K$ starting from $S$ has the smallest absolute difference between the number of boys and the number of girls among all the possible continuous circular intervals of length $K$. Note that a certain circle configuration may have multiple solutions with the same smallest absolute difference between the number of boys and girls. In such a case, you may return any of them.

The absolute difference between two numbers $x$ and $y$ is given by $|x - y|$. For example, $|2 - 4| = 2$, $|7 - 4| = 3$.

구현 상세

You should implement the following procedure:

int solve(int N, int K)
  • $N$: the number of participants in the hora.
  • $K$: the length of the considered interval.
  • This procedure should return $S$, the integer representing the beginning of the interval of length $K$ with the smallest absolute difference between the number of boys and the number of girls dancing in the hora.
  • This procedure is called exactly once.

The above procedure can make calls to the following procedure:

int ask(int L, int R)
  • $L$: the start index of the queried interval.
  • $R$: the end index of the queried interval.
  • Returns the number of boys in the queried interval.
  • If the number of calls to the ask procedure exceeds $10^5$, the solution will receive a Wrong Answer verdict.

예제

Let's assume that the circle looks as follows:

Note that the circles with the white letter B on them represent boys, and the circles with the black letter G on them represent girls. Additionally, the number immediately to the right of each circle represents the index of the corresponding person.

Consider the following call:

solve(12, 5)

In this example, we have $12$ people dancing hora, and we search for the continuous interval of length $5$ with the minimal possible absolute difference between the number of boys and the number of girls. Our program makes a call:

ask(0, 10)

The corresponding answer is $6$, meaning that there are $6$ boys dancing hora in this interval. We can easily deduce from this that there are $5$ girls dancing hora in the same interval.

ask(0, 4)

The corresponding answer is $4$, meaning that there are $4$ boys dancing hora in this interval.

ask(1, 5)

The corresponding answer is $3$, meaning that there are $3$ boys dancing hora in this interval. We can easily deduce that there are $2$ girls dancing hora in the same interval. Since the absolute difference between $3$ and $2$ is $1$, and there can't exist an interval with a smaller absolute difference of length $5$, your program returns $1$, which is the start of this corresponding interval.

제한

  • $2 ≤ N ≤ 10^5$
  • $1 ≤ K ≤ N$
  • $N$ is even.
  • The hora has an equal number of participating boys and girls.
  • The grader is not adaptive.

서브태스크

Subtask Score Limits $Q_{full}$
1 5 $N = 34$ $34$
2 13 $N = 100\,000$, all the boys are adjacent to each other (all the girls are adjacent to each other as well). $18$
3 8 $N = 100\,000$, the configuration of the hora was generated randomly. $34$
4 11 $N = 100\,000$, $K = 50\,000$ $18$
5 10 $N = 65\,536$, $K = 128$ $26$
6 10 $N = 100\,000$, $K = 400$ $26$
7 9 $N = 100\,000$, $K = 99\,601$ $26$
8 10 $N = 100\,000$, $K = 330$ $68$
9 24 Mixed values for $N$ and $K$ (no additional constraints). $34$

Take a test in a group with parameter $Q_{full}$ and Score. Let $Q$ be the number of calls to the ask procedure for that test. If $Q ≤ Q_{full}$ you get awarded Score points for that test. If $N ≥ Q > Q_{full}$ you will get awarded Score $\cdot \left( 1 - \left( \frac{ \left( Q - Q_{full} \right) }{N} \right)^{0.05} \right)$. If $Q > N$ or the answer of your program for that test is wrong you will get awarded $0$ points for that test. The score for the group is then the minimum score among all of its tests.

Calling the ask procedure more than $10^5$ times will result in a Wrong Answer verdict.

샘플 그레이더

The sample grader reads the input in the following format:

  • line $1$: $N$, $K$
  • line $2$: $A[0], A[1], \dots ,A[N - 1]$, where the array $A$ is a string representing our hidden circle of participants. In particular, if $A[i] = $'X', the corresponding person in our circle is a boy, and if $A[i] = $'Y', the corresponding person in our circle a girl.

The sample grader outputs each question in the following format:

  • line $1$: ? $L$ $R$

The sample grader outputs each answer in the following format:

  • line $1$: $x$ boys

The sample grader outputs the contestant's answer in the following format:

  • line $1$: ! $S$

At the end of the interaction, in the last line of the standard output the grader reports the number of calls to the ask procedure made by the contestant.

제출할 수 있는 언어

C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.