ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1073. Square Country

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!!!!!!!
Posted by Charlie 8 Sep 2006 20:05
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.

 The algo is:
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!!!!!!!
Posted by Slam [Tartu U] 24 Jan 2007 11:00
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!!!!!!!
Posted by jagatsastry 2 Dec 2007 18:10
What does "i" refer to. Can anyone tell me How the above method works. i.e. what a[i] stores.
?
Posted by CHIDEMYAN SERGEY 2 Dec 2007 21:19
[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!!!!!!!
Posted by partisan 10 Jun 2009 15:58
Greedy fails on 12:
12=9+1+1+1 (greedy)
12=4+4+4 (correct)
WA #5
Posted by Volkov Stanislav [MSU_Tashkent] 15 Aug 2011 22:29

Edited by author 15.08.2011 22:30