Фальшивые монеты
(Время: 1 сек. Память: 16 Мб Сложность: 55%)
Это интерактивная задача.
Перед вами стопка из N монет. В стопке есть все монеты номиналов от 1 до N, причём они упорядочены по возрастанию сверху-вниз. То есть, верхняя монета номиналом 1, а нижняя — N. Вес каждой монеты равен её номиналу. Некто заменил ровно три монеты в стопке на фальшивые — вес таких монет равен нулю. Вы можете спрашивать суммарный вес первых K монет сверху для любого 0 ≤ K ≤ N.
Определите номиналы фальшивых монет не более чем за 10 вопросов, и тогда Некто подарит вам всю стопку монет.
Протокол взаимодействия
Вначале на ввод подаётся число N — количество монет (3 ≤ N ≤ 109). Далее ваша программа должна выводить запросы вида «? K», где 0 ≤ K ≤ N. В ответ вы получите сумму весов первых K монет вверху стопки.
Как только ваша программа будет готова сообщить ответ, выведите «! A B C», где 1 ≤ A, B, C ≤ N — различные номиналы фальшивых монет. После этого программа должна завершить работу.
Пример
| стандартный ввод | стандартный вывод |
|---|
6
12
6
6
2
2
0
0 | ? 6
? 5
? 4
? 3
? 2
? 1
? 0
! 1 5 3 |
Примечание
Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:
- В языке Pascal: flush(output)
- В С/С++: fflush(stdout) или cout.flush()
- В Java: System.out.flush()
- В Python: sys.stdout.flush() из библиотеки sys
- В C# и Basic: Console.Out.Flush()
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
