I get WA on Test 14, some can help me with this? Here's my code. #include <iostream> #include <math.h> int solve( float val_p ) { int id = 0, sqr = 0, seqCount = 0, bestCount = 9999, maxVal = val_p, n = (int)sqrt( val_p ); for( int seqID = n; seqID > n/2; seqID-- ) { id = seqID; maxVal = val_p; seqCount = 0; while( id > 0 ) { sqr = id*id; --id; if ( maxVal >= sqr ) { maxVal -= sqr; id = sqrt( float( maxVal ) ); if ( ++seqCount > bestCount ) break; } } bestCount = std::min( bestCount, seqCount ); }; return bestCount; }; int main() { unsigned int val = 0; while( std::cin >> val ) { if ( val > 60000 || val <= 0 ) break; std::cout << solve( val ) << std::endl; } return 0; } Why I have Crash (access violation)? any hint or test case ? change f[60000] to f[60001] var n,tmp,i:word; begin i:=0; read(n); repeat tmp:=sqr(trunc(sqrt(n))); n:=n-tmp; i:=i+1; until n=0; writeln(i); end. This is my programm, why it's wrong? I do some test and i think to my programm is right. Help please, where my mistake? The classical "biggest square" greedy :) For N = 18, you output 3 (16 + 1 + 1) but the right answer is 2 (9 + 9). Think how you can use DP here (as it's also suggested). How to find a solution based on "smaller" solutions. Edited by author 12.11.2011 02:21 Thank, i'll think again :) P.S Can you say me what is DP? Edited by author 12.11.2011 02:33 Dynamic Programming (the problem is also tagged with DP) Do you known test?I got wa 2,but I think that my program is right) It's my code: var F:array[0..1000000] of longint; I,j,mi,n:longint; Begin Read(n); F[0]:=0; F[1]:=1; F[2]:=2; For i:=3 to n do Begin Mi:=100000; For j:=1 to trunc(sqrt(i)) do If mi>f[i-j*j] then mi:=f[i-j*j]; F[i]:=mi+1; End; Writeln(f[i]); End. Writeln(f[i]); = undefined behaviour first of all, try f[n], not f[i] You are a superman!!!!!!!!!!!!Thanks) Who can help me!!!tell me how to solve the problem!!! DP: a[i]:=min(a[i-j*j])+1 j:=trunc(sqrt(i div 4)+1)to trunc(sqrt(i)) can anyone tell me why (sqrt(i div 4)+1)? because there are 4 sides at the square!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! What does "i" refer to. Can anyone tell me How the above method works. i.e. what a[i] stores. [deleted] Edited by author 16.12.2008 18:48 thank u very much, i've AC wiht your help how could you get the transition function (a[i]:=min(a[i-j*j])+1)? How could you find it? Is it a "try -error method?" Please explain to me..thanks.. You don't need DP. You can solve it in O(1). Well actually, O(7) at worst :). I didn't solve it yet, I have WA at test 5, but I'm sure it can be done. [Edit] The algo is: read n while n>0 x++ n-=(int(sqrt(n)))^2 write x [/Edit] P.S: still have WA @ #5 :(. Don't know why... Edited by author 14.01.2007 23:09 Ok, my bad ... You need DP. Greedy is bad ! I need to remember that... Thanx to the guy who posted the 181 case. Actually, u don't need DP ) didt u read other topics?-) I did, but didn't understand them yet. (yes, I'm still at it after two years!) Greedy fails on 12: 12=9+1+1+1 (greedy) 12=4+4+4 (correct) Edited by author 15.08.2011 22:30 for i := 2 to n do begin min:=maxlongint; for j := 1 to trunc(sqrt(i)) do if min>f[i-j*j] then min:=f[i-j*j]; f[i]:=min+1; end; Объясните по русски, что им надо??? They need you to read a problem statement in english... ...or just turn the russian language on... Hi, It looks like, input test cases are not large enough. My DP program is taking 3 seconds for large inputs like 50000 or 60000 etc, but it got accepted in 0.062 seconds. Admins need to look at this. Varun We have large inputs, but your program works 0.062 sec on test 60000. :) There exists a proof by Lagrange, that 4 square are enough to display any number and it's a direct answer. It's a kind of Number Theory problem. I find it very useful because there is just 2 or 3 conditions you should check. Good Luck I have Wrong Answer on test number 18. Tell me please, how I can solve this problem. Where I can get Tests for this problem Tell my please, why I have Wrong Answer on test number 13 and if it is not problem, tell how I can solve this problem to e-mail WitaliyProg@mail.ru Thanks! Maybe you consider not all cases or some cases are considered incorrectly. Be patient in singular cases. Try this: ------ 1 1 ------ 2 2 ------ 8 2 ------ 12 3 ------ 45 2 ------ 32028 4 ------ 59999 4 ------ 60000 3 ------ 20242 2 ------ 12005 2 ------ 33333 3 ------ 2401 1 ------ 42025 1 ------ 4001 2 ------ 2999 4 ------ 29645 2 ------ 9999 4 ------ 512 2 ------ I had WA #15 in second version of problem (1593) and had wrong in tests like 2^(2k+1)*square. The tests above are on all cases in solution from that version. If you have DP, maybe you have little bug in it. I hope, that these tests will help you. Thanks! I dont use DP. Maybe you can tell me how to make not DP solution? Please... My e-mail WitaliyProg@mail.ru Thanks !!)) Let image graph where every number is vertex, then we can add edge from a to b if a+SQ=b (where SQ - some square). Now you can see graph, there maximum 60000 vertex and maximum ~ 60000*300 = 18 000 000 edges, out task is find way from 0 to given number. BFS will done this in O(N+M) this task is easy to solve O(N) time ;) answer == 1 - manually answer == 2 - manually answer == 3 - n%8 !=7 else answer ==4 and answer = 3 if ((N%32!=28)&&(N!=28)) good luck ) and answer = 3 if ((N%32!=28)&&(N!=28)) How did you derive this formula? I think it worked for you because of too little test numbers. In the analogous problem #1593 N<=10^15 your formula fails. Nevertheless checking n=a^2+b^2 is at worst longer (O(sqrt(N)) than checking n=a^2+b^2+c^2 (log(N)). I have Ac with wrong solution. My solution fails on 112 and other 4^k(8n+7) where k>=2 tests. DP is easy. I want to know the easiest solution to the problem. Please contact me. megatronbiao@gmail.com Thanks. Sorry for my English. #include <iostream> #include <cmath> using namespace std; int data[60001]; int main() { int n; cin>>n; data[1]=1; data[2]=2; for (int i=3;i<=n;++i) { int min=data[i-1]+1; for (int j=2;j<=245;++j) { if (i>=j*j) { if (min>data[i-j*j]+1) min=data[i-j*j]+1; } else break; } data[i]=min; } cout<<data[n]; return 0; } I know AC solution, that checks correctly for answers 1 and 2, but distinguishes answers 3 and 4 using simple test if (n%8==7) { answer 4 } else { answer 3 } One of tests that it not passes is 59996. It answers 3 while correct answer is 4. Please add some tests where n%8!=7 and answer is 4. Some new tests were added. for example: N=28 or N=60; good luck ) pleas tell me where is my mistake? var n,q,a:longint; begin read(n); q:=0; while n>=1 do begin a:=trunc(sqrt(n)); a:=sqr(a); inc(q); n:=n-a; end; write(q); end. Shortly, this solution (greedy - take the biggest square size possible) is incorrect. For example, let's take 12. Your solution would take 9, 1, 1, 1 - 4 pieces. But you can distribute them 4, 4, 4 - 3 pieces #include<stdio.h> long func(long a,long b,long c); long pow(long x,long y); long result=1; long n; long k; int count=0; int main(){ scanf("%ld",&n); k=n; for(;k>0;){ k-=pow((long)sqrt(k),2);; result=1; count++; }; func(n,0,(long)sqrt(n)); printf("%d",count); for(;;); }; long pow(long x,long y){ if (y!=0) return x*pow(x,y-1); return 1; }; long func(long a,long b,long c){ int i; if (b>=count || a<0) return 0; if (b<count && a==0){ count=b; printf("%ld %ld %ld\n",a,b,c); }; for(i=c;i>0;i--) func(a-pow(i,2),b+1,i); }; |
|