Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Any Idea Why WA on test 10? | Hemisphere | 1073. Квадратная страна | 27 фев 2012 21:57 | 3 |
change f[60000] to f[60001] |
Why my answer is wrong? | Saimon | 1073. Квадратная страна | 13 ноя 2011 02:26 | 5 |
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) |
wa 2!!! | Vadim | 1073. Квадратная страна | 30 окт 2011 13:44 | 4 |
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) |
Help!!!!!!! | Charlie | 1073. Квадратная страна | 15 авг 2011 22:29 | 15 |
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. ? CHIDEMYAN SERGEY 2 дек 2007 21:19 [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) WA #5 Volkov Stanislav [MSU_Tashkent] 15 авг 2011 22:29 Edited by author 15.08.2011 22:30 |
递推能过.. | grayluck | 1073. Квадратная страна | 21 янв 2011 13:16 | 2 |
递推能过.. grayluck 22 сен 2009 06:19 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; |
Помогите! | Pustovalov | 1073. Квадратная страна | 13 сен 2010 21:47 | 3 |
Объясните по русски, что им надо??? They need you to read a problem statement in english... ...or just turn the russian language on... |
Weak Tests (No Large Inputs) | Varun Sharma | 1073. Квадратная страна | 31 окт 2009 23:59 | 2 |
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. :) |
Good Point | Seyyed Mehran Kholdi | 1073. Квадратная страна | 24 июл 2009 13:23 | 3 |
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 |
Why WA#18? | mirsaid_mir | 1073. Квадратная страна | 22 июл 2009 12:15 | 1 |
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 |
Why WA 13?? | WITALIY[UA] | 1073. Квадратная страна | 26 июн 2009 16:05 | 4 |
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 !!)) |
i can't understand BFS, what is it??? | Bobur | 1073. Квадратная страна | 28 май 2009 18:07 | 4 |
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 ;) |
solution | Cat36 | 1073. Квадратная страна | 7 мар 2009 08:13 | 3 |
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)). |
Bad tests | Marginean Ciprian | 1073. Квадратная страна | 5 мар 2009 19:25 | 2 |
I have Ac with wrong solution. My solution fails on 112 and other 4^k(8n+7) where k>=2 tests. |
Here is DP solution. If you know the Lagrange's proof about the theory, please contact me. megatronbiao@gmail.com | Megatron | 1073. Квадратная страна | 8 фев 2009 14:47 | 1 |
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; } |
Add tests please | Fyodor Menshikov | 1073. Квадратная страна | 2 фев 2009 20:41 | 3 |
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 ) |
Why i have WA #5 | Terminator | 1073. Квадратная страна | 15 сен 2008 15:11 | 2 |
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 |
Why is my solution wrong? | PopPy Mwit#17 | 1073. Квадратная страна | 7 апр 2008 12:29 | 1 |
#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); }; |
Could you give me some tests? | PopPy Mwit#17 | 1073. Квадратная страна | 7 апр 2008 12:23 | 1 |
Could you give me some tests? |
help !!!!! | Alibek | 1073. Квадратная страна | 12 мар 2008 22:09 | 2 |
Can anybody explain me DP algo what is it? It is easy At first you should create array of squares[], where ith element equals i*i. This array is key to the desicion) At start dp[] array has not improved values(obviously dp[i] = i) (dp[i] is minimal number of squares that in sum equal to i) then at every cycle add a new square and try to improve the previous result of dp. result in - dp[n]. complexity is O(n*sqrt(n)) |
Whe I have T limit on # 9 test? | XSpider | 1073. Квадратная страна | 6 мар 2008 21:45 | 1 |
#include <stdio.h> #include <math.h> int N, kol, Optkol; void kvad(int n) { for (int i=sqrt(double(n)); i>=1; i--) { if (n-i*i>=0 && kol+1 < Optkol) { kol++; mas[kol] = i*i; n -= i*i; if (n>0) kvad(n); else if (n == 0) Optkol = kol; l--; n=n+i*i; } } } int main() { scanf("%d", &N); Optkol = N; kvad(N); printf("%d\n", Optkol); return 0; } |