CF154D.Flatland Fencing
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The King of Flatland will organize a knights' tournament! The winner will get half the kingdom and the favor of the princess of legendary beauty and wisdom. The final test of the applicants' courage and strength will be a fencing tournament. The tournament is held by the following rules: the participants fight one on one, the winner (or rather, the survivor) transfers to the next round.
Before the battle both participants stand at the specified points on the Ox axis with integer coordinates. Then they make moves in turn. The first participant moves first, naturally. During a move, the first participant can transfer from the point x to any integer point of the interval [x + a; x + b]. The second participant can transfer during a move to any integer point of the interval [x - b; x - a]. That is, the options for the players' moves are symmetric (note that the numbers a and b are not required to be positive, and if a ≤ 0 ≤ b, then staying in one place is a correct move). At any time the participants can be located arbitrarily relative to each other, that is, it is allowed to "jump" over the enemy in any direction. A participant wins if he uses his move to transfer to the point where his opponent is.
Of course, the princess has already chosen a husband and now she wants to make her sweetheart win the tournament. He has already reached the tournament finals and he is facing the last battle. The princess asks the tournament manager to arrange the tournament finalists in such a way that her sweetheart wins the tournament, considering that both players play optimally. However, the initial location of the participants has already been announced, and we can only pull some strings and determine which participant will be first and which one will be second. But how do we know which participant can secure the victory? Alas, the princess is not learned in the military affairs... Therefore, she asks you to determine how the battle will end considering that both opponents play optimally. Also, if the first player wins, your task is to determine his winning move.
平地王国的国王将举办一场骑士比武大赛!获胜者将获得王国的一半领土,以及那位以绝世美貌与非凡智慧闻名的公主的垂青。对参赛者勇气与力量的最终考验,是一场击剑比赛。比赛遵循如下规则:参赛者两两对决,胜者(更准确地说,是幸存者)晋级下一轮。
对决开始前,双方选手站在 Ox 轴上指定的整数坐标点处。随后他们轮流行动,自然由第一位选手先手。在一次行动中,第一位选手可从当前点 x 移动至区间 [x+a,x+b] 内任意一个整数点;第二位选手则可在其行动中移动至区间 [x−b,x−a] 内任意一个整数点。即两位选手的可行移动范围具有对称性(注意:a 与 b 不必为正数;若 a≤0≤b,则停留在原地也是一种合法的移动)。在任意时刻,双方选手相对于彼此的位置可以是任意的,也就是说,允许朝任意方向“跃过”对手。若某位选手在自己的回合中恰好移动到对手所在位置,则该选手获胜。
当然,公主早已选定夫婿,如今她希望心上人赢得本次大赛。他已成功闯入决赛,即将迎来最后一战。公主请求赛事主管安排决赛对阵方式,使得她的心上人能够获胜——前提是双方均采取最优策略。然而,双方选手的初始位置业已公布,我们唯一能暗中操作的是:决定哪位选手作为第一位选手、哪位作为第二位选手。但究竟谁能确保获胜呢?唉,公主不通军事谋略……因此,她请你判断:在双方均采取最优策略的前提下,这场对决将如何结束?此外,若第一位选手获胜,请你指出他的制胜一步。
输入格式
The first line contains four space-separated integers — _x_1, _x_2, a and b (_x_1 ≠ _x_2, a ≤ b, - 109 ≤ _x_1, _x_2, a, b ≤ 109) — coordinates of the points where the first and the second participant start, and the numbers that determine the players' moves, correspondingly.
第一行包含四个以空格分隔的整数:x1、x2、a 和 b(满足 x1=x2,a≤b,且 −109≤x1,x2,a,b≤109),分别表示第一位和第二位参与者起始位置的坐标,以及决定玩家移动方式的两个数。
输出格式
On the first line print the outcome of the battle as "FIRST" (without the quotes), if both players play optimally and the first player wins. Print "SECOND" (without the quotes) if the second player wins and print "DRAW" (without the quotes), if nobody is able to secure the victory.
If the first player wins, print on the next line the single integer x — the coordinate of the point where the first player should transfer to win. The indicated move should be valid, that is, it should meet the following condition: _x_1 + a ≤ x ≤ _x_1 + b. If there are several winning moves, print any of them. If the first participant can't secure the victory, then you do not have to print anything.
第一行输出战斗结果:“FIRST”(不带引号),表示双方均采取最优策略时先手获胜;输出“SECOND”(不带引号),表示后手获胜;输出“DRAW”(不带引号),表示双方均无法确保获胜。
若先手获胜,则在下一行输出一个整数 x —— 先手为获胜应转移至的点的坐标。该移动必须合法,即需满足条件:x1 + a ≤ x ≤ x1 + b。若存在多个获胜移动,输出任意一个即可。若先手无法确保获胜,则无需输出任何内容。
输入输出样例
输入#1
0 2 0 4
输出#1
FIRST 2
输入#2
0 2 1 1
输出#2
SECOND
输入#3
0 2 0 1
输出#3
DRAW
说明/提示
In the first sample the first player can win in one move.
In the second sample the first participant must go to point 1, where the second participant immediately goes and wins.
In the third sample changing the position isn't profitable to either participant, so nobody wins.
在第一个样例中,先手玩家可以在一步内获胜。
在第二个样例中,先手参与者必须移动到点 1,此时后手参与者立即移动至此并获胜。
在第三个样例中,改变位置对任意参与者均无利可图,因此无人获胜。
输入解题思路,AI测评打分。不知道怎么写?