SwitchingGame

TCO14 Round 2B · 2014-03-26 · by tourist

TCO14 Round 2B · 2014-03-26 · by tourist · Greedy

Show categories

Class Name: SwitchingGame

Return Type: int

Method Name: timeToWin

Arg Types: (vector<string>)

Problem Statement

You're playing a game with lamps. There are M lamps in a row. The lamps are numbered 0 through M-1. Initially, all lamps are turned off.

The game consists of N levels. The levels are numbered 0 through N-1. Each level is described by a string of M characters. For each i, character i of that string gives the required state of lamp i. Each of these characters will be either '+', '-', or '?'. Here, '+' means that the lamp must be on, '-' means that the lamp must be off, and '?' means that the lamp may be in either state.

The game is played in turns. Each turn takes one second. In each turn, you may do one of three things:

You may choose any subset of lamps that are all turned off, and turn all of them on.
You may choose any subset of lamps that are all turned on, and turn all of them off.
You may press the big red button that says "Check!".

Whenever you press the button, the current states of all lamps are checked against the requirements of the current level. If all lamps satisfy the requirements, you solved the current level. You win the game by solving all N levels. You must solve the levels in the given order, starting with level 0. Note that the lamps do not reset between levels: you continue playing the next level from the state you had when you solved the previous level.

Return the smallest number of seconds it takes to win the game if you play optimally.

Constraints

states will contain exactly N elements.
N will be between 1 and 50, inclusive.
Each element of states will contain exactly M characters.
M will be between 1 and 50, inclusive.
Each character of states will be '+', '-' or '?'.

Examples

{"++--",
 "--++"}
Returns: 5

The following sequence of actions wins the game in five seconds: Turn lamps 0 and 1 on. Press the button to win level 0. Turn lamps 0 and 1 off. Turn lamps 2 and 3 on. Press the button to win level 1 and thus win the game.

{"+-++",
 "+-++"}
Returns: 3

Each time you press the button you can only win a single level. Even though levels 0 and 1 are identical, you have to press the button twice in a row to win both of them.

{"++",
 "+?",
 "?+",
 "++"}
Returns: 5

Here we can simply turn both lamps on, and then use that configuration to win all four levels.

{"+", 
 "?",
 "?",
 "?",
 "-"}
Returns: 7

At some point between winning level 0 and winning level 4 we have to turn the lamp off.

{"+??++++?+++++++++", "++?++++++++++++?+", "?+?++++++++-++++?", "+++?+++++?++++--+", "+??++++++?++-++++", "?++?+?+++++++++++", "+-++++?++++?+++++", "++?++?+++++++++++", "++?++++++?+++++?-", "+++++++++++-+++++", "++++++++++++++++-", "-++++?+?+++++++?+", "+???+++++++++++++", "+++++++++++++?+++", "++-++++??++++++++", "+?++++++++++?++++", "++++++++++++-+++?", "+++++???++++++?++", "+++?++++++?++++++", "++++-+++?++++++++", "+++++-++++++?++++", "+++++++-+++-+?+++", "++++?+-++++++++++", "?++++++++++++++++", "+++?++++++++?++++", "+++++?++++++++++?", "+++?++++++++++++?", "++++?++++++++++++", "+?+++++?+?++-++++", "+++?+++++++++++++", "+++++++++++++++++", "+++++++++++++?+?+", "+++-++++++++?++++", "++++?++++??+++?++", "?+--++-++++-?++++", "+-+++++++?+++++++", "+?-?+++++++?+++?+", "+++?+++++++?+++++", "+++?++++??+++++++"}
Returns: 77

Submissions are judged against all 200 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SwitchingGame with a public method int timeToWin(vector<string> states) · 200 test cases · 2 s / 256 MB per case