ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

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.