시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

3 초 | 512 MB | 0 | 0 | 0 | 0.000% |

Imagine that you are returning home from your first year at USC, to find that your father has died and your evil uncle (his brother) has married your mother. And soon after, your father’s ghost appears and tells you that your uncle actually murdered him. Oh, and in addition, you are the prince of Denmark, and your evil uncle is now the new king. That’s the start of the play Hamlet. Not surprisingly, Hamlet is a little upset at this, and thinks things through in his famous soliloquy:

To be, or not to be — that is the question:

Whether ’tis nobler in the mind to suffer

The slings and arrows of outrageous fortune

Or to take arms against a sea of troubles

And by opposing end them. [...]

Hamlet is thinking about possible courses of action, notably including suicide; he notes that there is a lot of uncertainty about the outcome, e.g., whether he would enjoy deep sleep (good outcome), or be tormented by horrible “dreams” in death (bad outcome). Similarly, at a later stage, Hamlet hears noise behind the curtain while talking to his mother. He stabs at the curtain, despite the uncertainty of who is there. Had it been his evil uncle, things could have ended pretty well; instead, it was the father of the woman he loves, who then proceeds to drown (in madness or suicide), a rather bad outcome. The problem is that Hamlet (like the rest of us) has to take lots of actions whose outcomes are uncertain. You are to help him optimize his choices, and thereby prevent an ending where everyone in the House of Denmark dies.

Specifically, you will be given a number of states that the plot (or Hamlet’s life) could be in, such as “beginning” or “Hamlet has chosen to kill himself and sleeps peacefully” or “Hamlet has chosen to kill himself and is tormented in hell” or “Hamlet has stabbed his uncle Claudius” or “Hamlet has stabbed Polonius and Ophelia has drowned.” A state can be the end of the story, in which case there is a value the state has. Otherwise, Hamlet has one or more actions available, and for each action, there is a distribution over other states that could result from this action. For instance, if Hamlet stabs the person behind the curtain, it may be Claudius with probability 40%, Polonius with probability 50%, and a random servant with probability 10%, leading to three corresponding new plot states. To keep this manageable, we assume that there can never be a cycle in the plot states. This will be enforced by numbering the plot states from 1 to n, and guaranteeing that for all actions, the probability of going from a higher to a lower or equal state is always 0.

As an example, suppose that Hamlet can choose whether or not to stab the curtain. If Claudius is behind the curtain, then the plot ends and Hamlet gets value +3. If a random servant is behind the curtain, the plot ends and Hamlet gets value -1. If Polonius is behind the curtain, then Ophelia will drown, and Laertes will challenge Hamlet to a fencing match, secretly poisoning his sword. If Hamlet accepts, they will both die, and the value is -10. If Hamlet rejects, then they may still both die because of poisoned wine (with probability 50%), or they both live, but Polonius and Ophelia are dead, giving value -5. Then, the value of stabbing the curtain is 40% · 3 + 10% · −1 + 50% ·(50% · −10 + 50% · −5) = −2.65. (Because if it turns out to be Polonius behind the curtain, Hamlet is better off rejecting Laertes’s challenge.) After calculating this, we could compare it to the value of not stabbing the curtain, which would follow a similar calculation.

The first line contains a number K ≥ 1, which is the number of input data sets in the file. This is followed by K data sets of the following form:

The first line of the data set contains one integer n with 1 ≤ n ≤ 1000, the number of plot states.

This is followed by n descriptions of plot points, as follows. For each plot point 1 ≤ i ≤ n, the first line is an integer 0 ≤ a_{i} ≤ 5. This is the number of actions Hamlet can choose from in state i. If a_{i} = 0, then the next line contains a double v_{i} ∈ [−1000, 1000], which is the value of the final outcome i. If a_{i} > 0, then there are a_{i} more lines, each line k containing n doubles p^{(k)}_{i,j} ∈ [0, 1], such that` Σ _{j}`p

For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, output the maximum expected value Hamlet can guarantee himself with a best possible strategy, rounded to two decimals.

Each data set should be followed by a blank line.

1 10 2 0 0.4 0.1 0.5 0 0 0 0 0 0 0 0.2 0 0.3 0.3 0 0 0 0.5 0 0 3.0 0 -1.0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0.5 0.5 3 0 0 0 0 0 0.6 0 0 0 0.4 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0.5 0 0.3 0.2 0 2 0 0 0 0 0 0 0.5 0.5 0 0 0 0 0 0 0 0 0.7 0 0.3 0 1 0 0 0 0 0 0 0 0 0.6 0.4 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 -5 0 -10

Data Set 1: -2.65