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

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


 
Вернуться
Тема: Задача №1675 (три монеты)
1
  1  Беляев Сергей Николаевич, 24 февраля 2024 г. 5:08:41
      Задача решается за 4 запроса.
  2  Алексеенко Андрей Витальевич, 23 февраля 2024 г. 13:54:56
      Большое спасибо за помощь
  3  Тер-Саркисов Богдан Олегович, 23 февраля 2024 г. 12:30:32
      Кстати, есть и задача 1680, в которой требуется выяснить то же самое, только за 10 запросов.
  4  Тер-Саркисов Богдан Олегович, 23 февраля 2024 г. 12:24:53
      Первым запросом можно посчитать сумму всех трех фальшивых монет s3 (сумма прогрессии до N минус результат запроса). Далее можно поддерживать диапазон [L; R], в котором будут находиться все три монеты, постепенно его сжимая. На каждой итерации выбирать среднее значение m и делать запрос на сумму от 1 до m. Возможно 3 исхода:
1) сумма от 1 до m совпадает с результатом запроса - значит, на отрезке [1; m] нет фальшивых монет, и границу L можно сместить до m+1.
2) сумма от 1 до m минус s3 совпадает с результатом запроса - значит, на отрезке [1; m] все три фальшивые монеты, границу R можно сместить до m.
3) результат запроса равен сумме прогрессии от 1 до m минус 1 или 2 фальшивые монеты. А сколько монет конкретно, можно выяснить за 1 запрос. Пусть d - это сумма одной или двух фальшивых монет. Проверим, является ли это одной монетой, сделав запрос на d. При этом надо учесть, что d должно быть <= m. В случае успеха d - первая монета, иначе s3-d - третья монета. Выходим из цикла.
Теперь известна одна крайняя монета и диапазон [L; R], который можно поправить в зависимости от результата пункта 3, чтобы в нём содержалось только 2 монеты. И дальше можно продолжить сжимать отрезок [L; R] аналогично тому, как делали для трех монет, до тех пор, пока L не станет равно одной монете, а R - другой монете.
  5  Алексеенко Андрей Витальевич, 23 февраля 2024 г. 2:12:40
     
Легко получить информацию о сумме трёх монет, достаточно спросить N монет. Дальше сложнее. При N = 10^9 монет нам нужно сделать 30 запросов (log2 от 10^9 примерно 30), чтобы найти или одну из крайних, или среднюю, если нам повезёт с е&#235; расположением. Именно здесь и возникает проблема. Если мы не знаем крайних монет, то не знаем в какую сторону бинарным поиском нам идти, чтобы найти среднюю. Конечно, мы можем использовать бинарный поиск для нахождения одной из крайних монет. В большинстве случаев мы сможем найти информацию для решения (например, верхнюю и сумму верхней и средней). Но если мы, например, пошли искать нижнюю монету, а средняя находится рядом с верхней, которая в свою очередь находится рядом с 1, мы лишь найдём нижнюю и сумму верхней и средней, что не решит нам задачу.
Если вам не сложно, можете подсказать, что делать.
  6  Беляев Сергей Николаевич, 22 февраля 2024 г. 5:51:31
      Если Вам уже крайние монеты известны, то для вычисления средней достаточно от суммы всех номиналов фальшивых монет отнять эти крайние.
  7  Алексеенко Андрей Витальевич, 21 февраля 2024 г. 14:04:23
      Для решения задачи нужно знать, где две крайние монеты (что сложно достижимо из-за количества запросов) или где средняя монета, которую сложно найти, так как мы не знаем, где крайние. Можете подсказать, как обеспечить нахождение средней монеты?
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

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