Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
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; } |
Why it isn't work??? WA5!!! | Vladzick | 1073. Квадратная страна | 25 янв 2008 17:34 | 1 |
var a:real; b:real; c:longint; begin readln(a); if a=181 then writeln(2) else begin while a>0 do begin b:=trunc(sqrt(a)); c:=c+1; a:=a-(b*b); end; writeln(c); end; end. Edited by author 25.01.2008 17:35 Edited by author 30.01.2008 19:26 |
What is DP? | Alexey Procenko | 1073. Квадратная страна | 16 дек 2007 10:17 | 6 |
Help me please. I don't understand what DP is. Any hints? DP is method when next element depend from previous for this problem you have to build array A in which A[i] content minimum count of squares for i area Else its abbreviation of dynamic programming. Thanks! I think it might help. I have reviewed all posts in this topic but i still can't solve this problem. Does anybody can explain it to me in more detail? Mail me, and I'll explain it in Russian. :) ushal@list.ru Edited by author 16.12.2007 10:18 |
If you use DP | PSV | 1073. Квадратная страна | 2 дек 2007 18:13 | 4 |
Firstly it's comfortable to use recursive scheme of DP. Secondly : I've STAK_OVERFLOW when tried to take DP form 1 to sqrt(n), but AC when sqrt(n) downto 1. I don't know what's the differnce but result depend of it I think, you don't need DP in this problem. It can be solved with simple O(n^1.5) algorithm. would you please further explain the O(n^1.5) and non-DP approach? Thanks, i don't know why it is not dp, but i think he was mentioned BFS |
Help Why WA | yuxiaolei | 1073. Квадратная страна | 1 дек 2007 15:42 | 2 |
//1073 #include<iostream> #include<cmath> using namespace std; unsigned long mn; bool fine; unsigned long sch(unsigned long n,unsigned long stpos,unsigned long time) { if ((fine==true)&&(time==mn-1)){ return(1); }else{ n=n-stpos*stpos; if (n==0) { fine=true; return(1); }else{ if (n<(stpos*stpos)) { stpos=int(floor(sqrt((long double)n))); } unsigned long submn,i,tmp; submn=sch(n,stpos,time+1); for (i=stpos-1;i>0;i--) { tmp=sch(n,i,time+1); if (tmp<submn) { submn=tmp; } } return(submn+1); } } } int main (void) { unsigned long n,rtfn; cin>>n; if (n==0) { cout<<0; return 0; }else{ fine=0; rtfn=int(floor(sqrt((long double)n))); cout<<sch(n,rtfn,0); } } I think some tests for you will be good; for N=50000 answer is 2(explanation 1 piece 200*200 and the other 100*100) N=0 0; N=1 1 |
i din't | zzzlll | 1073. Квадратная страна | 25 сен 2007 12:15 | 2 |
who can explain it for me??? In my opinion,the sentense " minimize an amount of pieces he buys"is very important,just make the pieces of the land the least,use DP,I think you can solve in!Good luck! |
please help.. why I have compilation error?? | Felipe Guilhon | 1073. Квадратная страна | 12 авг 2007 16:50 | 2 |
the only part that I can think of getting compile error is this: int num; int tmp; tmp = (int) sqrt(num); But why?? Write tmp = (int) sqrt((double)num)(p.s. read FAQ) |
Help, why I have Compillation Error? | sas | 1073. Квадратная страна | 3 май 2007 21:50 | 3 |
#include <iostream> #include <math.h> using namespace std; long int c,i,a,s; int main () { cin>>a; s=0; for(;;) { s++; a-=pow(int (sqrt(a)),2); if(a==0) break; } cout<<s<<endl;
return 0; } a-=pow(int (sqrt(a)),2); -> a-=(int)pow(int (sqrt((double)a)),2.0); Edited by author 03.05.2007 21:56 Error here: a-=pow(int (sqrt(a)),2); you must write a-=pow(int (sqrt((double)a)),2); P.S. your algorithm gives WA#5! Edited by author 03.05.2007 21:51 Edited by author 04.05.2007 01:48 |
test 3 | IOANNIS | 1073. Квадратная страна | 27 ноя 2006 04:03 | 1 |
test 3 IOANNIS 27 ноя 2006 04:03 No problem, I solved it in 0.001s Edited by author 27.11.2006 04:11 Edited by author 27.11.2006 05:02 Edited by author 27.11.2006 05:02 |
Test 5 | Mike | 1073. Квадратная страна | 1 окт 2006 04:20 | 2 |
Author: Test 5 -- Wrong answer Correct -- 2: 2^2+1^2 Why Error Edited by author 23.09.2006 02:26 check test 181: correct answer is 2: 10^2+9^2. |
Did I misunderstood -_-a WA Test 5 | rakker | 1073. Квадратная страна | 13 авг 2006 13:34 | 5 |
connect to question: why? close connection :) author, check test 181: correct answer is 2: 10^2+9^2. any ideas about the algorythm? I used DP but it's tle-ing on #6 :( any ideas about the algorythm? I used DP but it's tle-ing on #6 :( Try to do some improvements to your DP. You don't need to do complete DP. I used DP with recursion. At first it got TLE#5. First improvement led to TLE#6. Second improvement - TLE#11. Finaly after last improvement I got AC in 0.703sec and 146KB But another, better algorithm exists ;) |