ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1222. Chernobyl’ Eagles

Right Algo:
Posted by bsu.mmf.team 24 Nov 2008 22:33
The product of natural numbers with a given condition in this problem will be maximal if and only if the middle arithmetic of these numbers is the most closely to the number e=2.71828... It's a mathematical sentence which are proved!

P.S. Sorry for my bad English
Re: Right Algo:
Posted by kobra 13 Mar 2012 20:20
thank you for advice
Re: Right Algo:
Posted by Petru Trimbitas 26 Jul 2012 18:41
Why is that true? You can get AC without math :P
Re: Right Algo:
Posted by 2rf 27 Jul 2012 01:32
Well, you only need to understand that optimal partition can't contain any x >= 4(as 2*(x-2) >= x in this case), it obviously can't contain ones, and it can't contain more than 2 copies of 2, as 2*2*2<3*3. Surpisingly, there is only one way to express any x >= 2 as sum of 3's and not more than two 2's.
Re: Right Algo:
Posted by ComebackSeason 16 Jun 2017 22:11
That's a very nice idea. Let me clarify it for those who had problems understanding  bsu.mmf.team's English. First of all, 'middle arithmetic' is an arithmetic mean. The thing is, the product will be maximal if (a_1 + a_2 + ... + a_n) / n  ≈ e.
Well, it's not hard to figure out that the output of the program should be something like that:    3 * 3 * 3 * ... * ?