var n,tmp,i:word;
begin
i:=0;
read(n);
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?

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

Thank, i'll think again :)

P.S Can you say me what is DP?


Edited by author 12.11.2011 02:33

Dynamic Programming (the problem is also tagged with DP)