You are not logged in. Please login at www.codechef.com to post your questions!

×

QCJ01 editorial eng + rus versions

ENGLISH VERSION:

PROBLEM LINK:

QCJ01

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:

editorialist

РУССКАЯ ВЕРСИЯ:

ССЫЛКА НА ЗАДАЧУ:

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)$.

РЕШЕНИЕ АВТОРА РАЗБОРА:

решение автора разбора

asked 01 Feb, 01:35

kirillpt's gravatar image

3★kirillpt
262
accept rate: 50%

edited 01 Feb, 02:03

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×2

question asked: 01 Feb, 01:35

question was seen: 50 times

last updated: 01 Feb, 02:03