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

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

Здравствуйте, Rimdalf! Спасибо за задачу!
Задача понравилась, поэтому захотелось её решить. Наличие ограничений на число монет подтолкнуло к поиску различных вариантов "сетки": степени двойки, степени десятки и т.д., но всегда что-то не ладилось, поэтому я стал искать другой путь и нашёл его, обратившись непосредственно к номиналам фальшивых монет. В результате удалось решить задачу всего за 4 вопроса при любом конечном числе монет, поэтому я немного переформулировал постановку задачи.

Спасибо, Сергей Вениаминович!

Прекрасная идея! Что-то я сам до этого не догадался.
Но есть ошибки:
1) случай с `N=3` надо рассматривать отдельно;
2) При некоторых раскладах `S-1` больше `N`.

Но это мелочи. Есть ещё какая-то ошибка, но я не пойму какая. Второй день бьюсь, но никак не могу найти. Может, кто подскажет?

Прошу прощения!
С `N=3` не надо рассматривать отдельно. Там и так всё получается.

Решение на PascalABC.NET

Всё равно не получается у меня. На 47-м тесте Wrong answer.

Вот код на Питоне:

Да вроде Accepted.

Не знаю. Я так понял, что задача прошла 46 тестов, а на 47-й не прошла.

Здравствуйте, Алексей Владимирович!
Спасибо за найденную ошибку! Да, по условию задачи нельзя спрашивать вес монет, количество которых больше N.
Вы прекрасно исправили эту ошибку в своей программе, заменив S-1 на min(S-1, N). Теперь вроде бы ошибок нет.
Вы пишите про какие-то тесты, а где их можно пройти?
Я написал свою программу тестирования вашей программы, многократно её запускал, пока никаких ошибок она не нашла. Конечно, она тестирует случайными числами, что хуже, чем специальный подбор чисел под определённые нюансы, выявленные на основе качественного анализа задачи, но всё-таки.

Это Rimdalf нашёл.



Да, вроде нет, но в то же время 47-й тест не проходит.



Эта задача отсюда:
https://acmp.ru/asp/do/index.asp?main=t ... oblem=1840

Тут надо зарегистрироваться и ввести код программы. Если код написан правильно, система засчитывает задачу как решённую. Но вот с этой задачей как раз 47-й тест не проходит. Посмотреть, какие числа в этом тесте, к сожалению, нельзя. Вот я и не понимаю, в чём проблема.



Спасибо большое!

И огромное спасибо за решение!!!

Алексей Владимирович, большое спасибо за сайт!
Когда будет время тоже здесь что-нибудь порешаю.