ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1108. Наследство

Edric Mao why greedy is right? [4] // Задача 1108. Наследство 24 авг 2010 16:06
why taking the biggiest fraction of remain assure that the church gets the minimized?
Frontone Re: why greedy is right? [1] // Задача 1108. Наследство 15 июл 2011 18:41
Please, anybody explain! Im also interested in answer!
zxc master Re: why greedy is right? // Задача 1108. Наследство 27 дек 2020 11:43
RUS
можно разобрать на первом примере.
1/2, 1/3
1 - (1/2) - (1/3) = (1/6)
Пусть следующий элемент в массиве будут равен x. Тогда доля для церкви будет составлять (1/6)- x .  Пусть оно будет равно y
Следует:
x + y = (1/6)
Тогда для минимизации y, нужно максимизировать x.
wangbicheng1 Re: why greedy is right? [1] // Задача 1108. Наследство 19 сен 2011 11:33
Also wondering... anyone can prove it?