Why my answer is wrong?

Posted by

Saimon 12 Nov 2011 02:14

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?

Re: Why my answer is wrong?

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?

Dynamic Programming (the problem is also tagged with DP)