When I tried to solve this problem, at first I wrote N^3 solution using Dynamic Programming: if we're seeing a piece with length = K and trying solve problem with any L, let's take K-1, K-2, ..., K-L buttons and see, whether second player win with new K and old L. But now we say, that it's first player, because we have already solve this problem for first player and K-1, K-2, ..., 2, 1.
That's all.

Here is my code:

{$APPTYPE CONSOLE}

program buttons;
var
  a: array[1..5000] of integer;
  k: integer;
  i, j, t, x: integer;
  f: boolean;

  function FirstWins(k, l: integer): boolean;
  begin
    Result := (l >= k) or (l < a[k]);
  end;

begin
  read(k);

  a[1] := 0; a[2] := 1;
  for i := 3 to k do
  begin
    for j := 2 to k-1 do
    begin
      f := true;
      for t := i-j to i-1 do
      begin
        if not FirstWins(t, j) then
        begin
          f := false;
          break;
        end;
      end;
      if f then
      begin
        a[i] := j;
        break;
      end;
    end;
  end;

  write(k);
end.

-----------------

After that I observed law: if k mod 3 = 0, print 2 else print n-1:

  read(k);

  if (k mod 3 = 0) then
    write(2)
  else
    write(k-1);

But I got WA in test 6.

Where is my mistake?
Where is mistake in DP-logic?

Edited by author 15.08.2005 10:25

Excuse me, I have already found the bug.
It was in function:

function FirstWins(k, l: integer): boolean;
begin
Result := (l >= k) or (l <> a[k]);
end;