Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Фальшивые монеты

(Время: 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()

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 Седьмая личная олимпиада
 A. Лифт в бизнес-центре
 B. Компаратор
 C. Фальшивые монеты
 D. Разделяемые разбиения

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru