Недавно в задачу были добавлены тесты, которые показали, что многие принятые ранее решения оказались неверными (задача упала даже у парня на первому месте в рейтинге). Давайте разбираться:
Нетрудно заметить (и это сделали в обсуждении к задаче), что выполнять махинацию первого типа не имеет смысла (даже в комбинации со второй). Действительно, простое прибавление одного и того числа не меняет взаимного расположения участников в таблице результатов. Если же прибавить, а потом домножить на некоторое число, то получим:
(x + a) * b = x * b + a * b
что эквивалентно домножению, а потом прибавлению числа a * b, то есть опять никак не влияет на результат.
Давайте второй вид махинации рассмотрим на примере:
3
10 21
20 15
50 0
Все участники имеют два числа, а значит их можно изобразить в виде точек на плоскости:
И выигрывают те, у кого сумма координат будет наибольшей, то есть то, которые лежат на прямой, параллельной y = -x, но максимально удалённой от начала координат.
Если результаты второго тура умножить на 4, то получим:
То есть произойдёт растяжение по оси y, что на самом деле эквивалентно изменению наклона решающей прямой:
Аналогичные изменения происходят, при домножении результатов первого тура, просто прямая будет увеличивать угол наклона.
Из всего этого можно сделать очень важный вывод:
Нет смысла применять махинацию второго типа одновременно к обоим турам
Потому что максимальный угол наклона достигается при максимальном изменении результатов первого тура. Если коэффициент уменьшать, то и угол будет стремиться к 45 градусам. А после этого уже можно увеличивать коэффициент домножения во втором туре. В итоге, мы всё равно получаем все допустимые положения прямой.
Благодаря этому наблюдению можно решать задачу независимо для каждого тура, существенно уменьшив сложность.
Первым делом подключим библиотеки и сделаем традиционные для работы с pair подстановки:
В этой задаче предстоит работать с дробными числами, поэтому все сравнения надо будет делать с учётом погрешности, так что помимо ввода данных сразу определим точность (eps), с которой будем работать:
Также заведём сет, куда будем складывать номера всех подходящих участников олимпиады:
Тогда вывод результата будет заключаться в выводе всех элементов этого сета:
Напишем функцию, которая будет вычислять всех участников, которые могут выиграть с помощью махинации второго типа в первом туре. Для этого переберём их всех и для каждого найдём минимальное значение множителя, которое необходимо для победы:
Изначально этот коэффициент равен 1, а затем проверим всех конкурентов и благодаря простой пропорции обновим (если необходимо) его значение:
Здесь мы пропустили всех участников, которые в первом туре набрали больше или столько же, потому что с такой махинацией победы над ними всё равно не добиться.
Итак, у нас множитель, проверим, что результаты участников не стали больше 100 баллов, и текущий участник действительно набирает не меньше баллов, чем все остальные (это необходимо как раз из-за того, что мы на прошлом шаге могли некоторых пропустить):
Если всё в порядке, то можно номер текущего участника добавить к ответу, так как мы нашли множитель, который обеспечивает ему победу:
Осталось вызвать нашу функцию, а затем поменять туры местами и снова вызвать функцию, тем самым накопив победителей, применив махинацию к обоим турам независимо:
Довольно непростая получилась задача в плане рассуждений (поэтому, если требуются дополнительные пояснения, то спрашивайте), которая ещё и осложняется аккуратной работой с дробными числами. Потому что стоит только к каком-нибудь сравнении убрать eps, сразу получаются неверные ответы.
Предыдущий выпуск: Задача 11. Зайчик
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.