시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 | 256 MB | 51 | 26 | 25 | 69.444% |
JOI is a baby playing with a rope. The rope has length N, and it is placed as a straight line from left to right. The rope consists of N cords. The cords are connected as a straight line. Each cord has length 1 and thickness 1. In total, M colors are used for the rope. The color of the i-th cord from left is Ci (1 ≤ Ci ≤ M).
JOI is making the rope shorter. JOI repeats the following procedure until the length of the rope becomes 2.
JOI wants to minimize the total cost of procedures to shorten the rope until it becomes length 2. For each color, JOI wants to calculate the minimum total cost of procedures to shorten the rope so that the final rope of length 2 contains a cord with that color.
Your task is to solve this problem instead of JOI.
Given the colors of the cords in the initial rope, write a program which calculates, for each color, the minimum total cost of procedures to shorten the rope so that the final rope of length 2 contains a cord with that color.
Read the following data from the standard input.
Write M lines to the standard output. The c-th line (1 ≤ c ≤ M) contains the minimum total cost of procedures to shorten the rope so that the final rope of length 2 contains a cord with color c.
All input data satisfy the following conditions.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | N ≤ 15, M ≤ 10. |
2 | 30 | N ≤ 100 000, M ≤ 10. |
3 | 10 | N ≤ 100 000, M ≤ 500. |
4 | 25 | M ≤ 5 000. |
5 | 20 | There are no additional constraints. |
5 3 1 2 3 3 2
2 1 1
By the following procedures, we can shorten the rope so that the final rope of length 2 contains a cord with color 1. The total cost is 2.
By the following procedures, we can shorten the rope so that the final rope of length 2 contains a cord with color 2, 3. The total cost is 1.
7 3 1 2 2 1 3 3 3
2 2 2
By the following procedures, we can shorten the rope so that the final rope of length 2 contains a cord with color 1. The total cost is 2.
10 3 2 2 1 1 3 3 2 1 1 2
3 3 4
Before shortening the rope, we may change the colors of several cords.