回答 1 已采纳 Description
You are trying to set up a straight line of dominos, standing on end, to be pushed over later for your entertainment. (Sure, it seems pointless to set something up only to knock it down again, but you have some strange hobbies) The tricky thing about setting dominos, however, is that if you make a mistake and knock one over as you place it, it will knock down any adjacent line of consecutive dominos on one side of it, partially ruining your work.
For instance, if you've already placed dominos in the pattern DD__DxDDD_D, and you try placing a domino at position x, there is a chance it will fall and knock over the domino to the left or the three dominos to its right, forcing you to place them again.
This human error is somewhat unavoidable, but you can make the odds somewhat more favourable by using a domino-placing technique that leads to dominos falling in one direction more often than in the other.
Given the number of dominos you are trying to set up, and the probability that you'll knock over any individual domino either to the left or to the right while placing it, determine the average number of dominos you'll need to place before you finish. Assume that you're using an optimal placement strategy.
Input will consist of up to 100 cases. Each case consists of one line of input. It will contain the number of dominos to place, n, 1 <= n <= 1000, followed by nonnegative values Pl and Pr, indicating the probability of any domino falling to the left or to the right when placed. You may assume 0 < Pl + Pr <= 0.5.
The last test case is followed by a line containing a single 0.
For each case, output the expected number of dominos that will need to be placed before you finish, accurate to two digits after the decimal.
10 0.25 0.25
10 0.1 0.4
10 0.0 0.5
回答 2 已采纳 Do you know Utopia? It's a perfect world in which everyone leads a happy life.
A fairy wants to make a naive Utopia City. She studies the factors that have an impact on people's happiness and thinks that a person is happy if and only if all other persons' total "influence factor" on him (or her) is nonnegative. Each person has an influence factor on another person, which may be a positive integer or negative integer or 0. The influence factor is always symmetric, that is, if person A has an influence factor f on person B, it means that person B also has an "influence factor" f on A. So we can say the influence factor between person A and B is f without confusion. A person's influence factor on himself (or herself) is always 0. So let f(i, j) be the influence factor between person i and person j and person i's happiness(i) is well defined as follows:
Obviously there may be some persons who are not happy. Though the fairy cannot change any influence factor, she can give every person a property p(i) which is always +1 or -1. Under the fairy's magical definition, a person i's happiness(i)' is redefined as follow:
Person i feels happy if the value of happiness(i)' is nonnegative. But the fairy wonders whether she can give everyone a property to make all of them happy so that she can build her ideal naive Utopia successfully.
Since you're an ace programmer, the fairy asks you to help her to fulfill her dream. Can you help her?
The input contains multiple test cases!
Each test case starts with an integer N (2 <= N <= 200), the number of persons in the city. After that there're N lines of integers and each line consists of N integers. The j-th integer of the i-th line of the matrix indicates the influence factor f(i,j) (-1000 < f(i,j) < 1000).
Proceed to the End Of File (EOF).
For each test case, if the fairy fails, output a single line with "No" (without the quotations), otherwise output "Yes" (without the quotations) in the first line, followed by N lines, each line contains exactly a "+" (without the quotations) or a "-"(without the quotations) to indicate that the fairy should give the i-th person property +1 or -1 to fulfill her dream.
0 1 3
1 0 -1
3 -1 0
回答 1 已采纳 Description
A variation of the minesweeper game is available for almost every computer platform. Your employer wants to create yet another version that is targeted toward casual, as opposed to expert, players. Your task is to write a program that takes a minesweeper board and returns the minimum number of covered, unmined cells that remain after a casual player has tried his/her best. The details of the game and program are decribed below.
A minesweeper board consists of a rectangular grid of cells, with one or more cells containing a mine. The entire board is initially presented with all the cells covered, i.e., blank. The object of the game is to uncover all the cells that do not contain a mine. If a mine in uncovered, the game is over and the player loses. A cell can be in one of 3 states: covered, cleared/uncovered, or flagged as a mine.
When a player clears a cell that does not contain a mine, that cell displays the number of mines in cells that are adjacent to it. These numbers help the player determine where the mines are located. The adjacent cells are the cells that form a 3x3 square with the cleared cell in the center. Depending on a cell's location, it will have between 3 and 8 adjacent cells. The board in Figure 1 below shows two mines at locations (3,1) and (3,2), and the numbers of adjacent mines for each of the remaining cells.
A casual player makes use of this information in the following way. First the player selects one cell from a totally covered board. If it's a mine, the game is over. Otherwise, the player clears the cell and then applies the following two rules to cleared cells on the board until no further progress can be made. Let (x,y) be the location of a cleared cell, and let f, c, and m be the number of flagged, covered, and mined cells adjacent to (x,y).
If f = m, then clear all covered cells adjacent to (x,y).
If f + c = m, then flag all covered cells adjacent to (x,y).
Note that after successfully clearing the first cell, a casual player never clears or flags a cell except as dictated by rule 1 or 2, which means that the player may get "stuck". When a casual player is stuck, the game is over; no further guesses are made, and the player will not use more sophisticated rules that might allow him/her to safely clear additional cells.
Figure 2 below shows an application of these rules using the board from Figure 1.
Figure 2a shows the board after a player initially clears cell (1,2). Rule 1 applies, since (0 flagged = 0 mined neighbors), so the player clears the adjacent cells at (1,1), (1,3), (2,1), (2,2), and (2,3), which leads to Figure 2b.
From the board in Figure 2b, the player can consider cell (2,1) and apply rule 2 (0 flagged + 2 covered = 2 mined) to flag cells (3,1) and (3,2) as mines. This generates Figure 2c.
Finally, by looking at cell (2,3), the player can again apply rule 1 to clear cell (3,3), since cell (2,3) has exactly 1 adjacent mine, and cell (3,2) is already flagged as a mine. Now, all the cells without mines have been cleared, so the game stops with the player winning.
As indicated above, these two rules are not sufficient to solve every game board from every starting position, so the player might get stuck. Again, considering the board in Figure 1, if the player instead first cleared cell (2,2), the resulting board appears as Figure 3. The player cannot make any further progress, since neither rule 1 nor rule 2 clears or flags any new cells. In this case the player is stuck with 6 covered cells that do not contain mines.
You must write a program that looks at a game board and determines the smallest number of covered, unmined cells that could possibly remain when a casual player plays the game as described. For the game board in Figure 1, the answer is 0.
The input contains one or more game boards, followed by a final line containing only two zeros. A game board starts with a line containing two integers, r and c, the number of rows and columns in the game board; r and c will always be at least 3. The total number of cells in any board will never be greater than 40. The rest of the data set consists of a graphical representation of the game board, where an upper case 'M' represents a mine and a period '.' represents an empty cell. There will always be at least one 'M' and at least one '.' on each game board.
For each data set write one line with a single integer indicating the smallest number of covered, unmined cells for that board.