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.

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.

Easy problem.

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

input->1
output->1

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

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.

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; }

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

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.

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

I think that correct answer for n=2 is 1, because if one of eagles has 2 heads and another 0 heads then IQ will be 2*0=0, isn't it? But my program had WA3 in that case. When I wrote 2 in output for n=2, I got accepted. Why?

For n=3000 my program outputs 1.3220708194808066E+0477. Any idea about how to print it digit by digit?

I get CE in the next time. Judge said this:

03cfd131-5f0d-45f4-91b6-d6962d109aa7.obj : error LNK2019: unresolved external symbol _itoa referenced in function "void __cdecl init(void)" (?init@@YAXXZ)

I already linked up <stdio.h> and <stdlib.h> but this didn't help.

Please help me.

Hi to all! I have some problems with solving this task on C (but AC on Pascal).. I got WA#1 and Crash(Access violation)#1, but I can't find any bug in my program and it runs without errors on my computer..
Is it different in compilers (I use BC++5.02)?
Thanks.
sorry for my bad english

please