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

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

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++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Цикл с параметром (for)
 Цикл с предусловием (while)
 Цикл с постусловием (do ... while)
 НОД и НОК
 Бинарный поиск
 A. Сложность бинарного поиска
 B. POBEDA-2014
 C. Угадай число
 D. Ксерокопии
 E. Космическое поселение
 F. Стреляй!
 G. Вырубка леса
 H. Корень кубического уравнения
 I. Дипломы
 J. Кампус
 K. Сыграешь с Денисом?
 L. Три монеты
 M. Круговой марафон

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