ENGLISH VERSION:
PROBLEM LINK:
editorilist: Kirill Ptukha.
QUICK EXPLANATION:
We can just simulate process of game.
For pawn u should check, can we go or not, if can check ability to kill other pawn, if u can, u automatically win.
EXPLANATION:
Lets see for some phases of turn for pawn.
r1 c1 - white pawn, r2 c2 - black pawn.
Let x is black or white pawn, rx, cx location of xth pawn. (rx - row, cx - colomn).
Will remind that rx of white pawn can only encrease for 1, and rx of black pawn, can only decrease.
1_ Let’s check that current pawn can go.
For this obviosly we should check rx for white pawn rx + 1 < 8, for black pawn rx - 1 > 1. And if this statement is true, lets check that rx ±1(for white or black pawn) is free, if not, win another pawn.
2_ If we can go forward, we should check can we kill another pawn or can’t.
For white pawn - if((r1 + 1 == r2 && c1 + 1 == c2) || (r1 + 1 == r2 && c1 - 1 == c2)) if true, white win.
For black pawn - if((r2 - 1 == r1 && c2 - 1 == c1) || (r2 - 1 == r1 && c2 + 1 == c1)) if true, black win.
TIME COMPLEXITY:
O(t * 8).
EDITORIALIST SOLUTION:
#РУССКАЯ ВЕРСИЯ:
#ССЫЛКА НА ЗАДАЧУ:
QCJ01
##Разбор подготовил: Кирилл Птуха.
#БЫСТРОЕ ОБЪЯСНЕНИЕ:
Для першки мы должны проверить возможность походить вперед, если можем, то нужно проверить можем ли мы сбить другую пешку.
#ОБЪЯСНЕНИЕ:
Посмотрим на фазу хода любой пешки.
r1 c1 - для белой, и r2 c2 - для черной.
Пусть x это белая или черная пешка, rx,cx расположение x-той пешки (rx - строка, cx - столбец).
Напомню что rx белой пешки может только увеличиваться на 1, а rx черной может только уменьшаться на 1.
1_ Проверим может ли совершить пешка ход.
Очевидно мы должны проверить rx (для белой пешки rx + 1 < 8, для черной rx - 1 > 1).
Если эти условия выполняются, то мы должны проверить клетку в которую собираемся идти. Если в ней есть пешка то, мы не можем совершить ход, а значит для текущей пешки игра проиграна.
2_ Если мы можем походить вперед, то мы должны проверить возможность сбить другую пешку.
Для белой пешки - if((r1 + 1 == r2 && c1 + 1 == c2) || (r1 + 1 == r2 && c1 - 1 == c2)) если верно, то белые победили.
Для черной пешки - if((r2 - 1 == r1 && c2 - 1 == c1) || (r2 - 1 == r1 && c2 + 1 == c1)) если верно, то черные победили.
АСИМПТОТИЧЕСКОЕ ВРЕМЯ:
O(t * 8).
#РЕШЕНИЕ АВТОРА РАЗБОРА:
решение автора разбора