|
|
|
|
|
|
Вернуться
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), чтобы найти или одну из крайних, или среднюю, если нам повезёт с еë расположением. Именно здесь и возникает проблема. Если мы не знаем крайних монет, то не знаем в какую сторону бинарным поиском нам идти, чтобы найти среднюю. Конечно, мы можем использовать бинарный поиск для нахождения одной из крайних монет. В большинстве случаев мы сможем найти информацию для решения (например, верхнюю и сумму верхней и средней). Но если мы, например, пошли искать нижнюю монету, а средняя находится рядом с верхней, которая в свою очередь находится рядом с 1, мы лишь найдём нижнюю и сумму верхней и средней, что не решит нам задачу. Если вам не сложно, можете подсказать, что делать.
|
|
|
6 Беляев Сергей Николаевич, 22 февраля 2024 г. 5:51:31 | |
Если Вам уже крайние монеты известны, то для вычисления средней достаточно от суммы всех номиналов фальшивых монет отнять эти крайние.
|
|
|
7 Алексеенко Андрей Витальевич, 21 февраля 2024 г. 14:04:23 | |
Для решения задачи нужно знать, где две крайние монеты (что сложно достижимо из-за количества запросов) или где средняя монета, которую сложно найти, так как мы не знаем, где крайние. Можете подсказать, как обеспечить нахождение средней монеты?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |