Задача №115256. Поиск фальшивых монет
Это интерактивная задача.
Перед вами партия из \(n\) золотых монет, среди которых есть \(k\) фальшивых. Все монеты выложены в ряд. Предполагаемый вес \(i\)-й монеты равен \(i\) грамм. Если монета фальшивая, ее вес равен \(0\) грамм.
Монеты трогать запрещено и единственная доступная вам операция — это выбрать некоторое \(1 \leq p \leq n\) и взвесить первые \(p\) монет. В результате вам будет сказан настоящий суммарный вес этих монет.
Используя как можно меньше операций узнайте, какие \(k\) монет являются фальшивыми. Количество баллов будет зависеть от количество запросов, сделанных вашим решением, подробности смотрите в системе оценки.
Каждый тест состоит из \(t\) игр, в которых вы должны узнать, какие монеты фальшивые. В самой первой строке находится единственное целое число \(t\) (\(1 \leq t \leq 50\)) — количество игр. Каждая игра состоит из взаимодействия в описанном ниже формате. После окончания всех игр, ваша программа должна завершиться.
В начале каждой игры вам дается два целых числа \(n\) и \(k\) (\(1 \leq n \leq 10^9\), \(1 \leq k \leq \min{(100, n)}\)). После этого вы можете сделать несколько запросов взвешивания.
Для того чтобы сделать запрос взвешивания выведите « \(? \, p\) ». В результате вам будет возвращено единственное целое число \(a\). Если \(a = -1\), ваша программа превысила допустимый лимит запросов взвешивания на игру и должна немедленно завершиться. На каждую игру разрешено сделать не более \(3500\) запросов взвешивания. Иначе \(a \geq 0\) это настоящий суммарный вес монет \(1, 2, \ldots, p\).
Для того чтобы сказать угаданное множество, выведите « \(! \, i_1 \, i_2 \, \ldots \, i_k\) », где \(1 \leq i_1, i_2, \ldots, i_k \leq n\) это различные индексы фальшивых монет в произвольном порядке. В результате вам будет возвращено единственное целое число \(a\). Если \(a = -1\), то ваш ответ неправильный и ваша программа должна немедленно завершиться. Иначе \(a = 1\), и ваша программа должна продолжить взаимодействие следующей игрой или завершиться, если это была последняя игра.
Обратите внимание, что интерактор играет адаптивно . Не гарантируется, что множество фальшивых монет зафиксировано до начала игры. Единственное что гарантируется — в любой момент времени ответы, которые были даны в течение игры, соответствуют хотя бы одному множеству фальшивых монет. Ваш ответ на игру является правильным, если он соответствует всем ответам на запросы, данным в течение игры, а также не существует ни одного другого множества фальшивых монет, которое соответствует всем ответам.
После вывода каждого действия вашей программы выводите перевод строки. После вывода каждого действия вашей программы делайте сброс потока вывода.
Если вы используете « writeln » в Паскале, « cout « ... « endl » в C++, « System.out.println » в Java, « print » в Python, « Console.WriteLine » в C#, то сброс потока вывода у вас происходит автоматически, дополнительно ничего делать не требуется. Если вы используете другой способ вывода, рекомендуется делать сброс потока вывода. Обратите внимание, что перевод строки надо выводить в любом случае.
В первой игре монеты \(1\), \(3\) являются фальшивыми. Таким образом, настоящие веса монет это \([0, 2, 0]\). С помощью одного запроса мы узнаем их суммарный вес \(2\), после чего однозначно можно восстановить множество фальшивых монет.
Во второй игре монеты \(2, 6, 8, 10\) являются фальшивыми. Таким образом, настоящие веса монет это \([1, 0, 3, 4, 5, 0, 7, 0, 9, 0]\). По ответам на запросы взвешивания можно однозначно восстановить множество фальшивых монет.
Тесты к этой задаче состоят из 6 групп. Пусть \(q\) это количество запросов взвешивания, которое сделало решение в ходе одной игры.
Баллы за первые 5 групп ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Для каждой из первых 5 групп зафиксировано некоторое число \(maxQ\). Тест в первых 5 группах считается пройденным, если \(q \le maxQ\).
Балл за каждую игру в последней группе равняется \(min\left(50, \left\lfloor 50 \sqrt{\frac{k + 30}{q}} \right\rfloor\right)\). Общее количество баллов за тест равняется минимальному количеству баллов за все игры. Общее количество баллов за последнюю группу равняется минимальному количеству баллов за все тесты в этой группе.
Обратите внимание, что решение получает \(100\) баллов, если оно делает \(\leq k + 30\) запросов взвешивания во всех тестах во всех играх.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(k\) | \(maxQ\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | \(maxQ = 3500\) | – | Тесты из условия. |
| 1 | 5 | \(n \le 1000\) | – | \(maxQ = 1000\) | 0 | |
| 2 | 9 | \(n \le 1000\) | – | \(maxQ = 600\) | 0, 1 | |
| 3 | 10 | – | \(k \le 30\) | \(maxQ = 1000\) | 0 | |
| 4 | 13 | – | \(k = 3\) | \(maxQ = 33\) | – | |
| 5 | 13 | – | \(k = 4\) | \(maxQ = 34\) | – | |
| 6 | \(\le 50\) | – | – | \(maxQ = 3500\) | – | Частичные баллы. |
3500 3500 2 set 3 2 1 3 set 10 4 2 6 8 10
2 2 1 4 4