1222 Timus answer/Решение задачи 1222

№1222
http://acm.timus.ru/problem.aspx?space=1&num=1222
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL


{W/A}
Type Long = Array[0..200] of Word;

Var N1,N2,I: LongInt;
E: Boolean;
S1,S2: Array[1..3000] of LongInt;
R: Long;

Procedure WriteLong(Var A: Long);
Var I: Integer;
S: String;
Begin
Write(A[A[0]]);
For I:=A[0]-1 downto 1 do begin
Str(A[I],S);
While Length(S)<4 do
S:='0'+S;
Write(S);
End;
End;

Procedure MulShort(Const A:Long;B: Word; Var R: Long);
Var I: Integer;
Rem: LongInt;
Begin
R[0]:=A[0];
Rem:=0;
For I:=1 to R[0] do begin
Rem:=Rem+A[I]*LongInt(B);
R[I]:=Rem mod 10000;
Rem:=Rem div 10000;
End;
R[R[0]+1]:=Rem;
If (Rem<>0) then Inc(R[0]);
End;

Begin
Read(S1[1]);
N1:=1;
Repeat
E:=True;
N2:=0;
For I:=1 to N1 do
If (S1[I] div 2)*(S1[I]-S1[I] div 2)>S1[I] then begin
E:=False;
Inc(N2,2);
S2[N2-1]:=S1[I] div 2;
S2[N2]:=S1[I]-S1[I] div 2;
End;
If not E then begin
S1:=S2;
N1:=N2;
End;
Until E;
R[0]:=1;
R[1]:=1;
For I:=1 to N1 do
MulShort(R,S1[I],R);
WriteLong(R);
End.

1222. Chernobyl’ Eagles

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ

A Chernobyl’ eagle has several heads (for example, the eagle on the Russian National Emblem is a very typical one, having two heads; there exist Chernobyl’ eagles having twenty-six, one and even zero heads). As all eagles, Chernobyl’ eagles are very intelligent. Moreover, IQ of a Chernobyl’ eagle is exactly equal to the number of its heads. These eagles can also enormously enlarge their IQ, when they form a group for a brainstorm. IQ of a group of Chernobyl’ eagles equals to the product of IQ’s of eagles in the group. So for example, the IQ of a group, consisting of two 4-headed eagles and one 7-headed is 4*4*7=112. The question is, how large can be an IQ of a group of eagles with a given total amount of heads.

Исходные данные

There is one positive integer N in the input, N ≤ 3000 — the total number of heads of Chernobyl’ eagles in a group.

Результат

Your program should output a single number — a maximal IQ, which could have a group of Chernobyl’ eagles, with the total amount of heads equal to N.

Пример

исходные данные	результат
5	6

Автор задачи: folklore, proposed by Leonid Volkov
Источник задачи: The Seventh Ural State University collegiate programming contest