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

Posted by Saimon 12 Nov 2011 02:14
var n,tmp,i:word;
begin
i:=0;
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?
Re: Why my answer is wrong?
Posted by morbidel 12 Nov 2011 02:17
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
Re: Why my answer is wrong?
Posted by Saimon 12 Nov 2011 02:25
Thank, i'll think again :)
Re: Why my answer is wrong?
Posted by Saimon 12 Nov 2011 02:27
P.S Can you say me what is DP?

Edited by author 12.11.2011 02:33
Re: Why my answer is wrong?
Posted by morbidel 13 Nov 2011 02:26
Dynamic Programming (the problem is also tagged with DP)