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

What idea in solution?
Posted by Kirin Vladislav 9 May 2006 02:27
I thought that we must do with heads (n) next:
2*2*2*...*(n div 2)      ---> for odd(n)=false and
2*2*2*...*3*((n-3) div 2)---> for odd(n)=true.
What why answer for n=:
5-->2*3=6
6-->2*2*2=8
7-->2*2*3=12
8-->2*2*2*2=16
9-->2*2*2*3=24
but when I write solution, a saw that ans
for 6=3*3=9(not an 8),
for 9=3*3*3=27(not a 24).
COULD YOU HELP ME WITH RIGHT IDEA?

Edited by author 29.05.2006 18:25
Re: What idea in solution?
Posted by GaLL [Tyumen SU] 9 May 2006 02:44
6--> 3*3=9, isn't it?
Re: What idea in solution?
Posted by lj_860603 9 May 2006 13:06
The last number must be 3,and others must be 2.So you have to judge whether n is an odd number or an even number first.This step is very important.And the n must be:
n=2+2+2...+3(if n was an even number,there is no 3.)
Re: What idea in solution?
Posted by Giorgi Beridze[IBSU_Tbilisi] 6 Feb 2008 14:52
if n mod 3=0 then ansver is 3 in pover (n div 3);
in other cases answer is 2*2*2*...*3
Re: What idea in solution?
Posted by denton 17 Feb 2008 19:45
Giorgi Beridze[IBSU_Tbilisi] wrote 6 February 2008 14:52
if n mod 3=0 then ansver is 3 in pover (n div 3);
in other cases answer is 2*2*2*...*3

3*3 > 2*2*2, so your assumption is wrong.
The answer is 2*3*3*...*3, when n is even and 3*3*...*3 otherwise.
Re: What idea in solution?
Posted by ☞ⓩⓢⓨⓩ™ⓣⓔⓢⓣ☜ 29 Mar 2009 19:20
for 8-->3*3*2=18(not a 16)
Re: What idea in solution?
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 2 Aug 2010 18:28


Edited by author 03.08.2010 17:40
No DP, O(1)
Posted by void 3 Aug 2010 03:30
Answer is a simple multiplication: 3*3*...*3. If n % 3 == 2, then it ends with ...*2*2.

It's somehow linked with E, but how?
Re: No DP, O(1)
Posted by bsu.mmf.team 3 Aug 2010 17:38
If n could be divided on rational numbers, then the max product will be always (n/k)^k, where k is integer, such that abs(n/k - E) is minimal possible value. It is a well-known theorem.