Discussion @ 1108. Heritage @ Timus Online Judge

why greedy is right?

Posted by Edric Mao 24 Aug 2010 16:06

why taking the biggiest fraction of remain assure that the church gets the minimized?

Re: why greedy is right?

Posted by Frontone 15 Jul 2011 18:41

Please, anybody explain! Im also interested in answer!

Re: why greedy is right?

Posted by wangbicheng1 19 Sep 2011 11:33

Also wondering... anyone can prove it?

No subject

Posted by Capitan 22 Feb 2013 15:04

http://en.wikipedia.org/wiki/Sylvester's_sequence

Re: why greedy is right?

Posted by zxc master 27 Dec 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.

Discussion of Problem 1108. Heritage