In previous meetings of the Independent Organization of 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.
The attendees at the meeting never manage to concentrate; they get distracted by any trivial matter. In the last meeting, for example, they were entertained by a piece of paper on the wall with the following lines.
1
11
21
1211
111221
312211
They spent a long time trying to decipher this tough problem until someone explained the solution to them. Each line is simply generated by reading the previous line aloud. For example, the second line is "one one," the third is "two ones" (and not "eleven"), etc.
To prevent this problem from happening again, the organization asks you to write a program that outputs the i-th number of the sequence, where $$$a_0 = 1$$$.
The input consists of a single case.
The case contains only one integer $$$N$$$.
The output consists of a single line, the value of the $$$N$$$-th term of the sequence.
$$$ 1 \leq N \leq 53 $$$
There is one case for each value of $$$N$$$. Each case, except for the three examples, is worth 2 points.
1
11
2
21
7
1113213211
As everyone knows, Timur's favorite number is $$$11$$$. Therefore, for his birthday, he asked for a string with the number $$$11$$$. However, when he opened the gift, he found a string $$$s$$$, which was not what he wanted. Totally disappointed, he started to cry, and his parents, wanting to console him, told him that his string had many substrings that were multiples of $$$11$$$. However, they do not know how to count them, and that is why they need your help. A substring is a group of consecutive characters from a string. For example, $$$102$$$ has substrings $$$1, 0, 2, 10, 02$$$, and $$$102$$$, but not $$$12$$$.
Note that substrings can start with $$$0$$$, and for example, the string $$$02$$$ would correspond to the number $$$2$$$. However, it is guaranteed that the first digit of the string $$$s$$$ given to you will never be zero.
The input consists of an integer $$$t$$$ indicating the number of cases. It is followed by $$$t$$$ cases, each consisting of 2 lines. In the first line, there is a number $$$n$$$ indicating the length of the string, and in the second line, there is the string $$$s$$$ representing Timur's number.
Print $$$t$$$ lines, one for each case indicating the number of substrings of $$$s$$$ that are multiples of $$$11$$$.
$$$n \leq 12$$$ (12 points)
$$$n \leq 300$$$ (14 points)
$$$n \leq 2000$$$ (21 points)
$$$n \leq 100000$$$ and all digits of the number are the same (20 points)
$$$n \leq 100000$$$ and no additional restrictions. (33 points)
2 3 121 4 1000
1 6
Night is approaching and its dangers lurk. As is well known, the most illustrious gentlemen turn into true rogues when the clock strikes twelve. Tired of seeing your neighbors steal from each other on the street with total impunity, you decide to install streetlights along your street so that it is always illuminated, and at least they feel some shame when committing their misdeeds. However, you do not want to waste electricity unnecessarily, so you decide to create a program that, knowing where your neighbors are at a given moment and what radius each streetlight illuminates, calculates the minimum number of streetlights to turn on so that everyone is illuminated, or informs you if it is not possible to do so. A neighbor is considered illuminated if they are within a closed interval centered on a streetlight and with the radius of that streetlight.
The input will consist of several cases. The first line will contain an integer $$$t$$$, the number of cases to solve.
For each case:
- The first line will contain two integers $$$n, m$$$, the number of neighbors and the number of streetlights.
- The following line contains $$$n$$$ integers $$$x_i$$$ with the positions of your neighbors.
- The last $$$m$$$ lines contain a pair of integers $$$y_i, r_i$$$, the position and the radius of each streetlight.
For each case, write on a line the minimum number of streetlights that need to be turned on to illuminate all the neighbors or "imposible" if it cannot be resolved.
$$$0 \leq x_i, y_i, r_i \leq 10^9, 1 \leq t \leq 100$$$
- 30 points $$$1 \leq n \leq 100, 1 \leq m \leq 10$$$
- 30 points $$$1 \leq n \leq 1000, 1 \leq m \leq 100$$$
- 40 points $$$1 \leq n, m \leq 10^5$$$
3 1 2 5 3 2 7 2 5 5 7 10 3 4 4 3 3 7 1 8 2 3 2 2 4 1 1 0 3 2
1 2 imposible
It is the year 1692, and the people of Salem are bloodthirsty. Accusations of witchcraft are flying, and the mob is eager to see the heads of the witches on a platter. The mayor, wanting to appease the masses by minimizing the bloodbath, has decided to consult the $$$M$$$ friendships and enmities of the $$$N$$$ inhabitants: if two people are friends, then both are witches or neither is a witch, while if they are enemies, exactly one of them is a witch. Among all possible combinations of witches, the mayor will choose the one that contains the smallest number of witches. It is possible that the mayor's information is incorrect and no valid combination exists. Can you calculate how many witches will be executed?
The input consists of an integer $$$t$$$, followed by $$$t$$$ test cases. Each case starts with the integers $$$N$$$, $$$M$$$, the number of inhabitants and the number of relationships between the inhabitants. This is followed by $$$M$$$ lines, each with three integers $$$r_i$$$, $$$a_i$$$, $$$b_i$$$. If $$$r_i=1$$$, it means that inhabitants $$$a_i$$$ and $$$b_i$$$ are friends, and if $$$r_i=2$$$, then they are enemies.
One line per case with the minimum number of witches, or -1 if no valid configuration exists.
For all test cases, it holds that $$$t \leq 50$$$, $$$1 \leq N$$$, $$$0 \leq M \leq \frac{N(N - 1)}{2}$$$, $$$r_i \in \{1, 2\}$$$, $$$0 \leq a_i, b_i \lt N$$$, $$$a_i \ne b_i$$$ and for every pair of lines $$$i, j$$$, it holds that $$$a_i \ne a_j$$$ or $$$b_i \ne b_j$$$.
16 points: $$$N \leq 16$$$, $$$M \leq 30$$$
17 points: $$$N \leq 3 \cdot 10^4$$$, $$$M \leq 5 \cdot 10^4$$$, $$$r_i = 2$$$ for all i
17 points: $$$N \leq 200$$$, $$$M \leq 300$$$
50 points: $$$N \leq 3 \cdot 10^4$$$, $$$M \leq 5 \cdot 10^4$$$
3 6 5 2 0 1 2 1 2 1 1 3 2 3 4 2 4 5 5 3 1 0 1 2 2 3 2 3 4 3 3 1 0 1 1 1 2 2 0 2
3 1 -1
Surely you have heard of Japanese ninjas. What you probably didn't know is that there are also Spanish ninjas, but you have never heard of them because they are much better than the Japanese. In fact, throughout the history of Spain, they have only been caught once, trying to infiltrate the royal palace. Here are the chronicles.
The royal palace consists of $$$n$$$ rooms numbered from $$$0$$$ to $$$n - 1$$$, connected to each other by $$$n - 1$$$ corridors, all of equal length, so that from any room you can reach any other without leaving the palace. It also has multiple entrances: in each room that has only one corridor, there is a door that allows entry and exit from the palace through it.
A very large group of ninjas is ready to enter the palace to set an ambush for the king. Just as they are about to enter, an even larger group of royal guards spots them. At this moment, the ninjas quickly choose a door and all enter through it, and the guards, who have seen where the ninjas enter but do not have time to run towards them, choose another door and all enter through it.
Once inside, since both the ninjas and the guards move at the same speed, each room is occupied by the group that started closest to it, and in case of a tie, the guards take it (see the examples). The ninjas' goal is to occupy the maximum number of rooms possible, and the guards' goal is to ensure that the ninjas occupy the minimum possible. Knowing that both choose their starting room optimally, how many rooms do the ninjas occupy in the end?
One line, with an integer $$$t$$$, followed by $$$t$$$ test cases. Each test case consists of one line with an integer $$$n$$$, the number of rooms in the palace, followed by $$$n - 1$$$ lines with two integers $$$a_i$$$, $$$b_i$$$, indicating that rooms $$$a_i$$$ and $$$b_i$$$ are connected by a corridor.
One line for each case with the number of rooms occupied by the ninjas.
For all test cases, it holds that $$$t \leq 100$$$, $$$2 \leq n$$$, $$$0 \leq a_i, b_i \lt n$$$
5 points: $$$n \leq 5$$$
16 points: $$$n \leq 70$$$
22 points: $$$n \leq 500$$$
57 points: $$$n \leq 10000$$$
3 5 0 1 0 2 0 3 1 4 6 0 1 0 2 0 3 1 4 2 5 7 0 1 0 2 1 3 1 4 2 5 2 6
2 4 1