1) White moves first.
2) The game is being played according to the usual chess rules, but
if the white pawn reaches the Nth horizontal, the game immediately
stops.
3) How could Black win? There are 5 actual possiblities
   a) Beat the white pawn with the King
   b) Block the movement of the white pawn with the King
   c) Block the movement of the white pawn with the Pawn
   d) Promote the black pawn to the Queen (or something else) and
then beat the white pawn with this new piece
   e) Promote the black pawn to the Queen (or something else) and
then block the movement of the white pawn with this new piece

> 1) White moves first.
> 2) The game is being played according to the usual chess rules, but
> if the white pawn reaches the Nth horizontal, the game immediately
> stops.
> 3) How could Black win? There are 5 actual possiblities
>    a) Beat the white pawn with the King
>    b) Block the movement of the white pawn with the King
>    c) Block the movement of the white pawn with the Pawn
>    d) Promote the black pawn to the Queen (or something else) and
> then beat the white pawn with this new piece
>    e) Promote the black pawn to the Queen (or something else) and
> then block the movement of the white pawn with this new piece
>
>

First, we consider that the site of white pawn is (x1,y1), (x2,y2)
for black pawn, (x3,y3) for Black King. We can consider the following
five lines:

>    a) Beat the white pawn with the King
We can count the least steps of Black King to get to y1+1 or y1-1,
and it could only go left-up or right-up. (I think it's the optimum)

>    b) Block the movement of the white pawn with the King
I think we can ignore it or put it into state a).

>    c) Block the movement of the white pawn with the Pawn
I think if and only if (x2=x1+1 or x2=x1-1) and (y2>=x2+2), then the
black pawn can block the movement of the white pawn and beat it...

>    d) Promote the black pawn to the Queen (or something else) and
> then beat the white pawn with this new piece
first i think because n>5, so we only can promote it to the Queen.
Then the best way to beat the white pawn is to move left to y1. If
and only if x1<=n-2, the Queen can beat it.

>    e) Promote the black pawn to the Queen (or something else) and
> then block the movement of the white pawn with this new piece
I think we can ignore it!!!

Only some ideas, I haven't programme yet. Because of the time...

>    d) Promote the black pawn to the Queen (or something else) and
> then beat the white pawn with this new piece
first i think because n>5, so we only can promote it to the Queen.
Then the best way to beat the white pawn is to move left to y1. If
and only if x1<=n-2, the Queen can beat it.

change to:

>    d) Promote the black pawn to the Queen (or something else) and
> then beat the white pawn with this new piece
first i think because n>5, so we only can promote it to the Queen.
Then the best way to beat the white pawn is to move left or right to
y1. If and only if x1<=n-2, the Queen can beat it.

*    white pawn
x    black pawn
K    black King
The white first. If we beat the black pawn:

..........
..........
..........
......x...
.....*...K
..........
..........
..........
..........
..........

..........
..........
..........
......*.K.
..........
..........
..........
..........
..........
..........

..........
..........
......*K..
..........
..........
..........
..........
..........
..........
..........

White will lose.....

but if we don't beat the black pawn:

..........
..........
..........
......x...
.....*...K
..........
..........
..........
..........
..........

..........
..........
..........
.....*....
......x..K
..........
..........
..........
..........
..........

..........
..........
.....*....
..........
.........K
......x...
..........
..........
..........
..........

of course white will win!!

If it is not Black&#8217;s turn to move, the black King should not be
under check, i.e. in the position, when the white pawn could beat it.

Can everyone give me your testdata(s) of ural1216? I have checked a
lot, but I think if we put our testdatas(or ideas) together, the
problem will be solved easily. I want to be the programmer, and you
give me the datas, I test..again and again. Can you help me? If I get
ac, of course I will send my program to you all!!! My ideas you can
see at http://acm.timus.ru/messages.asp?id=5753, my msn messager is
zhuzeyuan@hotmail.com, I'm a Chinese.

> 1) White moves first.
> 2) The game is being played according to the usual chess rules, but
> if the white pawn reaches the Nth horizontal, the game immediately
> stops.
> 3) How could Black win? There are 5 actual possiblities
>    a) Beat the white pawn with the King
>    b) Block the movement of the white pawn with the King
>    c) Block the movement of the white pawn with the Pawn
>    d) Promote the black pawn to the Queen (or something else) and
> then beat the white pawn with this new piece
>    e) Promote the black pawn to the Queen (or something else) and
> then block the movement of the white pawn with this new piece
>
>
And what about beating with the pawn?

> And what about beating with the pawn?

That's true, I forgot to mention that case :-)