Problem A. Amateur Chess Players

59 阅读 0 评论 39 点赞

我是靠谱客的博主淡淡鸵鸟，最近开发中收集的这篇文章主要介绍Problem A. Amateur Chess Players，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Tags：Game Theory

From 2020 ECNU Campus Online Invitational Contest
Description：
Chess is a two-player board game played on a chessboard (a square-checkered board with 64 squares
arranged in an eight-by-eight grid). In a chess game, each player begins with sixteen pieces: one king, one
queen, two rooks, two knights, two bishops, and eight pawns. The object of the game is to checkmate the
opponent’s king, whereby the king is under immediate attack (in “check”) and there is no way to remove
or defend it from attack, or force the opposing player to forfeit.
在这里插入图片描述 Cuber QQ and Quber CC are two amateur chess players, who know almost nothing about all the fancy
rules in chess, perhaps except how the chessboard looks like, and they have no interest in it. Instead, they
invent their own chess game. At the beginning, Cuber QQ, who has the white pieces, and Quber CC, who
has the black pieces, place some of their pieces on the chessboard. Then they start to remove those pieces
by turn. Cuber QQ moves first. In each turn, they must remove at least one of their own pieces (Cuber
QQ can only remove white and Quber CC can only remove black). Two or more pieces can be removed
together in one turn if and only if these pieces are collinear on the chessboard, meaning they should lie
in the same line. Note that this line does NOT have to be in horizontal or vertical or diagnoal direction.
The one who fails to make a move loses the game.
Now Cuber QQ and Quber CC are both desperate to win the game. So they will do it smartly and make
optimal decisions. Who do you think will win the game, eventually?

Input
The input consists of four lines:
• The first line is an integer n (1 ≤ n ≤ 16), the number of white pieces on the chessboard.
• The second line consists of n space-separated positions, which are the positions of white pieces.
• The third line is an integer m (1 ≤ m ≤ 16), the number of black pieces on the chessboard.
• The last line consists of m space-separated positions, which are the positions of black pieces.
Each position is a upper case letter in “A” to “H”, followed by a digit in “1” to “8”.
It is guaranteed that there are no overlapping pieces, that is, all pieces are located at different positions.

Output
If Cuber QQ is going to win, output “Cuber QQ” without quotes. Otherwise output “Quber CC”.
Examples
standard input standard output
4
A1 B2 D4 C3
3
A8 D6 H7
Cuber QQ
4
A1 B2 C3 D5
4
A8 C7 E6 G5

I’think it’s obvious that the optimal strategy is removing only one piece at a time
For the first player（Cuber QQ），only if his pieces are more than CC he can win this game

So much useless information，hh

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
string s;
int n,m;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>s;
    }
    cin>>m;
    for(int i=0;i<m;++i)
        cin>>s;
    cout<<(n>m? "Cuber QQ":"Quber CC")<<endl;
    return 0;

}