using DP you can achieve O(n)

This question can be solved using the same logic in 1167(Bicolored horses), but it will give tle.

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

I got AC. My time is 0.001s (This problem #1222) - Objected-oriented progarmming, call methods, cycles in cycles...

But my time of Problem #1000 (A+B) (int + int) - 0.015s

Why?

:)))

Editorial 1222. Chernobyl’ Eagles

We need to find set of numbers k > 0 and a[i] > 0:
a1 + a2 + ... + ak = n
a1 * a1 * ... * ak -> inf

0. If n = 1 answer = 1, later let's suppose n > 1

1. First of all let's see that in optimal solution a[i] > 1:
Assume a[j] == 1 for some j, also it means that k > 1 (i.e. there is another a[f] in our solution, f != j):
a1 * a2 * ... * a[j-1] * 1 * a[j+1] * ... * ak =
a1 * a2 * ... * a[j-1] * a[j+1] * ... * ak  <
a1 * a2 * ... * a[j-1] * a[j+1] * ... * (ak + 1) =
a1 * a2 * ... * a[j-1] * a[j+1]) * ... * ak + a1 * a2 * ... a[j-1] * a[j+1]) * ... * a[k-1]

It means that such set of number (a1, a2, ..., a[j-1], 1, a[j+1], ..., ak) is not optimal solution

2. Now let's see that in optimal solution a[i] < 4:
Assume a[j] >= 4 for some j, now we can split a[j] to (a[j] - 2) and 2, and find which a[j] will give us better results:

a1 * a2 * ... * a[j] * ... * ak >= a1 * a2 * ... * (a[j] - 2) * 2 * ... * ak
(a[j] - 2) * 2    >= a[j]
2 * a[j] - 4    >= a[j]
a[j] - 4        >= 0
a[j]            >= 4 (as we assumed)

It means that optimal solution will be consist 2's and 3's:
2 * a + 3 * b = n
2 ^ a + 3 ^ b -> max

3. Consider all leftover form of solution which was not proved to be not optimal:

1) 3 * 3 * 3 * 3 * ... (a = 0)
2) 2 * 3 * 3 * 3 * ... (a = 1)
3) 2 * 2 * 3 * 3 * ... (a = 2)
4) 2 * 2 * 2 * 3 * ... (a = 3)
5...) .... a > 3

Solution's 4), 5), 6), ... - is not optimal because we can take any 3 of 2's and replace it with 2 of 3', because
2 * 2 * 2 = 8 < 9 = 3 * 3

It means that 1), 2), 3) potential form of optimal solution

4. Now show that none of the solutions 1), 2), 3) can be compared to each other and it will be mean that 1), 2) and 3) can not be improved, i.e. it is optimal solution.
For this let's look at constraint:
2 * a + 3 * b = n

1) 3 * b1 = n => n % 3 = 0
2) 3 * b2 + 2 = n => n % 3 = 2
3) 3 * b3 + 2 * 2 = 3 * b3 + 4 = 3 * (b3 + 1) + 1 = n => n % 3 = 1

Now we can see that form of optimal solution (1), 2) or 3)) depend on n % 3,
e.g. if n % 3 == 2, then form 2) is optimal solution and nor 1) nor 3) can be formed.

If you're using C++, you should use a class that allow you to use big numbers. I performed that making a bigNum struct, that store the number in a string. It has one function, that multiplies that value by a given integer. Then, return that value. Once you got that, make a function powBigNum, with parameters:

-a bigNum struct
-the exponent
-The number that you'll use as product.

this function returns a bigNum struct. So, you'll get in the main code something like that:

        if(n%3 == 0)
            cout << powBigNum(num, n/3, 3).n;
        else if(n%3 == 1)
            cout << powBigNum(num, (n/3)-1, 3).product(4);
        else if(n%3 == 2)
            cout << powBigNum(num, (n/3), 3).product(2);

My program got AC in 0.031 sec 368 KB. Hope you get AC too.

Please do something with TL on java applications. My usual programs gets TL too often. For example, normal solution in 1222 using DP and BigInteger has failed because of this problem. I had to use precalculations, but it's not so clear a normal solutions.

Easy problem.

P.S. If you have WA#2
check this tests
3 -> 3
2 -> 2
1 -> 1

Hehe,,, normally i don't write Java code, but I am lazy this time :)

input->1
output->1

The time limit is 1 sec and my program works for 3000 for about 0.5 seconds.Why I got TL?
Here's my solution:

[code deleted]

Edited by moderator 02.02.2020 19:25

Edited by author 10.01.2006 12:58

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

simply use bignums...

I do not know why
Please help me!

var
  i,n,m,k,j:integer;
  b:array[1..5000]of integer;

begin
  fillchar(b,sizeof(b),0);
  readln(n);
  case n of
    0:begin writeln(1); halt;end;
    1:begin writeln(1); halt;end;
    2:begin writeln(2); halt;end;
    3:begin writeln(2); halt;end;
  end;
  case (n mod 3) of
    1:b[5000]:=4;
    2:b[5000]:=6
  else b[5000]:=3;
  end;
  n:=(n div 3)-1;
  m:=1;
  while n>0 do
    begin
      for i:=5000 downto 5001-m do
        b[i]:=b[i]*3;
      for i:=5000 downto 5001-m do
        if b[i]>=10 then
          begin
            inc(b[i-1],b[i] div 10);
            b[i]:=b[i] mod 10;
          end;
      if b[5000-m]<>0 then inc(m);
      dec(n);
    end;
  for i:=5001-m to 5000 do
    write(b[i]);
end.

What is the answer for n=3000? According to my problem it is:

1112410638837951982681559213420228436655660132143101893639583499479104
8307860224498112075664780555124758923322998295448875554498944133575085
7206969739792707314008867553774340959765426840307082886757146900689409
1769558402678831747586833656908719011631685677289799215417532225045801
3194444896132535792828846054226294650004927200184834052327444607699483
6595280893152817992146653301160115779064762003728308491537220749832979
2557104621996394714041315150395706599135856376433569557036792447902521
76364500701

but i've got WA

HELP!

How Can I show the longest value with all digits.
Now I show for n=3000  1.32207e+477
I use long double.
somebody can help me????

F[i] =   Max[F[i-j]*j}   (0<i<=20)
         1               (i=0)
         F[i-3]*3        (i>20)

In this way,you can solve the problem in O(n^2).

Edited by author 28.01.2009 03:58

#include <iostream>
using namespace std;
int main()
{ int n,x=0,s=0,y=1,i;
cin>>n;
while(x<=n) ( x+=3; s++; }
if(n%3==0) { for(i=0; i<s; i++) y*=3; cout<<y<<endl; }
if(n%3==1) { for(i=0; i<(s-1); i++) y*=3; cout<<(4*y)<<endl; }
if(n%3==2) { for(i=0; i<s; i++) y*=3; cout<<(2*y)<<endl; }
return 0; }