A Coin Game
Description
Harry and Sally have recently got addicted to a coin game. The game goes as follows.
The games uses a T × T grid board, each square in which is denoted by a pair of integers (x, y) between 1 and T (inclusive). Two players take turns to flip the coins. Each turn a player can choose four coins in the squares (x1, y1), (x1, y2), (x2, y1) and (x2, y2) (1 ≤ x1 < x2 ≤ T, 1 ≤ y1 < y2 ≤ T) to flip, as long as the coin in (x2, y2) will be turned from heads to tails. The player who cannot make a move loses.
After a sweet winning streak, Harry says to Sally, “Let’s have a bet! I’ll play first, and I’ll put heads in some squares and tails in some others of the board. You can decide whether the rest of coins shows heads or tails. I dare say you can’t beat me no matter how you put them.”
Given the squares in which Harry puts heads and those in which he puts tails, can you help Sally decide on the rest of coins so that she will win to teach the arrogant Harry a lesson? Assume that both Harry and Sally play optimally in the game.
Input
The input contains multiple test cases. Each test cases begins with a line containing two integers n1 and n2 (n1, n2 ≤ 200). The next n1 + n2 lines each contain a pair of integers (x, y) (1 ≤ x, y ≤ 100). For the first n1 pairs, Harry puts heads in the corresponding squares. Harry lets Sally decide on coins in the squares denoted by the rest n2 pairs and puts tails in other squares.
Output
For each test case, if Sally can win the game, print “Yes”, followed by n2 letters being either “H” (heads) or “T” (tails), showing one way (possibly among others) she put the coins. The output should be in the same order as the squares appear in the input. If Sally cannot win, just print “No”.
Sample Input
0 4
1 1
1 2
2 1
2 2
1 1
1 1
2 2
Sample Output
Yes
T
T
T
T
Yes
T
 点赞
 写回答
 关注问题
 收藏
 复制链接分享
 邀请回答
2条回答

采纳
点赞 评论 复制链接分享

采纳
这个我源代码我写过，只要想清楚整个过程，如何必胜，代码实现起来就很容易实现了。
点赞 评论 复制链接分享
相关推荐
 4年前回答 2 已采纳 Description Harry and Sally have recently got addicted to a coin game. The game goes as follows. The games uses a T × T grid board, each square in which is denoted by a pair of integers (x, y) between 1 and T (inclusive). Two players take turns to flip the coins. Each turn a player can choose four coins in the squares (x1, y1), (x1, y2), (x2, y1) and (x2, y2) (1 ≤ x1 < x2 ≤ T, 1 ≤ y1 < y2 ≤ T) to flip, as long as the coin in (x2, y2) will be turned from heads to tails. The player who cannot make a move loses. After a sweet winning streak, Harry says to Sally, “Let’s have a bet! I’ll play first, and I’ll put heads in some squares and tails in some others of the board. You can decide whether the rest of coins shows heads or tails. I dare say you can’t beat me no matter how you put them.” Given the squares in which Harry puts heads and those in which he puts tails, can you help Sally decide on the rest of coins so that she will win to teach the arrogant Harry a lesson? Assume that both Harry and Sally play optimally in the game. Input The input contains multiple test cases. Each test cases begins with a line containing two integers n1 and n2 (n1, n2 ≤ 200). The next n1 + n2 lines each contain a pair of integers (x, y) (1 ≤ x, y ≤ 100). For the first n1 pairs, Harry puts heads in the corresponding squares. Harry lets Sally decide on coins in the squares denoted by the rest n2 pairs and puts tails in other squares. Output For each test case, if Sally can win the game, print “Yes”, followed by n2 letters being either “H” (heads) or “T” (tails), showing one way (possibly among others) she put the coins. The output should be in the same order as the squares appear in the input. If Sally cannot win, just print “No”. Sample Input 0 4 1 1 1 2 2 1 2 2 1 1 1 1 2 2 Sample Output Yes T T T T Yes T
 5年前回答 1 已采纳 Description Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 3, we use c1, c2, ..., cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.) Suppose that both Alice and Bob do their best in the game. You are to write a program to determine who will finally win the game. Input There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 10 6). There are no blank lines between cases. A line with a single 0 terminates the input. Output For each test case, if Alice win the game,output "Alice", otherwise output "Bob". Sample Input 1 2 3 0 Sample Output Alice Alice Bob
 回答 1 已采纳 Problem Description Alice and Bob play a random turn connection game in a square board with 8×8 cells. In each move, a player tosses a fair coin to decide who gets the move. That is, both Alice and Bob will get the next move with 50% chance, no matter who has moved before. Once a player gets a move, she will place a piece in an empty cell. Both Alice and Bob play randomly. That is, if there are k empty cells, each cell will be chosen with 1/k chance. Once Alices pieces connect the top side and the bottom side of the board, she will win the game. Similarly, once Bobs pieces connect the left side and the right side of the board, he will win the game. Pieces only connect horizontally or vertically, and cannot connect diagonally. Your task is to calculate the winning probabilities of Alice and Bob. Input The first line is the number of test cases. Each test case contains 8 lines and each line contains 8 characters, representing the current status of the board. The cells occupied by Alice are marked as “A”, the cells occupied by Bob are marked as “B”, and the empty cells are marked as “.”. There is an empty line between test cases. Output For each test case, output the probability that Alice and Bob will win with the precision of 6 digits. Sample Input 4 ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... BBBB.BBB ....A... ....A... ....A... ....A... ....A... ....A... BBBBA... ...ABBBB ...A.... ...A.... ...A.... ........ ........ ........ ........ ........ ........ ........ .......A Sample Output Alice 1.000000 Bob 0.000000 Alice 0.500000 Bob 0.500000 Alice 0.000000 Bob 0.000000 Alice 0.223093 Bob 0.198498
 4年前回答 1 已采纳 Problem Description Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the leftunderneath blank space.The person who can't make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game? Input Input contains multiple test cases. Each line contains two integer n, m (0<n,m<=2000). The input is terminated when n=0 and m=0. Output If kiki wins the game printf "Wonderful!", else "What a pity!". Sample Input 5 3 5 4 6 6 0 0 Sample Output What a pity! Wonderful! Wonderful!
 回答 1 已采纳 Problem Description You are given N baskets of gold coins. The baskets are numbered from 1 to N. In all except one of the baskets, each gold coin weighs w grams. In the one exceptional basket, each gold coin weighs wd grams. A wizard appears on the scene and takes 1 coin from Basket 1, 2 coins from Basket 2, and so on, up to and including N1 coins from Basket N1. He does not take any coins from Basket N. He weighs the selected coins and concludes which of the N baskets contains the lighter coins. Your mission is to emulate the wizard's computation. Input The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins. N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w. Output For each instance of the problem, your program will produce one line of output, consisting of one positive integer: the number of the basket that contains lighter coins than the other baskets. Sample Input 10 25 8 1109 10 25 8 1045 8000 30 12 959879400 Sample Output 2 10 50
 To Bet or Not To Bet less4年前回答 1 已采纳 Description Alexander Charles McMillan loves to gamble, and during his last trip to the casino he ran across a new game. It is played on a linear sequence of squares as shown below. ![](http://poj.org/images/1644_1.jpg) A chip is initially placed on the Start square. The player then tries to move the chip to the End square through a series of turns, at which point the game ends. In each turn a coin is fl ipped: if the coin is heads the chip is moved one square to the right and if the coin is tails the chip is moved two squares to the right (unless the chip is one square away from the End square, in which case it just moves to the End square). At that point, any instruction on the square the coin lands on must be followed. Each instruction is one of the following: 1. Move right n squares (where n is some positive integer) 2. Move left n squares (where n is some positive integer) 3. Lose a turn 4. No instruction After following the instruction, the turn ends and a new one begins. Note that the chip only follows the instruction on the square it lands on after the coin flip. If, for example, the chip lands on a square that instructs it to move 3 spaces to the left, the move is made, but the instruction on the resulting square is ignored and the turn ends. Gambling for this game proceeds as follows: given a board layout and an integer T, you must wager whether or not you think the game will end within T turns. After losing his shirt and several other articles of clothing, Alexander has decided he needs professional helpnot in beating his gambling addiction, but in writing a program to help decide how to bet in this game. Input Input will consist of multiple problem instances. The first line will consist of an integer n indicating the number of problem instances. Each instance will consist of two lines: the first will contain two integers m and T (1 <= m <= 50, 1 <= T <= 40), where m is the size of the board excluding the Start and End squares, and T is the target number of turns. The next line will contain instructions for each of the m interior squares on the board. Instructions for the squares will be separated by a single space, and a square instruction will be one of the following: +n, n, L or 0 (the digit zero). The first indicates a right move of n squares, the second a left move of n squares, the third a loseaturn square, and the fourth indicates no instruction for the square. No right or left move will ever move you off the board. Output Output for each problem instance will consist of one line, either Bet for. x.xxxx if you think that there is a greater than 50% chance that the game will end in T or fewer turns, or Bet against. x.xxxx if you think there is a less than 50% chance that the game will end in T or fewer turns, or Push. 0.5000 otherwise, where x.xxxx is the probability of the game ending in T or fewer turns rounded to 4 decimal places. (Note that due to rounding the calculated probability for display, a probability of 0.5000 may appear after the Bet for. or Bet against. message.) Sample Input 5 4 4 0 0 0 0 3 3 0 1 L 3 4 0 1 L 3 5 0 1 L 10 20 +1 0 0 1 L L 0 +3 7 0 Sample Output Bet for. 0.9375 Bet against. 0.0000 Push. 0.5000 Bet for. 0.7500 Bet for. 0.8954
 回答 1 已采纳 Problem Description Mr. Sheep lost himself in a computer game. In this game, he plays the part of a super hero and fight with the evil. The equipment is very important in this game and Mr. Sheep thinks the Quelling Blade is the most powerful weapon. In this game, each type of weapon costs hero some money, and brings the hero benefits. If the hero buys two weapons (no matter they have the same type or not), the benefit values are accumulated. That is to say, if the hero buys two weapons with benefit 3 and 5, the hero will get total benefit value 8=3+5. There are some requirements for each weapon. If the hero wants to buy a certain weapon, he may need some other weapons first. For example, if hero wants to buy a “Divine Rapier”, he needs a “Demon Edge” and a “Scared Relic”. Of course, if he wants to buy the second “Devine Rapier”, he must buy another “Demon Edge” and another “Scared Relic” first. Notice that the existing weapon will not disappear after the trade. Note that a weapon may need multiple weapons with same type. And you may assume that a type of weapon is required by at most one other type of weapon. The hero is busy with combat and has no time to earn money. Fortunately, the game will give the hero 1 coin per second. So if the hero wants to buy a “Quelling Blade”, the minimum total time for him to achieve his goal can be easily calculated. Mr. Sheep is a perfectionist. He not only wants to get the “Quelling Blade” as soon as possible, but also wants to optimize every second during the game. He defines the utility of the game as the sum of the benefit value of the hero in each second. He calculates the utility from the start of the game until the second he gets “Quelling Blade”, exclusively. You may refer to the samples for further clarification. In the other words, you should define a way of process to buy the weapons for the hero, which minimize the total time to get “Quelling Blade” and optimize the utility of the game. Input There are hundreds of test cases, the number of test case are in the first line of the input. Notice that most of the test cases are relatively small. For each test case, the first line contains a single integer N denoting the number of different types of weapons. (1 <= N <= 1000) The next lines are describing the weapons. For each weapon, the first line contains two integers B and C, denoting the benefit value and the cost of this kind of weapon. (1 <= B, C <= 2^311) Then a single integer P in the next line describes the number of requirements of this weapon. Next P lines, each line contains two integers I and A, means that this weapon needs A weapons of index I. The indexes of weapons are start from 1 to N. The “Quelling Blade” is the first type of weapon. And you may assume that the total numbers of weapons which are needed by the “Quelling Blade” is less than 1000000. Also notice that “Quelling Blade” can be brought in a finite game time and a type of weapon can be required by at most one other type of weapon. Output For each test case, output a single integer denoting the optimal utility. You may assume that the answer is fit in 64bit signed integer. Sample Input 2 3 1 1 1 2 2 2 1 1 3 1 1 1 0 3 1 1 1 2 2 1 1 1 3 1 2 1 0 Sample Output Case #1: 14 Case #2: 17
 4年前回答 1 已采纳 问题描述 : Mr. Sheep lost himself in a computer game. In this game, he plays the part of a super hero and fight with the evil. The equipment is very important in this game and Mr. Sheep thinks the Quelling Blade is the most powerful weapon. Revenge of Fibonacci In this game, each type of weapon costs hero some money, and brings the hero benefits. If the hero buys two weapons (no matter they have the same type or not), the benefit values are accumulated. That is to say, if the hero buys two weapons with benefit 3 and 5, the hero will get total benefit value 8=3+5. There are some requirements for each weapon. If the hero wants to buy a certain weapon, he may need some other weapons first. For example, if hero wants to buy a “Divine Rapier”, he needs a “Demon Edge” and a “Scared Relic”. Of course, if he wants to buy the second “Devine Rapier”, he must buy another “Demon Edge” and another “Scared Relic” first. Notice that the existing weapon will not disappear after the trade. Note that a weapon may need multiple weapons with same type. And you may assume that a type of weapon is required by at most one other type of weapon. The hero is busy with combat and has no time to earn money. Fortunately, the game will give the hero 1 coin per second. So if the hero wants to buy a “Quelling Blade”, the minimum total time for him to achieve his goal can be easily calculated. Mr. Sheep is a perfectionist. He not only wants to get the “Quelling Blade” as soon as possible, but also wants to optimize every second during the game. He defines the utility of the game as the sum of the benefit value of the hero in each second. He calculates the utility from the start of the game until the second he gets “Quelling Blade”, exclusively. You may refer to the samples for further clarification. In the other words, you should define a way of process to buy the weapons for the hero, which minimize the total time to get “Quelling Blade” and optimize the utility of the game. 输入: There are hundreds of test cases, the number of test case are in the first line of the input. Notice that most of the test cases are relatively small. For each test case, the first line contains a single integer N denoting the number of different types of weapons. (1 <= N <= 1000) The next lines are describing the weapons. For each weapon, the first line contains two integers B and C, denoting the benefit value and the cost of this kind of weapon. (1 <= B, C <= 2^311) Then a single integer P in the next line describes the number of requirements of this weapon. Next P lines, each line contains two integers I and A, means that this weapon needs A weapons of index I. The indexes of weapons are start from 1 to N. The “Quelling Blade” is the first type of weapon. And you may assume that the total numbers of weapons which are needed by the “Quelling Blade” is less than 1000000. Also notice that “Quelling Blade” can be brought in a finite game time and a type of weapon can be required by at most one other type of weapon. 输出: There are hundreds of test cases, the number of test case are in the first line of the input. Notice that most of the test cases are relatively small. For each test case, the first line contains a single integer N denoting the number of different types of weapons. (1 <= N <= 1000) The next lines are describing the weapons. For each weapon, the first line contains two integers B and C, denoting the benefit value and the cost of this kind of weapon. (1 <= B, C <= 2^311) Then a single integer P in the next line describes the number of requirements of this weapon. Next P lines, each line contains two integers I and A, means that this weapon needs A weapons of index I. The indexes of weapons are start from 1 to N. The “Quelling Blade” is the first type of weapon. And you may assume that the total numbers of weapons which are needed by the “Quelling Blade” is less than 1000000. Also notice that “Quelling Blade” can be brought in a finite game time and a type of weapon can be required by at most one other type of weapon. 样例输入: 2 3 1 1 1 2 2 2 1 1 3 1 1 1 0 3 1 1 1 2 2 1 1 1 3 1 2 1 0 样例输出: Case #1: 14 Case #2: 17
 9年前andro_wei的博客 Suppose you play the following game with your opponent: There is a sequence of n coins with values v[1], v[2], …, v[n] in a queue which are known in advance. Now each player takes alternate turn to ...
 ShinyaLicone的博客 Farmer John's cows like to play coin games so FJ has invented with a new twoplayer coin game called Xoinc for them. Initially a stack of N (5 ,000) coins sits on the ground; coin i from the top ...
 weixin_30287169的博客 Farmer John's cows like to play coin games so FJ has invented with a new twoplayer coin game called Xoinc for them. Initially a stack of N (5 ,000) coins sits on the ground; coin i from the top has...
 weixin_34023982的博客 scanf("%d",&a[i]); } for(int i=1;i;i++) { s[i]=s[i1]+a[i]; } for(int i=1;i;i++) { for(int j=1;j;j++) { f[i][j]=f[i][j1]; if(2*j1) { f[i][j]=max(f[i][j],s[i]f[i2*j+1][2*j1]); } if...
 妖怪吧的博客 Farmer John’s cows like to play coin games so FJ has invented with a new twoplayer coin game called Xoinc for them. Initially a stack of N (5 &lt;= N &lt;= 2,000) coins sits on the ground; ...
 yzyyylx的博客 题面 题意 有一叠硬币，每个硬币有一个币值，双方轮流操作，每个人至少取一枚硬币，最多取上一个人取的数量的两倍（第一个人最多取1枚），问先手至多能得到的硬币币值之和为多少。 做法 首先定义状态dp[i][j]dp[i][j...
 largecub233的博客 i++)a[i]=a[i 1 ]+a[i]; for ( int i= 1 ;i;i++) for ( int j= 1 ;j;j++){ f[i][j]=f[i][j 1 ]; int k=j* 2 ; if (i>=k)f[i][j]=max(f[i][j],a[i]f[ik][k]); k=j* 2  1 ; if (i>=k)f[i][j]=max...
 sdfzyhx的博客 Farmer John’s cows like to play coin games so FJ has invented with a new twoplayer coin game called Xoinc for them. Initially a stack of N (5 ,000) coins sits on the ground; coin i from ...
 donname的博客 这道题和A Game类似，我们用dp[i][j]表示当剩下i枚硬币且上一次拿硬币的人取走了j枚硬币时可以取得的最大价值,（下列说明默认不超出范围）dp[i][j]状态下,可以取(k=ni+1)k,k+1,k+2…k+2j1,dp[i][j1]状态下,可以取...
 Farmer_ZY的博客 Farmer John's cows like to play coin games so FJ has invented with a new twoplayer coin game called Xoinc for them. Initially a stack of N (5 The first player starts the game by taking the top one
 Reversing的博客 Coin Game Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d &amp; %I64uDescription After hh has learned how to play Nim...
 3年前weixin_30814223的博客 Problem Description ...After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.The game goes like this:Two players start the game with a circle of n c...