루미 알고리즘

#1640플래티넘Strawberries

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

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

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Mikaela has harvested the first strawberries in all of Sweden, and wants to sell them for a high price. But in order to legally sell strawberries, she must first weigh them. Unfortunately, Mikaela doesn't own a scale of any kind. The only tool she has that is up for this job is a vacuum cleaner.

There are N strawberries, where the ith one has weight w_i. The strawberries are sorted by weight, so

w_1 ≤ w_2 ≤ … ≤ w_N.

All weights are integers between 1 and M, where M ≤ N. You can make queries of the form

  • ? i s: You set the strength of the vacuum cleaner to s, and use it on the strawberry with index i. If w_i ≤ s, then the strawberry gets sucked up by the vacuum cleaner and is lost. Otherwise, the strawberry remains.

The goal is to find the weights of all of the strawberries that did not get lost, while also losing at most M-1 strawberries. In addition, in order to get full score you must use at most 300 queries.

Note that you should not find the weights of the lost strawberries. Once a strawberry is lost, no more queries can be performed on it, but it still keeps its position in the list.

Interaction

This is an interactive problem.

• Your program should first read one line containing the integers N and M (2 ≤ M ≤ N ≤ 300).

• Then, your program starts interacting with the grader. In order to make a query, print two integers i and s, on the format ? i s. These two integers must satisfy 1 ≤ i ≤ N and 1 ≤ s ≤ M.

After that, read one line containing a string, the answer to your query. This string is either borta (lost) or kvar (remaining), which indicates that strawberry i was lost or remained.

If you try to print a query that doesn't follow the format, or try to query a strawberry that was already lost earlier, then you will get Wrong Answer.

• When you are ready to report the weights of all the remaining berries, print one line on the format ! w1 w2 w3 ... wN. The weights of lost berries should be printed as -1, otherwise you will get Wrong Answer.

If you use more than 10^5 queries, you get Wrong Answer. If more than M-1 strawberries are lost, you get Wrong Answer. Reporting the final answer does not count as a query.

The grader is not adaptive. This means that the list of weights w_1, w_2, …, w_N is fixed before the interaction starts.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

For every test group, you will get 50% of the score if your program uses between 301 and 10^5 queries. If you use at most 300 queries, you get full score for that test group.

GroupPointsConstraints
116M = 2
230M = N
354No additional constraints.

Explanation of Sample

In the first query, we use the vacuum cleaner on berry 2, with s = 1. The berry gets lost. Then, we use the vacuum cleaner on the last berry, with s = 2. The last berry remains.

Finally, we report the answer that w_1 = 1 and w_3 = 3. Note that we print -1 for the weight of berry 2 because it got lost, even though we know that it must have had weight 1.

Since M = 3 in this case, we can afford to lose at most M-1 = 2 berries. We only lost one berry, so this counts as Accepted.

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.