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 Why is that true? You can get AC without math :P Well, you only need to understand that optimal partition can't contain any x >= 4(as 2*(x-2) >= x in this case), it obviously can't contain ones, and it can't contain more than 2 copies of 2, as 2*2*2<3*3. Surpisingly, there is only one way to express any x >= 2 as sum of 3's and not more than two 2's. That's a very nice idea. Let me clarify it for those who had problems understanding bsu.mmf.team's English. First of all, 'middle arithmetic' is an arithmetic mean. The thing is, the product will be maximal if (a_1 + a_2 + ... + a_n) / n ≈ e. Well, it's not hard to figure out that the output of the program should be something like that: 3 * 3 * 3 * ... * ? 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? :))) Rounding. You can get times of 0.001, 0.015, 0.031, 0.046, 0.062 etc (the step is around 15.5). And, of course, 0.015 wouldn't mean you have exactly that time; it would rather mean that you have somewhere between 0.002 and 0.015. Or around that. Thanks. Possible time interval of 15 ms, I saw a long time ago. Just do not understand, he can not keep within the 1 ms solution like С++: ----------------------------------- #include <iostream> using namespace std; int main() { int a,b; cin>>a>>b; cout<<(a+b)<<"\n"; } ----------------------------------- or Pascal: ----------------------------------- var a,b: integer; begin readln(a,b); writeln(a+b); end. ----------------------------------- I think it should work many times faster than 1 ms. Time spent on the input and output? P.S. Today I passed the task of "1000 A + B Problem" of 0.001s. But usually - 0.015s. :) Hypotesis: The program may start at the beginning or end of the interval timer - and depending on this time will be different. If TLE < 0.014, repeat Submit, while not AC! ))) 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. I solved it with Python and 4 SLOC in 0.14 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 :) YOU ARE REALLY LAZY : void MLT(int x) { int r = 0; REP(i,3000) { int init = ((res[i]*x)+r);
res[i] = init % 10; r = init / 10; } } 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 your program works endlessly when n is 1; in other cases your program is right and also in case when n is 2 your program outputs ' symbol hope it helps!!! Edited by author 08.03.2012 13:36 Edited by author 08.03.2012 13:37 Edited by author 10.01.2006 12:58 n=3000 answer 1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001 1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001 I pass your test, but i can't pass test 10. 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 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.) if n mod 3=0 then ansver is 3 in pover (n div 3); in other cases answer is 2*2*2*...*3 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. for 8-->3*3*2=18(not a 16) Edited by author 03.08.2010 17:40 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? 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. 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! n=3000 6230944380615661730540866744905062220607354471963766287778397756065940 6962697903814082629320941801101660304581383981489487361062625347661816 5706321659264965023017203487210780255823880970691747085650866739360077 645709393425508719830393155473510779779930751 But I got wa too. 1322070819480806636890455259752144365965422032752148167664920368226828 5973467048995407783138506080619639097776968725823559509545821006189118 6534272525795367402762022519832080387801477422896484127439040011758861 8041128947815623094438061566173054086674490506178125480344405547054397 0388958174653682549161362208302685637785822902284163983078878969185564 0408489893760937324217184635993869 13220708194808066368904552597521443659654220327521481676649203682268285973467048 99540778313850608061963909777696872582355950954582100618911865342725257953674027 62022519832080387801477422896484127439040011758861804112894781562309443806156617 30540866744905061781254803444055470543970388958174653682549161362208302685637785 82290228416398307887896918556404084898937609373242171846359938695516765018940588 109060426089671438864102814350385648747165832010614366132173102768902855220001 78269792221766377248792586107312578551454955298456387837931004855964813172193821243390064215949238600077681954053753825948909941306968357700343451652009989159020094600778289423859975436358546313727455317042603649908448160723189846384364576128985442328158891806918309846544996297697505373844135967311576127112637752359444869773878802929985672496258464403635036929317966161945895754817512140406205791563756008285751669647079656658308372789688485874728678798223164136163414900736 When n=3000 my AC program print: 1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001 Because correct is: 1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001 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???? Use array friend, write your own multiply function. Timus array max size = 64 K (or i may wrong) which means you can create char array[64000] store up to 64K digit Edited by author 16.04.2007 20:37 Edited by author 16.04.2007 20:56 size of array is not limited. if you need you can create array of any size. you must to implemet your own multiplication. algorithm is the same as you do it in your exercise book if in pascal you can use extended 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; } |
|