Discussion @ 1255. Graveyard of the Cosa Nostra @ Timus Online Judge

any1 tell me what`s wrong with my greedy (most obvious) algorithm?

Posted by Locomotive 15 Mar 2003 19:33

Var
N, K : LongInt;
begin
Readln(N, K);
WriteLn((Sqr(N)-Sqr(N Mod K)) Div K);
end.
isn`t answer of
7 4
--->
10?

aidin_n7@hotmail.com

Re: any1 tell me what`s wrong with my greedy (most obvious) algorithm?

Posted by Leonid Volkov 16 Mar 2003 00:10

But it is wrong, indeed.
Look at the following sample - 5 3
What is the answer? 7? No, it's 8!

1 1 1 2 3
4 4 4 2 3
5 6 * 2 3
5 6 7 7 7
5 6 8 8 8

thanks a lot So can u tell me a hint?

Posted by Locomotive 16 Mar 2003 14:25

No subject

Posted by Gheorghe Stefan 18 Mar 2003 21:20

Your formula don't work with 5 3. The answer is 8 like this:

1 1 1 3 4 but your program outputs (25 - 4) / 3 = 7
2 2 2 3 4
5 6 0 3 4
5 6 7 7 7
5 6 8 8 8

:)

Discussion of Problem 1255. Graveyard of the Cosa Nostra