## DMOPC '14 Contest 3 P5 - Not Enough Servers!

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Amagi Brilliant Contests runs a business making and hosting contests on its online platform for competitive programmers who want to run their own contests.

On their most recent contest, submissions were queued for unreasonably long times. The investigation that followed concluded that ABC needs to acquire more servers for their next contest. However, since ABC is not doing so well, they have no money to buy new servers with. Instead, the management has decided to cut out some test cases from the problems.

Cutting out test cases is a process that needs to be handled with care. The process involves removing a subset of test cases from the original cases of a problem (numbered from to ). The test cases that are left have to satisfy three conditions:

1. All users who would have gotten AC for all cases should still get AC for all cases with the new test cases.
2. All users who would not have gotten AC for all cases should not get AC for all cases with the new test cases.
3. There should be at least 1 test case.

Amagi Brilliant Contests has collected some data from problem testers on a problem they're planning to use on their next contest. Each tester submitted exactly one submission, and the verdict for each test case of a submission will either be O for AC or X for anything other than AC. Amagi Brilliant Contests believes that the data from these submissions should represent real contestants to a reasonable degree.

You are the head of the quality assurance department at Amagi Brilliant Contests, and so you have been tasked with selecting a minimal sized set of test cases such that they satisfy the three conditions above.

#### Constraints

There will be a number of subtasks for this problem:

Test Case BatchPoints (%)Constraints
120
210

Additionally, each submission will have exactly 1 test case where it did not receive an AC verdict.
310
410
515
635

#### Input Specification

The first line of input will have , separated by a single space.

The next lines will each contain the results of a single submission.

The character (the first character has index 1) of each of these lines will be O if test case received an AC verdict; otherwise it will be X. There are no spaces between the characters.

#### Output Specification

The first line of output should be the minimal number of test cases to keep in the final set of test cases, .

The second line of output should consist of space-separated pairwise distinct integers between and , inclusive, the set of test cases to keep in the final set of test cases. If there are multiple possible solutions, you may output any of those. The numbers of test cases to keep may be listed in any order.

Your score for a test case will be

• 0, if your output is formatted incorrectly or the is incorrect
• 40% of the full marks, if the first line of output, , is correct, but the rest of the output is either formatted incorrectly or incorrect
• 100% of the full marks, if the first line of output, , is correct and the second line of output is a correct final set of test cases

#### Sample Input 1

2 4
XOOX
OXXX

#### Sample Output 1

1
4

#### Explanation for Sample Output 1

Both submissions should not get AC, and test case is successful in failing both submissions.

#### Sample Input 2

2 4
OOOO
XOOX

#### Sample Output 2

1
1

#### Explanation for Sample Output 2

Since the first submission should get AC and the second submission should not, choosing the first test case will pass the first submission and fail the second submission. Another valid solution is choosing the fourth test case.

#### Sample Input 3

3 4
OOOO
XOOX
OXOO

#### Sample Output 3

2
2 4

#### Explanation for Sample Output 3

Choosing cases and is also a valid solution. and are the only two valid solutions.