Поиск фальшивых монет

문제

Это интерактивная задача.

Перед вами партия из $nn$ золотых монет, среди которых есть $kk$ фальшивых. Все монеты выложены в ряд. Предполагаемый вес $ii$-й монеты равен $ii$ грамм. Если монета фальшивая, ее вес равен $00$ грамм.

Монеты трогать запрещено и единственная доступная вам операция --- это выбрать некоторое $1\le p\le n1\; \backslash leq\; p\; \backslash leq\; n$ и взвесить первые $pp$ монет. В результате вам будет сказан настоящий суммарный вес этих монет.

Используя как можно меньше операций узнайте, какие $kk$ монет являются фальшивыми. Количество баллов будет зависеть от количество запросов, сделанных вашим решением, подробности смотрите в системе оценки.

힌트

В первой игре монеты $11$, $33$ являются фальшивыми. Таким образом, настоящие веса монет это $[0,2,0][0,\; 2,\; 0]$. С помощью одного запроса мы узнаем их суммарный вес $22$, после чего однозначно можно восстановить множество фальшивых монет.

Во второй игре монеты $2,6,8,102,\; 6,\; 8,\; 10$ являются фальшивыми. Таким образом, настоящие веса монет это $[1,0,3,4,5,0,7,0,9,0][1,\; 0,\; 3,\; 4,\; 5,\; 0,\; 7,\; 0,\; 9,\; 0]$. По ответам на запросы взвешивания можно однозначно восстановить множество фальшивых монет.