Обсуждение @ 1222. Chernobyl’ Eagles @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

What idea in solution? Kirin Vladislav 9 май 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? GaLL [Tyumen SU] 9 май 2006 02:44

6--> 3*3=9, isn't it?

Re: What idea in solution? lj_860603 9 май 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? Giorgi Beridze[IBSU_Tbilisi] 6 фев 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? denton 17 фев 2008 19:45

Giorgi Beridze[IBSU_Tbilisi] писал(a) 6 февраля 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? ☞ⓩⓢⓨⓩ™ⓣⓔⓢⓣ☜ 29 мар 2009 19:20

for 8-->3*3*2=18(not a 16)

Re: What idea in solution? Andrew Hoffmann aka SKYDOS [Vladimir SU] 2 авг 2010 18:28

Edited by author 03.08.2010 17:40

No DP, O(1) void 3 авг 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) bsu.mmf.team 3 авг 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.

Обсуждение задачи 1222. Chernobyl’ Eagles