The Unofficial Mirror Contest of 19th Thailand Olympiad in Informatics Day 2
A. Energy
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

At Prof. TOI's prototype electric vehicle factory, the machine that manufactures electric vehicle parts has $$$2^K-1$$$ pieces, where $$$K$$$ is the number of layers in which the pieces are connected. Layer $$$K$$$ contains $$$2^{K-1}$$$ pieces. The first layer contains only one piece, numbered 1. Pieces in the next layers are numbered continually from the previous layer according to the connection scheme. That is, piece numbered $$$m$$$ is connected to pieces numbered $$$2m$$$ and $$$2m+1$$$ in the next layer.

Operating this machine requires cutting $$$N$$$ contiguous power cells into $$$2^{K-1}$$$ chunks to feed into all of the pieces in layer $$$K$$$. Each piece of the machine has a power value, which can be calculated as follows:

  • If the piece is in layer $$$K$$$, the power value is equal to the total value of energy cells fed into it
  • Each piece in layer $$$i$$$, that is not layer $$$K$$$, has the power value equal to the sum of the power values of the connected pieces in layer $$$i+1$$$ (in which there are 2 pieces). In order for the machine to operate properly, both pieces in layer $$$i+1$$$ that connects to the same piece in layer $$$i$$$ must have their power values differ by at most $$$D$$$.
For example, the machine that has 3 layers ($$$K=3$$$) has 4 pieces and in layer 3. Assume there are 13 power cells, as shown in Figure 1.
Figure 1 displays 13 power cells

In the case $$$D=5$$$, there are 4 possible methods of dividing the power cells to feed the machine, as shown in Figures 2-5.

Figure 2 displays method 1 of dividing power cells
Figure 3 displays method 2 of dividing power cells
Figure 4 displays method 3 of dividing power cells
Figure 5 displays method 4 of dividing power cells

Your Task

Write an efficient program to determine the total number of possible methods of dividing power cells according to the restrictions, giving the answer as the remainder when dividing the number by 1,000,000,007

Input

There are 2 lines of input:

Line 13 integers separated by a space.

The first integer is $$$N$$$, denoting the number of power cells.

The second integer is $$$K$$$, denoting the number of connected layers in the machine.

The third integer is $$$D$$$, denoting the largest difference of the power values for two pieces in layer $$$i+1$$$ that connects to the same piece in layer $$$i$$$ ($$$1\leq i\leq K−1$$$).

Let

  • $$$1\leq N\leq 300$$$
  • $$$1\leq K\leq 9$$$
  • $$$0\leq D\leq 1{,}000{,}000$$$
Line 2contains $$$N$$$ values of $$$A_j$$$, denoting the power value of power cell $$$j$$$, where $$$1\leq A_j\leq 1{,}000$$$, $$$1\leq j\leq N$$$.
Output

There is 1 line of output:

Line 11 integer denoting the total number of possible methods of dividing power cells. For every input, there is always at least 1 method of dividing power cells. Output the answer as the remainder when dividing the number by 1,000,000,007
Scoring

Notices regarding the test sets are as follows:

Test GroupMaximum attainable score in this groupCondition(s)
12$$$K=2$$$ and $$$N\leq 50$$$
23$$$K=3$$$ and $$$N\leq 50$$$
36$$$K=3$$$
417$$$2^{K-1}\leq N\leq 2^{K-1}+3$$$; that is, there are 3 more power cells than there are pieces at the bottom layer.
528$$$N\leq 50$$$
644No additional constraints
Examples
Input
13 3 5
8 7 4 2 8 5 3 5 2 5 3 7 7
Output
4
Input
14 2 6
1 1 2 1 2 3 1 2 1 2 3 4 2 1
Output
5
Note

Recommended programming tips

If the contestant uses cin/cout, it is recommended to add 2 lines as the following: 

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

B. Phitsanulok
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Miss Great TOI is a famous pageantry that seeks representatives from all provinces to compete at the national competition. For this, CEO Nawat Thattong personally holds the Miss Phit'lok competition to find the representative of Phitsanulok province. The top two competitors Nu-Kee and Non-Um are in a tight race. Nu-Kee wants to sabotage Non-Um by giving her a devious gift: a piece of fruit laced with poison. Non-Um has no choice but to accept and eat it out of politeness. Not wanting the situation to be extreme, Nu-Kee uses poison that only causes mild sickness. She also puts antidote in other pieces of fruit, just in case Non-Um is too ill to get on stage at all, she can play the role of a heroine. What a classic pageantry drama! It is so classic that other competitors also put poison and antidotes of multiple recipes in pieces of fruit at the pageantry, and therefore a piece of fruit may contain poison of more than 1 recipe and antidotes of more than 1 recipe. Nevertheless, Non-Um is experienced in the pageantry business, and she asks her mentor to find out which poison and antidotes are present in which pieces of fruit. The mentor advises Non-Um about the way to relief herself from poison as follows:

  1. When Non-Um eats whichever piece of fruit as the first piece, her body receives poison of all recipes that are put in that first piece of fruit. However, the antidotes in that piece of fruit has no effect on her body.
  2. Some pieces of fruit may only contain poison (1 recipe or more). Some may only contain antidote (1 recipe or more). Some may contain both poison and antidotes in the same piece of fruit, but no piece of fruit contains both the poison and the antidote of the same recipe, and it is possible that some piece of fruit contains neither poison nor antidotes.
  3. Among all pieces of fruit available at the pageantry, at least 1 piece of fruit contains no poison.
  4. To relief the effect of poison, the next piece of fruit she eats must contain antidote for all recipes of poison currently in effect. (It is OK to receive more antidote than needed.)
  5. When eating a piece of fruit with antidotes, the antidotes do not stay in the body and will not counter the effect of poison received from future pieces of fruit.
  6. When eating a piece of fruit with antidotes, if it also contains poison of other recipes, it is necessary to sequentially eat other pieces of fruit to relief herself from the new poison consumed.
  7. Non-Um needs to eat pieces of fruit to completely relief herself from poison so that the total weight is the smallest possible (not including the first piece of fruit with poison that she was handed).
  8. If it is impossible to find a sequence of pieces of fruit to relieve her from poisoning, Non-Um must notify the pageantry so that she can be sent to the expert Prof. TOI for immediate cure.
Note The situation in 8. above is undesirable to Nu-Kee, because it leads to investigation and the evidence can lead to her punishment.

The Miss Phit'lok pageantry war is full of twists and turns. At one point, Nu-Kee sees a text message sent to Non-Um to warn about the fiasco. Nu-Kee is now aware that Non-Um knows the way to relieves herself from poisoning, but Nu-Kee cannot find an alternate plan, so she remains committed to the plan to poison her opponent. However, she wants to choose a piece of fruit for Non-Um to eat so that, in order to cure the poisoning, she must consume other pieces of fruit in such a way that the total weight is as large as possible.

Example 1

Assume the pageantry has 5 pieces of fruit and 3 recipes of poison, with the details as shown in Table 1.

Table 1 displays the fruits, their weights, and the presence of poison/antidote in each piece of fruit within Example 1.
fruitweight (units)antidotepoison
recipe 1recipe 2recipe 3recipe 1recipe 2recipe 3
11---yesyes-
21yes-----
31-----yes
41--yes-yes-
51-yes-yes--
  • If Nu-Kee hands Non-Um fruit 3 for her to eat, Non-Um receives poison of recipe 3 immediately.
    • It is then necessary to eat fruit 4 that has antidote of recipe 3, but she consumes poison of recipe 2 in turn.
    • It is then necessary to eat fruit 5 that has antidote of recipe 2, but she consumes poison of recipe 1 in turn.
    • It is then necessary to eat fruit 2 that has antidote of recipe 1 which leads to complete relief.
    • Non-Um would consume fruits with the total weight of 1+1+1=3 units.
  • If Nu-Kee hands Non-Um fruit 4 for her to eat,Non-Um receives poison of recipe 2 immediately.
    • It is then necessary to eat fruit 5 that has antidote of recipe 2, but she consumes poison of recipe 1 in turn.
    • It is then necessary to eat fruit 2 that has antidote of recipe 1 which leads to complete relief.
    • Non-Um would consume fruits with the total weight of 1+1=2 units.
  • If Nu-Kee hands Non-Um fruit 1 for her to eat, which contains poison of recipe 1 and recipe 2, the next piece of fruit she eats must contain antidotes of both recipes. Therefore, it is impossible to find a sequence of pieces of fruit to eat that leads to complete relief, and the pageantry will be notified.

For the example above, Nu-Kee chooses to hand Non-Um fruit 3 for her to eat because Non-Um the fruits she must eat to get her to complete relief has the largest total weight.

Example 2

Assume the pageantry has 5 pieces of fruit and 3 recipes of poison, with the details as shown in Table 2.

Table 2 displays the fruits, their weights, and the presence of poison/antidote in each piece of fruit within Example 2.
fruitweight (units)antidotepoison
recipe 1recipe 2recipe 3recipe 1recipe 2recipe 3
11---yesyes-
23-yes----
34yesyes---yes
45yesyesyes---
57--yes---

If Nu-Kee hands Non-Um fruit 1 for her to eat, Non-Um receives poison of recipe 1 and recipe 2 immediately

  • If Non-Um chooses to eat fruit 3 that has antidote of recipe 1 and recipe 2, but she consumes poison of recipe 3 in turn.
    • It is then necessary to eat fruit 5 that has antidote of recipe 3 which leads to complete relief.
    • In this scenario, Non-Um would consume fruits with the total weight of 4+7 = 11 units.
  • If Non-Um chooses to eat fruit 4 that has antidote of recipe 1, recipe 2 and recipe 3, which leads to complete relief, Non-Um would consume fruits with the total weight of 5 units.
In this example, Non-Um chooses to eat fruit 4, because all the fruit that leads to her complete relief has the smallest total weight.

Your Task

Write an efficient program to determine, from the fruit data that contains the number of fruits, their weights, and the presence of poison/antidote in each piece of fruit, the total weight of fruit that Non-Um eats to complete relief herself, under the following conditions:

  • If none of the fruit at the pageantry contains poison, Nu-Kee may choose the fruit without poison to hand to Non-Um, but if there is a piece of fruit with poison, Nu-Kee chooses the piece of fruit that leads to Non-Um eating fruit with antidote with the highest total weight.
  • After Non-Um eats a piece of fruit with poison handed to her by Nu-Kee, Non-Um must eat pieces of fruit with antidote leading to complete relief with the smallest total weight.
Input

There are $$$N+1$$$ lines of input:

Line 12 integers, separated by a space.

The first integer is $$$N$$$, denoting the number of pieces of fruit, where $$$1\leq N\leq 80{,}000$$$.

The second integer is $$$S$$$, denoting the number of recipes of poison, where $$$1\leq S\leq 19$$$.

Line $$$i+1$$$ to $$$N+1$$$

for $$$i=1,\ldots,N$$$

$$$S+1$$$ integers, separated by a space.

The first integer is $$$w_i$$$, denoting the weight of fruit $$$i$$$ for $$$1\leq w_i\leq 1{,}000$$$.

Then, integer $$$p_i^j$$$ ($$$j=1,\ldots,S$$$) denotes that fruit $$$i$$$ contains poison or antidotes of which recipes, as follows:

  • $$$p_i^j=−1$$$ means fruit $$$i$$$ contains poisonof recipe $$$j$$$.
  • $$$p_i^j=0$$$ means fruit $$$i$$$ contains no poison and no antidote of recipe $$$j$$$.
  • $$$p_i^j=1$$$ means fruit $$$i$$$ contains antidote of recipe $$$j$$$.
Output

There is 1 line of output:

Line 11 integer denoting the total weight of fruit that is the smallest possible that Non-Um eats for complete relief under the condition that Nu-Kee chooses the piece of fruit with poison that leads to Non-Um eating pieces of fruit with antidote for complete relief with the largest total weight. If Non-Um does not receive a piece of fruit containing poison, answer 0.
Scoring

Notices regarding the test sets are as follows:

Test GroupMaximum attainable score in this groupCondition(s)
19$$$N\leq 8$$$
24Each piece of fruit containing poison has only 1 other piece of fruit that contains the matching antidote for it. Each piece of fruit contains an antidote for at most 1 other piece of fruit. In addition, $$$N\leq 200$$$
36Each piece of fruit containing poison has only 1 other piece of fruit that contains the matching antidote for it, except for one special piece of fruit that, for the poison in it, there are more than 1 piece of fruit that contains the antidote for it. However, it is still guaranteed that each piece of fruit contains an antidote for at most 1 other piece of fruit. In addition, $$$N\leq 200$$$
49$$$N\leq 5{,}000$$$ and every piece of fruit has weight 1
58$$$N\leq 700$$$
67$$$N\leq 1{,}500$$$
722$$$N\leq 5{,}000$$$
811$$$S\leq 12$$$
924No additional constraints
Examples
Input
4 2
5 0 1
6 -1 1
7 1 0
8 -1 -1
Output
7
Input
5 3
1 -1 -1 0
1 1 0 0
1 0 0 -1
1 0 -1 1
1 -1 1 0
Output
3
Note
  1. In Example 1, Nu-Kee hands Non-Um fruit 2, and Non-Um must eat fruit 3 for relief. The total weight of fruit Non-Um consumes is 7.
  2. In Example 2, Nu-Kee hands Non-Um fruit 3, and Non-Um must eat fruit 4, then fruit 5, then fruit 2 in order for relief. The total weight of fruit Non-Um consumes is 3.

Recommended programming tips

If the contestant uses cin/cout, it is recommended to add 2 lines as the following: 

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

C. Range
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After Prof. TOI has carried out a survey to promote tourism to a certain extent, he discovered that there is a place not far from the city of Phitsanulok that can be interestingly developed to become a natural tourist attraction. The tourist spot is located in Ban Mung, Noen Maprang, Phitsanulok which is considered to be an emerging tourist attraction. Its main attractions are the beautiful landscape and alternately overlapping limestone mountain range. With such a geological feature, it is suitable for sport climbing. Therefore, the villagers in that area have the idea to develop it into a new tourist attraction in the province by organizing a sport climbing competition at Ban Mung 2023 in order to publicize to the general public and give an opportunity for the visitors to challenge themselves by competing in climbing those mountains. The criteria to determine the winner is: the person who gets the highest score from climbing the mountain wins. In order to determine each scoring criteria appropriately, the score will be given based on the mountain that the contestant has climbed, where each mountain, when successfully climbed, gives a certain number of points that will be added to the previous score that the contestant has. The criteria for determining the points of each mountain is judged by the size and the complexity of that mountain. Therefore, the details of the scoring criteria for each mountain is as follows.

  1. Consider the mountain range by its front view on a 2-dimensional plane.
  2. The mountain range consists of various mountains, each represented by an isosceles triangle with $$$45^\circ$$$ angle at both sides of its base. Its vertices are located at $$$(L,0), (R,0)$$$, and $$$\left(\frac{R+L}{2},\frac{R-L}{2}\right)$$$, which can be represented as $$$[L, R]$$$ (as shown in Figure 1.)
  3. Two mountains can be related in the form of parent mountain and child mountain. The $$$i^\text{th}$$$ mountain is a parent mountain of the $$$j^\text{th}$$$ mountain and the $$$j^\text{th}$$$ is a child mountain of the $$$i^\text{th}$$$ mountain when $$$L_i \leq L_j \leq R_j \leq R_i$$$ where $$$[L_i,R_i]$$$ is the location of the $$$i^\text{th}$$$ mountain, and $$$[L_j, R_j]$$$ is the location of the $$$j^\text{th}$$$ mountain, and $$$[L_i, R_i]\neq [L_j, R_j]$$$
  4. A parent mountain can have more than 1 child mountain
  5. Denote $$$P(i)$$$ as a scoring function of the $$$i^\text{th}$$$ mountain, then
    1. $$$P(i) = 1$$$ if the $$$i^\text{th}$$$ mountain doesn't have any child mountain
    2. $$$P(i) = \max(P(m_1^i), P(m_2^i), \ldots,P(m_{k_i}^i)) + 1$$$ if the $$$i^\text{th}$$$ mountain has $$$k_i$$$ child mountains which are mountains $$$m_1^i, m_2^i, \ldots, m_{k_i}^i$$$, where $$$\max(\cdot)$$$ is a function that returns the maximum value of the numbers.

From the information above, the mountain that has the highest score is going to be the one that Prof. TOI uses as a tourist attraction spot.

Example

Figure 1. An example of parent mountain and child mountain

From Figure 1, there are 7 mountains: A, B, C, D, E, F, and G that are located at [2,6], [1,9], [3,8], [6,7], [7,11], [9,13], and [11,13] respectively. We can see that

    Mountain B is a parent mountain of mountains A, C, and D (mountains A, C, and D are child mountains of B)

    Mountain C is a parent mountain of mountain D (mountain D is a child mountain of mountain C)

    Mountain F is a parent mountain of mountain G (mountain G is a child mountain of mountain F)

The score of each mountain can be calculated as follows:

  1. $$$P(A)$$$,$$$P(D)$$$,$$$P(E)$$$, and $$$P(G)$$$ have a score of 1
  2. $$$P(C)=\max(P(D))+1=1+1=2$$$
  3. $$$P(F)=\max(P(G))+1=1+1=2$$$
  4. $$$P(B)=\max(P(A),P(C),P(D))+1=\max(1,2,1)+1=2+1=3$$$
Therefore, mountain B has the highest score compared to the rest, and the score of mountain B is 3

Your Task

Given the data of every mountain, write an efficient program to determine the score of the mountain with the highest score, and also the score of each mountain.

Input

There are $$$N+1$$$ lines of input:

Line 1An integer $$$N$$$ denoting the number of mountains, for $$$1\leq N\leq 400{,}000$$$
Line $$$i + 1$$$ to Line $$$N+1$$$

where $$$i=1,\ldots,N$$$

2 integers separated by a single space, $$$L_i$$$ and $$$R_i$$$, denoting the location $$$[L_i,R_i]$$$ of the $$$i^\text{th}$$$ mountain, where $$$1\leq L_i \leq R_i \leq 10^9$$$
Output

There are 2 lines of output:

Line 1Output the score of the mountain with the highest score.
Line 2Output $$$N$$$ integers separated by a single space, denoting the score of each mountain in order from the $$$1^\text{st}$$$ mountain to the $$$N^\text{th}$$$ mountain.

Notice

You will receive 40% of the total score if the program only answers the first line of the output correctly.

Scoring

Notices regarding the test sets are as follows:

Test GroupMaximum attainable score in this groupCondition(s)
15$$$L_i = 1$$$ for every $$$i$$$
23$$$L_i$$$ are sorted in an ascending order, and $$$R_i$$$ are sorted in a descending order i.e. $$$L_i-1\leq L_i$$$ and $$$R_i-1\geq R_i$$$ for every integer $$$i=2,\ldots,N$$$
34$$$L_i$$$ are sorted in an ascending order, and $$$R_i$$$ are also sorted in an ascending order i.e. $$$L_i-1\leq L_i$$$ and $$$R_i-1\leq R_i$$$ for every integer $$$i=2,\ldots,N$$$
412$$$N\leq 5$$$
520$$$N\leq 2{,}000$$$
623The answer of the first question is not greater than 50
733No additional constraints.
Examples
Input
7
9 13
11 13
7 11
1 9
2 6
3 8
6 7
Output
3
2 1 1 3 1 2 1
Input
5
1 3
1 6
1 5
1 1000
1 4
Output
5
1 4 3 5 2
Input
4
1 2
2 3
3 4
4 5
Output
1
1 1 1 1
Note

Recommended programming tips

If the contestant uses cin/cout, it is recommended to add 2 lines as the following: 

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);