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

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

why greedy is right?
Послано Edric Mao 24 авг 2010 16:06
why taking the biggiest fraction of remain assure that the church gets the minimized?
Re: why greedy is right?
Послано Frontone 15 июл 2011 18:41
Please, anybody explain! Im also interested in answer!
Re: why greedy is right?
Послано wangbicheng1 19 сен 2011 11:33
Also wondering... anyone can prove it?
No subject
Послано Capitan 22 фев 2013 15:04
Re: why greedy is right?
Послано zxc master 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.