DMOPC '22 Contest 1 P4 - Card Game

View as PDF

Points: 12 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

You are playing a card game with an opponent. Your opponent will draw cards and insert them into their hand one by one. Each of these cards has a value between and , chosen uniformly at random and independent of the other cards.

Having played this game many times against this opponent, you realize that they always insert these cards in a highly predictable way. For each card, your opponent inserts it into their hand so that their hand remains sorted in nondecreasing order, and this new card is inserted before all occurrences of the same value.

You carefully observe that your opponent inserted the -th card at position . That is, there were cards before the position that the -th card was inserted in when the -th card was inserted.

From this information, can you guess the number of times each value appears in your opponent's hand? You will play games in each file, and you only need to be correct in enough games.

Constraints

Each subtask contains exactly test files. Every test case is generated from a sequence of card values that are integers between and , chosen uniformly at random and independent of the other card values.

You do not need to pass any previous subtasks to be judged on a subtask.

You do not have to correctly answer all test cases to get full points in this subtask. Please check the Scoring section for more details.

Input Specification

The first line contains space-separated integers: , , and .

The next lines each contain space-separated integers: The positions in a single test case.

Output Specification

Output lines, each containing space-separated integers. The -th integer on a line should represent the number of times you guess that a card with value appears in your opponent's hand in that test case.

Scoring

For each test file:

If you do not output exactly lines, each containing space-separated integers between and , you will receive a score of for that file and a Wrong Answer verdict.

Otherwise, each of the test cases will be graded as correct if the sequence you produced exactly matches the sequence of card frequencies that was generated. Your score for the test file is determined as follows:

• In subtasks and , you will receive full points if you answer of the cases correctly and points otherwise. You will receive a Wrong Answer verdict if you did not answer of the cases correctly.
• In subtask , suppose you answered of the cases correctly. Your score will be calculated as:

In particular, you will receive full points if you answer at least of the cases correctly.

Your final score within a subtask will be the minimum score over all test files.

Sample Input

5 3 2
0 1 2 1 3
0 0 0 0 0

Sample Output

1 2 2
3 0 2

Explanation

This sample input does not satisfy the constraints for any subtask and is only provided to clarify the input and output format.

In the first case, it is possible to uniquely determine that the sequence of card values was , so the card counts are .

In the second case, one possible sequence of card values is , giving card counts of . Note that we cannot uniquely determine the card counts; for example, giving card counts of is also possible. This case will be graded as correct only if you correctly guessed the exact card frequencies that were generated, so is a reasonable guess.