TopCoder SRM 598 Div1 第2題

Problem Statement
Fox Ciel is playing a board game with her friend Squirrel Liss. The game is played on an infinite strip of paper. The strip of paper is divided into consecutive cells. Each cell has an integer coordinate. Formally, for each integer i, the left neighbor of cell i is cell (i-1) and the right neighbor of cell i is cell (i+1). Each of the players has a single token called the fencer. At the beginning of the game, Ciel's fencer is in cell 0 and Liss's fencer is in cell d. Each of the fencers has two limits: its maximum move length and its hitting range. For Ciel's fencer the maximum move length is mov1 and the hitting range is rng1. Similarly, for Liss's fencer we have the parameters mov2 and rng2. Note that the parameters of Liss's fencer may differ from the ones of Ciel's fencer. The players take alternating turns. Ciel goes first. In each turn the current player starts by moving her fencer. The distance between the original cell and the destination cell must be at most equal to the fencer's maximum move length. (It is also allowed to leave the fencer in the same cell.) Then, the current player checks whether the other fencer lies within the hitting range - that is, whether the current distance between the fencers is at most equal to the current fencer's hitting range. If that is the case, the game ends and the current player wins. You are given the ints mov1, mov2, rng1, rng2, and d. Return "Ciel" (quotes for clarity) if Fox Ciel has a winning strategy, "Liss" if Squirrel Liss has a winning strategy, and "Draw" otherwise.
Definition
Class: FoxAndFencing Method: WhoCanWin Parameters: int, int, int, int, int Returns: string Method signature: string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) (be sure your method is public)
Constraints
-	mov1 will be between 1 and 100,000,000, inclusive.
-	mov2 will be between 1 and 100,000,000, inclusive.
-	rng1 will be between 1 and 100,000,000, inclusive.
-	rng2 will be between 1 and 100,000,000, inclusive.
-	d will be between 1 and 100,000,000, inclusive.
Examples
0)
1 58 1 58 2 Returns: "Ciel" The attributes of Ciel's fencer are much smaller than the attributes of Liss's fencer. Luckily for Ciel, she can win the game in her first turn: she should move her fencer to cell 1 and from there she can hit the other fencer.
1)
2 1 1 100 50 Returns: "Liss" Ciel cannot score a hit in the first turn. After Ciel's turn, her fencer will be on one of the cells {-2,-1,0,1,2}. Regardless of its precise location, Liss can always move her fencer one cell to the left and then hit Ciel.
2)
2 1 1 100 150 Returns: "Draw" Clearly, Ciel has no chance of winning this game. However, this time the initial distance d is big enough for Ciel to escape.
3)
100 100 100 100 100000000 Returns: "Draw"
4)
100 1 100 1 100000000 Returns: "Ciel"
5)
100 1 100 250 100000000 Returns: "Draw"
6)
100 1 100 150 100000000 Returns: "Ciel"
7)
100 50 100 1 100000000 Returns: "Ciel"
8)
100 150 100 1 100000000 Returns: "Draw"

類型：博弈  難度：2

題意：不知道為啥這道不算太難的博弈會是550分的題，考察細節吧。Ciel和Liss在一條直線的兩點，相距距離為d，他們每次能走的最大距離為mov1,mov2，他們的武器能夠到的範圍為rng1,rng2，Ciel先走，每一步包括走一段并可以嘗試用武器打對方，每個人都用最優政策走，問誰會赢，還是平局

分析：1、首先應該考慮第一回合會不會分出勝負，若mov1+rng1>=d，那麼Ciel赢，若mov2+rng2>=d+mov1，Liss赢（Liss後手，要加mov1）

2、若第一回合分不出勝負，那麼需要比較mov1，mov2（之前考慮比較mov1+rng1和mov2+rng2，發現并不正确，每次隻能走mov步，是以要按mov來分情況）

（1）mov1==mov2，一定是平局

（2）mov1>mov2，Ciel走得快，那麼Ciel如果想赢，必須在追着Liss走了x步時能打到Liss，但是又要防止Liss在x-1步時反向走倒打一耙，是以需要滿足條件，

mov1-mov2+rng1>mov2+rng2。也可以了解為，當Ciel走到和Liss距離為mov1+rng1時，Liss又會走mov2，那麼Ciel必須保證第x步走到和Liss距離為mov1-mov2+rng1，然後Liss走第x步走過mov2，然後這時輪到Ciel走第x+1步，此時距離為mov1+rng1，那麼一走一打剛好打到Liss，其中，當Ciel走完第x步而Liss未走第x步時，二者距離最近，為mov1-mov2+rng1，必須保證這個距離大于mov2+rng2，否則Liss就會倒打一耙，就是平局。

（3）mov1<mov2，和(2)同理

代碼：

#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;

class FoxAndFencing
{ 	 
	public:
		string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d)
		{
			if(mov1+rng1>=d) return "Ciel";
			else if(mov2+rng2>=mov1+d) return "Liss";
			
			if(mov1>mov2)
			{
				if((mov1-mov2)+rng1 > mov2+rng2) return "Ciel";
				return "Draw";
			}
			if(mov1<mov2)
			{
				if((mov2-mov1)+rng2 > mov1+rng1) return "Liss";
				return "Draw";
			}
			return "Draw";
		}
};

int main()
{
	FoxAndFencing t;
	cout << t.WhoCanWin(2,1,1,100,50)<<endl;
}