CF493D.Vasya and Chess

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Vasya decided to learn to play chess. Classic chess doesn't seem interesting to him, so he plays his own sort of chess.

The queen is the piece that captures all squares on its vertical, horizontal and diagonal lines. If the cell is located on the same vertical, horizontal or diagonal line with queen, and the cell contains a piece of the enemy color, the queen is able to move to this square. After that the enemy's piece is removed from the board. The queen cannot move to a cell containing an enemy piece if there is some other piece between it and the queen.

There is an n × n chessboard. We'll denote a cell on the intersection of the r-th row and c-th column as (r, c). The square (1, 1) contains the white queen and the square (1, n) contains the black queen. All other squares contain green pawns that don't belong to anyone.

The players move in turns. The player that moves first plays for the white queen, his opponent plays for the black queen.

On each move the player has to capture some piece with his queen (that is, move to a square that contains either a green pawn or the enemy queen). The player loses if either he cannot capture any piece during his move or the opponent took his queen during the previous move.

Help Vasya determine who wins if both players play with an optimal strategy on the board n × n.

瓦西里决定学习下棋。经典国际象棋对他来说似乎不够有趣,因此他玩的是自己设计的一种棋类游戏。

皇后是能够吃掉其所在竖线、横线和对角线上所有格子的棋子。若某个格子与皇后位于同一竖线、横线或对角线上,且该格子中存在对方颜色的棋子,则皇后可以移动到该格子上;随后,对方的这枚棋子将被从棋盘上移除。但若皇后与目标格子中的敌方棋子之间存在其他棋子,则皇后不能移动到该格子。

现有一个 n×nn \times n 的棋盘。我们将第 rr 行与第 cc 列交叉处的格子记为 (r, c)(r,\,c)。格子 (1, 1)(1,\,1) 上放置着白方皇后,格子 (1, n)(1,\,n) 上放置着黑方皇后。其余所有格子上均放置绿色兵(pawns),这些兵不属于任何一方。

双方轮流走棋:先手方控制白方皇后,后手方控制黑方皇后。

每次走棋时,玩家必须用己方皇后吃掉某枚棋子(即移动到一个包含绿色兵或对方皇后的格子上)。若某玩家在轮到自己走棋时无法吃掉任何棋子,或在上一手棋中己方皇后已被对方吃掉,则该玩家判负。

请帮助瓦西里判断:在 n×nn \times n 棋盘上,若双方均采用最优策略,哪一方将获胜?

输入格式

The input contains a single number n (2 ≤ n ≤ 109) — the size of the board.

输入包含一个整数 nn(2 ≤ n ≤ 1092 \leq n \leq 10^9)——棋盘的大小。

输出格式

On the first line print the answer to problem — string "white" or string "black", depending on who wins if the both players play optimally.

If the answer is "white", then you should also print two integers r and c representing the cell (r, c), where the first player should make his first move to win. If there are multiple such cells, print the one with the minimum r. If there are still multiple squares, print the one with the minimum c.

第一行输出该问题的答案——字符串 "white" 或 "black",具体取决于双方均采取最优策略时的获胜方。

若答案为 "white",则还需输出两个整数 rr 和 cc,表示先手玩家应在其第一步中选择的格子 (r, c)(r,\,c) 以确保获胜。若存在多个满足条件的格子,则输出其中 rr 最小者;若仍有多个格子满足 rr 最小,则输出其中 cc 最小者。

输入输出样例

  • 输入#1

    2

    输出#1

    white
    1 2
  • 输入#2

    3

    输出#2

    black

说明/提示

In the first sample test the white queen can capture the black queen at the first move, so the white player wins.

In the second test from the statement if the white queen captures the green pawn located on the central vertical line, then it will be captured by the black queen during the next move. So the only move for the white player is to capture the green pawn located at (2, 1).

Similarly, the black queen doesn't have any other options but to capture the green pawn located at (2, 3), otherwise if it goes to the middle vertical line, it will be captured by the white queen.

During the next move the same thing happens — neither the white, nor the black queen has other options rather than to capture green pawns situated above them. Thus, the white queen ends up on square (3, 1), and the black queen ends up on square (3, 3).

In this situation the white queen has to capture any of the green pawns located on the middle vertical line, after that it will be captured by the black queen. Thus, the player who plays for the black queen wins.

在第一个样例测试中,白方皇后可在第一步吃掉黑方皇后,因此白方获胜。

在题面给出的第二个测试中,若白方皇后吃掉位于中央竖直线上的绿色兵,则下一步会被黑方皇后吃掉。因此,白方唯一可行的走法是吃掉位于 (2, 1)(2, 1) 的绿色兵。

同理,黑方皇后别无选择,只能吃掉位于 (2, 3)(2, 3) 的绿色兵;否则,若它移动至中央竖直线,将被白方皇后吃掉。

接下来的一步中,情况相同——白方皇后与黑方皇后均只能吃掉各自正上方的绿色兵,别无他选。最终,白方皇后到达格子 (3, 1)(3, 1),黑方皇后到达格子 (3, 3)(3, 3)。

此时,白方皇后必须吃掉中央竖直线上任一绿色兵,此后即被黑方皇后吃掉。因此,执黑方获胜。

输入解题思路,AI测评打分。不知道怎么写?

首页