|
|
back to boardHelp!!!!!!! Posted by Charlie 28 Jul 2006 19:58 Who can help me!!!tell me how to solve the problem!!! Re: Help!!!!!!! Posted by sniper 4 Sep 2006 17:56 DP:
a[i]:=min(a[i-j*j])+1
j:=trunc(sqrt(i div 4)+1)to trunc(sqrt(i)) Re: Help!!!!!!! thank u!nou I get AC. BUT WHY Posted by SM 9 Jan 2007 10:55 can anyone tell me why (sqrt(i div 4)+1)? Re: Help!!!!!!! Posted by xerxe 14 Jan 2007 21:31 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 Re: Help!!!!!!! Posted by xerxe 23 Jan 2007 15:45 Ok, my bad ... You need DP. Greedy is bad ! I need to remember that... Thanx to the guy who posted the 181 case. Re: Help!!!!!!! Actually, u don't need DP ) didt u read other topics?-) Re: BUT WHY Posted by alisher 17 Feb 2007 12:02 because there are 4 sides at the square!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Re: Help!!!!!!! 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 Re: Help!!!!!!! Posted by Bobur 25 Dec 2007 22:10 thank u very much, i've AC wiht your help Re: Help!!!!!!! Posted by Cyclops 22 Aug 2008 10:33 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.. Re: Help!!!!!!! Posted by xerxe 12 May 2009 01:39 I did, but didn't understand them yet. (yes, I'm still at it after two years!) Re: Help!!!!!!! Greedy fails on 12:
12=9+1+1+1 (greedy)
12=4+4+4 (correct) WA #5
Edited by author 15.08.2011 22:30 |
|
|
