Baq has $$$n$$$ coins, each with a value of $$$m_{i}$$$. Baq does not like it when the machines where he buys subway tickets give him change, so he wants to know if with his $$$n$$$ coins he can pay exactly any amount.
What is the minimum amount of money that Baq cannot pay exactly with his $$$n$$$ coins?
The input consists of an integer $$$t$$$ followed by $$$t$$$ cases.
Each case starts with an integer $$$n$$$ followed by the $$$n$$$ values of the coins, $$$m_{i}$$$.
One line for each case with the minimum amount of money that Baq cannot pay exactly.
$$$1 \leq t \leq 500$$$
$$$1 \leq m_{i} \leq 10^{9}$$$
$$$1 \leq n$$$
13 Points $$$\; \; \; n \leq 10 $$$
26 Points $$$\; \; \; n \leq 100$$$
30 Points $$$\; \; \; n \leq 1000$$$
31 Points $$$\; \; \; n \leq 10000$$$
3 5 2 4 16 8 1 3 1 2 3 4 3 5 7 1
32 7 2
Hermenegilda is training to compete in the International Olympiad in Informatics, but she doesn't have much time left. After pondering for a while about what strategy she should follow, she has decided that the best thing she can do is to stop studying and focus her efforts on becoming a Russian contestant, as this way she is sure to win a medal. To achieve this goal, she travels to the Federal Amusement Park of Kazan, famous for its authentically Russian roller coasters.
An authentically Russian roller coaster is an attraction that consists of $$$2l$$$ segments, placed one after the other. There are only two types of segments: ascending and descending. Each segment measures exactly one Russian unit of length in its horizontal component and one Russian unit of length in its vertical component. That is, each segment advances one Russian unit of length upward or downward and one Russian unit of length horizontally, depending on whether it is an ascending or descending segment. Furthermore, authentically Russian roller coasters have no segments underground and start and end at ground level. Surprisingly, the Federal Amusement Park of Kazan contains all possible authentically Russian roller coasters.
In her effort to become a Russian contestant, Hermenegilda starts her training methodically: she wants to ride all the authentically Russian roller coasters that have a length of $$$2l$$$ Russian units and a height of exactly $$$h$$$ Russian units; that is, their highest point is $$$h$$$ Russian units above ground level. We ask you to tell us how many authentically Russian roller coasters Hermenegilda will need to ride.
The first line contains a single positive integer $$$t$$$, the total number of cases. The following $$$t$$$ lines, one for each case, each consist of two positive integers: $$$l$$$ and $$$h$$$.
For each case, you must print a single integer: the number of attractions of length $$$2l$$$ and height $$$h$$$ that Hermenegilda will ride. Since this number can be very large, we ask you to print it modulo 1000000007.
$$$1\leq h, l \leq 9, 1\leq t \leq 25 \qquad \qquad \; \; \;$$$ 20 Points
$$$1\leq h, l \leq 13, 1\leq t \leq 9 \qquad \qquad \; \; \;$$$ 20 Points
$$$1\leq h, l \leq 200, 1\leq t \leq 40000 \qquad \, \,$$$ 60 Points
4 2 2 2 3 3 2 15 5
1 0 3 2665884
The brothers Baq and Babaq enjoy collecting permutations. Babaq's collection is larger than Baq's (it has taken him more time to collect them). For this reason, Baq wants to take some permutations from his brother, but he has a small problem: Babaq has encoded his permutations so that no one can take them away.
The encoding has been done in the following way: If $$$p$$$ is a permutation of the numbers from $$$1$$$ to $$$n$$$, Babaq's encoding is a vector of $$$n$$$ integers $$$c$$$ such that $$$c_i$$$ (the $$$i$$$-th number of $$$c$$$) is the number of integers less than $$$p_i$$$ that appear before $$$p_i$$$ in the permutation. Formally, $$$c_i = |\{j \mid j \lt i \wedge p_j \lt p_i\}|$$$.
Help Baq decode his brother's permutations.
Each case starts with an integer $$$t$$$, the number of permutations that Baq wants to decode. This is followed by the description of the $$$t$$$ permutations to decode. Each encoding is described by an integer $$$n$$$, the number of elements in the permutation, and $$$n$$$ integers $$$c_i$$$ that describe the encoding.
Write $$$t$$$ lines. In the $$$i$$$-th line, write the $$$i$$$-th decoded permutation.
$$$1 \leq n \leq 8, t=36$$$ (21 points)
$$$1 \leq n \leq 2000, t=40$$$ (37 points)
$$$1 \leq n \leq 10^5, t=25$$$ (42 points)
2 3 0 0 2 5 0 1 2 0 2
2 1 3 2 4 5 1 3
For more than 60 years, the city of Girona has celebrated the flower exhibition "Girona temps de flors," where every corner and iconic space of the old town is decorated with flowers. The result is a city full of flowers and, of course, curious tourists from all over the world filling the streets of the old town of Girona to enjoy the wonderful exhibition.
But like everything, there is a dark side. The poor citizens who live peacefully throughout the year in the old town see their streets infested with tourists who seem unable to distinguish between a road and a sidewalk, or between a flower and a car that wants to pass.
After years of living in the old town of Girona, this year Cesc is going to fulfill the secret dream of all the residents of his neighborhood: to push as many tourists as possible on his way home!
This year, the exhibition consists of $$$n$$$ points decorated with flowers, at point $$$i$$$ there are $$$t_{i}$$$ tourists taking photos. The old town has a large number of alleys, and between each two flower exhibition points, there is an alley that connects them. The alley that goes from point $$$i$$$ to point $$$j$$$ has a length of $$$a_{ij}$$$; keep in mind that the alleys are one-way.
Cesc starts at point $$$0$$$ and wants to go home, which is at point $$$1$$$, pushing the maximum number of tourists possible. However, he is a bit in a hurry and does not want to take more than $$$S$$$ seconds, as he travels one unit of distance per second and can push the tourists without losing time. How many tourists can he push on his way home at most?
**Important**: To go from point $$$i$$$ to point $$$j$$$, it is not necessary to use the direct alley; any combination of alleys can be used.
Each tourist can only be pushed once.
It is guaranteed that he always has time to go from point $$$0$$$ to point $$$1$$$.
The input consists of several cases.
Each case starts with the integers $$$n$$$, $$$S$$$.
The following line contains the $$$n$$$ integers $$$t_{i}$$$.
Each of the next $$$n$$$ lines contains the integers $$$a_{ij}$$$. Line $$$i$$$ contains the integers $$$a_{i0}, a_{i1}, ..., a_{in}$$$.
One line for each case with the answer.
$$$1 \leq a_{ij}, t_{i} \leq 1000$$$
$$$a_{ii} = 0$$$
$$$1 \leq S \leq 20000$$$
11 points $$$\; \; 2 \leq n \leq 8 \; \;$$$ and $$$\; a_{ij} = 1 \; \;$$$ for all distinct $$$i$$$ and $$$j$$$.
12 points $$$\; \; 2 \leq n \leq 8 \; \;$$$ and $$$\; a_{ij} \; \;$$$ is the minimum time to go from $$$i$$$ to $$$j$$$.
13 points $$$\; \; 2 \leq n \leq 8 \; \;$$$
11 points $$$\; \; 2 \leq n \leq 15 \; \;$$$ and $$$\; a_{ij} = 1 \; \;$$$ for all distinct $$$i$$$ and $$$j$$$.
12 points $$$\; \; 2 \leq n \leq 15 \; \;$$$ and $$$\; a_{ij} \; \;$$$ is the minimum time to go from $$$i$$$ to $$$j$$$.
13 points $$$\; \; 2 \leq n \leq 15 \; \;$$$
28 points $$$\; \; 2 \leq n \leq 18 \; \;$$$
4 4 887 778 916 794 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
3375
3 1379 650 422 363 0 887 778 916 0 794 336 387 0 3 454 173 737 212 0 28 691 60 0 751 601 541 0
1435 910
8 7246 171 997 282 306 926 85 328 337 0 384 887 778 916 794 336 387 493 0 650 422 363 28 691 60 764 927 0 541 427 173 737 212 369 568 430 0 783 531 863 124 68 136 930 803 0 23 59 70 168 394 457 12 43 0 230 374 422 920 785 538 199 325 0 316 371 414 527 92 981 957 874 0
3432