Problem Statement | |||||||||||||
Imagine a game consisting of two billion doors (numbered starting at 1), behind some of which lie fabulous cash prizes. There are a limited number of patterns to the placement of the prizes, which the contestant knows in advance. All doors initially begin closed. Before the game begins, the host secretly selects one of the patterns from the list at random (all with equal probability), and puts prizes behind the doors specified by the pattern. For example, if the host chose the pattern "3-4 9 12-15", he would put prizes behind doors 3, 4, 9, 12, 13, 14, and 15 (and nowhere else). Two things happen every turn. First, the contestant decides which door is currently most likely to contain a prize, and secretly records this choice. (If two or more doors both have the greatest likelihood of containing a prize, he chooses the door with the lowest number.) The second part of a turn consists of the host opening one or more doors, all of which are revealed to be empty. For example, if the host gave the hint "2 7-10", this would indicate that he opened doors 2, 7, 8, 9, and 10 and there were no prizes behind any of them. In specific, the following grammar is used for this problem: <doors> ::= <range> | <range><sp><doors><range> ::= <num> | <num><to><num> (the first num must be strictly less than the second num) <num> ::= integer between 1 and 2000000000, inclusive, with no leading zeroes <sp> ::= ' ' <to> ::= '-' Given a String[] possible, containing the possible placements of prizes, and a String[] hints, the N hints given during the course of the game, your method should return a int[] containing N+1 elements. Each element should describe the most likely position of a prize at that point in the game. The first element represents your guess before any hints are given; the last element represents your guess taking every hint into account. Remember to break ties by choosing the lowest numbered door, if multiple doors are all the most likely. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | Each element of possible has an equal chance of being the pattern that is chosen by the host. This means that if one pattern appears on the list twice, it is twice as likely of being chosen as a pattern which appears on the same list only once. | ||||||||||||
Constraints | |||||||||||||
- | possible will contain between 2 and 50 elements, inclusive. | ||||||||||||
- | Each element of possible will contain between 1 and 50 characters, inclusive. | ||||||||||||
- | Each element of possible will conform to the rules of <doors>, as specified in the grammar above. | ||||||||||||
- | For each element of possible, the ranges contained therein will be non-overlapping and in ascending order. | ||||||||||||
- | hints will contain between 0 and 50 elements, inclusive. | ||||||||||||
- | Each element of hints will contain between 2 and 50 characters, inclusive. | ||||||||||||
- | Each element of hints will conform to the rules of <doors>, as specified in the grammar above. | ||||||||||||
- | For each element of hints, the ranges contained therein will be non-overlapping and in ascending order. | ||||||||||||
- | The information given in hints will always be consistent with at least one pattern in possible. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
|