Help!!!!!!!

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*