2015
04-15

# Game

Alice and Bob are playing game with each other. They play the game on a 2D board. Alice has many vertical 1*2 tiles while Bob has many horizontal 2*1 tiles. They take turn to place their own tiles on the board. Considering about that the tiles cannot overlap each other, the player cannot do the placement any more loses. Since this is such a complex game that they could not find optimal method to play that, Alice decide to simplify this game by replace the large 2D board by some small ones. Alice set up a lot of Tetris tiles instead of the original 2D board. In the other words, the player can only place their own vertical or horizontal tiles on the Tetris-like board. Each player can choose one possible place on any Tetris tiles to place its own tiles. In fact, there are following 15 types of Tetris playground.

The playground cannot be transformed in any ways, including reflection and rotation.
Given the number of each type of tiles, you are asked to determine who will win the game if Alice plays first and both players are playing optimal.

There are multiple test cases; the first line of input contains a single integer denoting the number of test cases.
For each test case, there are only one line contains 15 integers denoting the number of Tetris tiles of the above 15 types. All the numbers are no greater than 100.

There are multiple test cases; the first line of input contains a single integer denoting the number of test cases.
For each test case, there are only one line contains 15 integers denoting the number of Tetris tiles of the above 15 types. All the numbers are no greater than 100.

3
5 4 0 0 0 0 0 0 0 0 0 0 0 0 0
5 5 0 0 0 0 0 0 0 0 0 0 0 0 0
100 100 0 0 0 0 0 0 0 0 0 2 1 0 0

Case #1: Alice
Case #2: Bob
Case #3: Alice

1– 2A  2–2B                                              ///1

3 4– 1A OR 2B       5 6 –1B OR 2A        ///2

7 8 1A1B OR 1A    9 10–1A1B OR 1B  ///3

11 12 13 14 1A OR 1B                            ///4

15 2A OR 2B                                             ///5

#include <cstdio>
#define min(a,b) (a>b?b:a)
int num[16];
int game[10];
int p[5];
int main ()
{
int cas;
scanf("%d",&cas);
for (int I=1 ; I<=cas ; ++I)
{
int tmpmin;
int turn=0;//表示当前子游戏的先手
p[0]=0;p[1]=0;//记录约去平衡状态后的每个人的可放个数
for (int i=0 ; i<15 ; ++i)
{
scanf("%d",num+i);
}
game[0]=num[0];     game[1]=num[1];             ///1
game[2]=num[2]+num[3];  game[3]=num[4]+num[5];  ///2
game[4]=num[6]+num[7];    game[5]=num[8]+num[9];///3
game[6]=num[10]+num[11]+num[12]+num[13];        ///4
game[7]=num[14];                                ///5

/**约去平衡态**/
/// 1
game[0]>game[1]?p[0]+=2*(game[0]-game[1]):p[1]+=2*(game[1]-game[0]);
/// 2
tmpmin=min(game[2],game[3]);
game[2]-=tmpmin;
game[3]-=tmpmin;
/// 3
tmpmin=min(game[4],game[5]);
game[4]-=tmpmin;    game[5]-=tmpmin;
/// 4
game[6]=game[6]&1;
/// 5
game[7]=game[7]&1;

/// 5>2>4>3>1
///**按优先级进行游戏 1情况不影响结果可先处理**///
///5
if(game[7])p[turn]+=2,turn^=1;
///2
if(game[2])
{
if(game[2]&1){if(turn == 1)p[1]+=2;  else p[0]+=1; turn^=1 ; }
p[1]+=game[2]/2*2;
p[0]+=game[2]/2;
}
if(game[3])
{
if(game[3]&1){if(turn == 0)p[0]+=2;  else p[1]+=1; turn^=1 ; }
p[0]+=game[3]/2*2;
p[1]+=game[3]/2;
}
///4
if(game[6])
{
p[turn]+=1;turn^=1;
}
///3
if(game[4])
{
p[0]+=game[4];
if(game[4]&1)
{
if(turn == 1)p[1]+=1;
turn^=1;
}
p[1]+=game[4]/2;
}
if(game[5])
{
p[1]+=game[5];
if(game[5]&1)
{
if(turn == 0)p[0]+=1;
turn^=1;
}
p[0]+=game[5]/2;
}
///
//printf("%d----%d\n",p[0],p[1]);
printf("Case #%d: %s\n",I,p[0]>p[1]?"Alice":"Bob");
}
return 0;
}


1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。