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

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

HotLog


 

Три монеты

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

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

Перед вами стопка из N монет. В стопке есть все монеты номиналов от 1 до N, причём они упорядочены по возрастанию сверху-вниз. То есть, верхняя монета номиналом 1, а нижняя — N. Вес каждой монеты равен её номиналу. Некто заменил ровно три монеты в стопке на фальшивые — вес таких монет равен нулю. Вы можете спрашивать суммарный вес первых K монет сверху для любого 0 ≤ K ≤ N.

Определите номиналы фальшивых монет не более чем за 32 вопроса, и тогда Некто подарит вам всю стопку монет.

Протокол взаимодействия

Вначале на ввод подаётся число 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++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 A. Архимед
 B. Верхняя граница
 C. Волшебные цветы
 D. Двоичное упражнение
 E. Stack Unwinding
 F. Пробежка
 G. Три монеты
 H. Кинозал
 I. Индикатор загрузки
 J. Заверните две!
 K. Сладкая вата

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