In previous meetings of the Independent Organization for Epizootics, also known as the World Organization for Animal Health, everyone gathered in Barcelona to discuss the most relevant topics. However, every year several problems arose.
The problem occurred when it was time for dinner; several options were always proposed for dinner: a dining hall at the meeting venue, a café a little south of the location, or the pizzeria on the corner. But this was not the problem, as the attendees could not choose and always went to the pizzeria.
The issue they faced was that they never knew if they could buy pizzas to satisfy all the diners without any leftovers.
The pizzeria sells $$$M$$$ different pizza toppings numbered from $$$0$$$ to $$$M-1$$$. Each pizza is divided into 8 slices, and a pizza has only one topping.
There are $$$N$$$ people attending the meeting, and each person wants to eat $$$p_i$$$ slices of pizza.
The organization wants to know if, given the slices that the attendees want to eat, it is possible to buy a number of pizzas such that no food is wasted.
The input consists of several cases. Each case consists of several lines.
Each case begins with two integers $$$N$$$, $$$M$$$. The number of attendees and the number of pizza toppings offered by the pizzeria.
This is followed by $$$N$$$ lines, each line beginning with a number $$$p_i$$$, the number of slices that the i-th person wants to eat, followed by $$$p_i$$$ integers $$$t_{ij}$$$ indicating the toppings they want for their slices. A person may want more than one slice with the same topping.
For each case, you must print SI if it is possible to buy pizzas without wasting food, or NO if it is not possible. Each case must be printed on a different line.
$$$ 1 \leq N \leq 1000 $$$
$$$ 1 \leq M \leq 100 $$$
$$$ 1 \leq p_i \leq 10^5 $$$
$$$ 0 \leq t_{ij} \leq M-1 $$$
For each case, the sum of $$$p_i$$$ does not exceed $$$10^5$$$
Subtasks
Subtask 1 (15pt):
$$$ M = 1, N = 1 $$$
Subtask 2 (20pt):
$$$ M = 1 $$$
Subtask 3 (65pt):
No additional restrictions
1 1 8 0 0 0 0 0 0 0 0 5 1 1 0 2 0 0 3 0 0 0 2 0 0 1 0 3 3 3 0 1 2 3 2 2 0 3 1 1 1
SI NO NO
Mariano's farm can be viewed as a horizontal line, and at certain positions with integer coordinates, there is a pen that initially contains a single chicken. The chickens have a limited flying capacity and can only fly from one pen to another if the difference in coordinates of the two pens is less than a certain number $$$k$$$. We will say that two chickens are friends if one can fly to where the other is located using as many pens as they want as intermediate points. For example, if the chickens can fly a distance of 2 and we have 3 chickens at positions 1, 2, and 4, the chickens at positions 1 and 4 are friends because the first chicken can go to position 4 passing through position 2. Of course, Mariano wants his chickens to be able to relate to each other, but without causing chaos on the farm. Therefore, he asks you to determine the minimum distance they must be able to fly so that there are at least $$$a$$$ pairs of friends, given $$$a$$$, the number of pairs of chickens he wants to be friends.
The input starts with an integer $$$t$$$, the number of cases. It is followed by $$$t$$$ cases, each starting with two integers $$$n$$$ and $$$a$$$, the number of pens (each with one chicken) and the number of pairs of friend chickens that Mariano wants. Following this are $$$n$$$ integers, $$$x_i$$$, indicating the positions of the chickens. No two pens are at the same point, and it holds that $$$0 \leq x_i \leq 10^9$$$, $$$1 \leq a \leq n(n-1)/2$$$.
Print $$$t$$$ lines, each with a single number, the minimum distance that the chickens must be able to fly in each case.
$$$2 \leq n \leq 10$$$ (10 points)
$$$2 \leq n \leq 1000$$$ and $$$0 \leq x_i \leq 10000$$$ (13 points)
$$$2 \leq n \leq 1000$$$ (23 points)
$$$2 \leq n \leq 10^5$$$ and $$$a=1$$$ (5 points)
$$$2 \leq n \leq 10^5$$$ and $$$a=n(n-1)/2$$$ (8 points)
$$$2 \leq n \leq 10^5$$$ and no additional restrictions (41 points)
2 3 2 1 2 4 3 1 1 2 4
2 1
Given a word $$$s$$$, we want to apply a transformation $$$k$$$ times. The transformation consists of replacing all occurrences of the letter $$$a$$$ with the word $$$p_{a}$$$, all occurrences of $$$b$$$ with $$$p_{b}$$$, all occurrences of $$$c$$$ with $$$p_{c}$$$, and so on.
If we apply the transformation $$$k$$$ times, what is the letter at position $$$i$$$? ($$$i = 1$$$ represents the first letter).
The input consists of several cases, each case starts with the word $$$s$$$, followed by the integers $$$k$$$ and $$$i$$$.
This is followed by 26 lines, each containing a word, which corresponds to $$$p_{a}$$$, $$$p_{b}$$$, $$$p_{c}$$$...
One line for each case with the letter at position $$$i$$$ after $$$k$$$ transformations.
11 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 10, 0 \leq k \leq 1$$$
22 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 2, 0 \leq k \leq 20$$$
67 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 10, 0 \leq k \leq 10000$$$
$$$1 \leq i \leq 10^{18}$$$, and it is never greater than the final length of the word.
rb 2 16 mqbh dar owkk h d qs dxr mo frx j bld efsa cbyn c yg x pk orel nm apqf kho kmco h wnku w sqmg ljj 1 6 vsw d q bx x v rrbl ptns fw qf mafa rr sof b n vqh fb a x pqc c hch vfrk l oz kpqp
h f
In previous meetings of the Independent Organization for Epizootics, also known as the World Organization for Animal Health, everyone gathered in Barcelona to discuss the most relevant topics. However, every year several problems occurred.
Many members lost the key to their room. For this reason and others, this year the meeting will be held remotely.
Although the meeting will not take place, the organization wants to solve the problem and proposes a solution. They know that $$$N$$$ people will attend the meeting, and each person $$$p_i$$$ has two keys to their room: one they will carry with them and the other they will leave in the room of the person $$$c_i$$$ ($$$c_1 \neq p_i$$$) whom they trust. Thus, whenever person $$$c_i$$$ can access their room, they will be able to enter and take the key of person $$$p_i$$$. It is guaranteed that there is at least one person such that if they can access their room, then all other people will be able to access theirs.
The association is interested in knowing for each person $$$p_i$$$, what is the minimum number of people that need to lose their key for them to be unable to access their room.
The input consists of several cases. Each case consists of two lines.
The first line of each case is an integer $$$N$$$, the number of people attending the meeting. The second line of each case contains $$$N$$$ integers $$$c_i$$$, the room where the i-th person leaves their second key.
For each case, you must print $$$N$$$ integers separated by a space and with a newline at the end.
The i-th integer is the minimum number of people that must lose their key for person $$$p_i$$$ to be unable to access their room.
$$$ 2 \leq N \leq 10^5 $$$
$$$ 0 \leq c_i \lt N $$$
Subcases
Subcase 1 (10pt):
- $$$ N \leq 100 $$$
Subcase 2 (35pt):
- $$$ N \leq 1000 $$$
Subcase 3 (55pt):
- No additional restrictions
2 1 0 5 1 0 0 0 0 5 1 2 3 2 3
2 2 2 2 3 3 3 4 3 2 2 3
Dean has received a tree as a gift. A tree is a connected graph without cycles (there is exactly one path without repeating vertices between each pair of vertices). However, Dean's tree has a special property: its vertices are painted in 2 colors: white and black. Dean does not like to mix these two colors, so he decides to turn it into a monochromatic tree (all vertices have the same color). Of course, he wants to do this in the minimum number of steps. In each step, he can do the following:
- Select a set $$$S$$$ of vertices such that all are connected and of the same color, and change their color.
Help Dean find the minimum number of steps he needs to convert his tree.
The input starts with a number $$$t$$$, the number of test cases. This is followed by the $$$t$$$ cases. Each case starts with an integer $$$n$$$, the number of vertices in the tree. This is followed by $$$n-1$$$ lines with 2 integers $$$a$$$ and $$$b$$$, $$$0 \leq a, b \leq n-1$$$ each, indicating that vertices $$$a$$$ and $$$b$$$ are connected by an edge. Next, there is a line with $$$n$$$ integers indicating the initial color of each vertex ($$$0$$$ if it is white, $$$1$$$ if it is black).
Print $$$t$$$ lines, each with a single integer: the minimum number of steps Dean must take to achieve his goal in each case.
$$$0 \leq n \leq 10$$$ (11 points)
$$$0 \leq n \leq 5000$$$ (27 points)
$$$0 \leq n \leq 100000$$$ and the tree is a chain, that is, vertex $$$i$$$ is connected to $$$i+1$$$, for all $$$i$$$ such that $$$0 \leq i \leq n-1$$$ (19 points)
$$$0 \leq n \leq 100000$$$ and the tree is a star, that is, vertex $$$0$$$ is connected to $$$i$$$, for all $$$i$$$ such that $$$1 \leq i \leq n$$$ (8 points)
$$$0 \leq n \leq 100000$$$ and there are no additional restrictions (35 points)
2 2 0 1 1 1 5 0 1 1 2 2 3 2 4 0 1 1 1 0
0 1