|
|
back to boardRight Algo: 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: 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: 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 * ... * ? |
|
|