Recently, Yura bought a new car. Let's uncover some of its features: the car can speed up with acceleration no more than $$$a$$$, maintain a constant speed and also brake with deceleration no more than $$$b$$$. But the main thing is the car doesn't have a maximum speed, so it can go faster than the speed of light and move its owner to the future.
Yura enjoyed his car that much that he forgot, that BSUIR Open starts in $$$4$$$ minutes. Yura's house and the university are located in a straight line. Unfortunately, it is not possible to reach the speed of light, cause the whole path from home to the university is covered with speed cameras. Specifically, the path has $$$n$$$ cameras, $$$i$$$-th located at point $$$x = x_i$$$ denoting that at this point the car should move with speed no more than $$$v_i$$$ or its owner will get a fine.
The house is located at point $$$x = 0$$$, and the university — at the same point where the last camera ($$$x = x_n$$$). Calculate the minimum time to get to the university from home by car. Note that Yura starts at zero speed.
The first line contains three integers $$$n, a, b$$$ — denoting the number of speed cameras on the path and the car parameters.
Each line $$$i$$$ of the following $$$n$$$ subsequent lines contains two integers $$$x_i, v_i$$$. It is guaranteed, that $$$x_i \gt x_{i - 1}$$$ for all $$$i \gt 1$$$.
$$$$$$1 \le n \le 10^5, 1 \le a, b \le 1000$$$$$$ $$$$$$1 \le x_i \le 10^7, 0 \le v_i \le 1000$$$$$$
Print a single number — minimal time to reach the university from home without fines. Your answer would be considered correct, if absolute or relative error won't exceed $$$10^{-6}$$$.
2 1 1 1 1 2 2
2.1815405
4 1 5 2 3 4 5 7 3 9 5
4.3598594
Someone has gifted Varvara matrix $$$n \times m$$$, which consists of numbers from $$$0$$$ to $$$k$$$. Each row and each column of this matrix has at most one $$$0$$$.
Let the beauty of matrix be the number of different rectangles which have equal numbers on all four corners of this rectangle. Formally, the beauty of the matrix is the number of different sets $$$\{x_1, x_2, y_1, y_2\}$$$, where «$$$1 \le x_1 \lt x_2 \le n$$$», «$$$1 \le y_1 \lt y_2 \le m$$$» and «$$$a_{x_1, y_1} = a_{x_1, y_2} = a_{x_2, y_1} = a_{x_2, y_2}$$$».
Varvara is interested in the following question: can she replace each $$$0$$$ in matrix with integers $$$A$$$ or $$$B$$$, in such a way that the beauty of matrix won't change. Note that each $$$0$$$ is replaced independently.
The first line contains two integers $$$n$$$ and $$$m$$$, denoting the number of rows and columns of the matrix respectively. The second line contains a single integer $$$k$$$. The third line contains two integers $$$A$$$ and $$$B$$$ denoting the numbers which can be used to replace $$$0$$$ in matrix. Each of the following $$$n$$$ lines contain $$$m$$$ space-separated integers $$$a_{i, j}$$$ denoting the given matrix.
$$$$$$2 \le n, m \le 10^3$$$$$$ $$$$$$2 \le k \le n \cdot m$$$$$$ $$$$$$1 \le A, B \le k, A \neq B$$$$$$ $$$$$$0 \le a_{i, j} \le k$$$$$$
Print «Yes» and $$$n$$$ lines with the matrix after replacing all $$$0$$$ if it is possible to keep the same beauty of the matrix. Otherwise, print a single line «No».
4 4 5 3 5 1 1 0 3 0 5 4 5 1 1 4 4 2 5 3 0
Yes 1 1 5 3 5 5 4 5 1 1 4 4 2 5 3 3
4 4 4 1 2 1 1 3 3 1 0 2 3 1 2 0 3 1 3 1 3
No
Julia organizes the largest cockroach race ever. It's a fun and exotic job where the main and the only problem is to place cockroaches in the correct order at the start. Once it's done, everything is cockroach gods will. It is known that, chalk written numbers on the cockroaches backs can have leading zeros, and most crucially, the numbers of cockroaches at the start must form an increasing sequence. It's not known who and why came up with this rule. Anyway, we just have to obey. But unfortunately chalk erases easily, so here and there only vague spots remained instead of some digits. Since Julia is a true professional and doesn't want to break the rule, she is trying to restore accidentally erased digits. Let's calculate the sum of all the possible numbers of cockroaches for all possible sequences.
The first line contains two integers $$$n$$$ and $$$m$$$ — the ammount of cockroaches and the length of their numbers. Next $$$n$$$ lines contain numbers patterns. Each pattern is formed using digits '0' to '9' and/or '?' symbol.
$$$$$$1 \le n, m \le 50$$$$$$
Output the sum of all the possible numbers of cockroaches for all the possible sequences modulo $$$10^9+7$$$.
2 2 ?? ??
490050
2 3 4?? ??2
6403775
4 1 0 ? 4 8
42
Junior DJ DIMAS wants to held $$$d$$$ parties in a row in the Byteland. As known, a single party of DJ DIMAS can't be without a light show. There are $$$n$$$ different lightbulbs in the night club, where the parties are held. However, after the last rave, some vandals broke all the switches. Now Dima has the following problem: he has to find new switches somewhere. However, a purchase of them is not possible, because DJ DIMAS isn't wealthy yet. So, he will rent them. Because of the fact that there are some other DJ in Byteland, each switch has an interval of days when it is available.
Switches toggle the state of a subset of lightbulbs. The switch is denoted by a binary string $$$s$$$, consisting of $$$n$$$ characters, ones and zeroes. If $$$i$$$-th position contains one, then after toggling this switch the state of $$$i$$$-th light will change on the opposite (if the light was on, it becomes off, and vice versa).
There are $$$q$$$ switches in the store. For each of them you are given $$$l$$$ and $$$r$$$ — interval of days this switch is available for rent.
DJ DIMAS wants the light show be as various as possible, so before each party, he wants to know the number of different sets of enabled lights he can get using some of the available switches. DJ DIMAS doesn't have much time preparing new tracks, so he asks you to help.
The first line contains three integers $$$n$$$, $$$q$$$ and $$$d$$$, where $$$n$$$ — the number of lightbulbs, $$$q$$$ — the number of switches, $$$d$$$ — the number of days parties will be held.
The next $$$q$$$ subsequent lines contain information about switches. Every switch is given as follows:
- $$$l$$$ $$$r$$$ $$$s$$$ — interval of days, when the switch is available. $$$s$$$ — string of $$$n$$$ characters consisting of $$$0$$$ and $$$1$$$ (for example, if $$$n = 5$$$, $$$s$$$ can be $$$\text{01101}$$$).
$$$$$$1 \leq n, q, d \leq 500 \, 000$$$$$$ $$$$$$1 \leq l \leq r \leq d$$$$$$
It is guaranteed that total length of $$$s$$$ of all switches will not exceed $$$500 \, 000$$$.
Print $$$d$$$ space-separated integers, $$$i$$$-th ($$$1 \leq i \leq d$$$) of them denoting the number of different sets of enabled lights, that are possible to toggle using some of the available switches at day $$$i$$$. It is worth mention, that all the switches can be unused.
Still this numbers can be very large, print them modulo $$$10^9 + 7$$$.
3 3 3 1 3 011 3 3 101 3 3 001
2 2 8
4 3 4 2 4 1010 2 4 0101 3 4 1101
1 4 8 8
5 2 2 1 2 01101 1 1 10101
4 2
A little girl named Julia has decided to open a toy store in the backyard. She decided to sell two types of goods: teddy bears and stuffed bunnies. As you know, every normal store has price tags for its goods. But Julia still can not write, although she is taking her first steps in business. That's why she decided to form price tags from her kids blocks with numbers using every single block, so that not one is lost. Julia is very kind and generous, so she decided that prices should form a minimum pair, should not be more than $$$10^{18}$$$, and even can be equal to zero. However, the girl doesn't like leading zeros, so they shouldn't be present on price tags. Let's support small business and help to form two price tags from the available blocks.
The first and the only line contains a list of available blocks — string $$$s$$$ consisting of digits only. $$$$$$1 \le |s| \le 50 $$$$$$
Output two price tags. Remember that the minimum pair is a pair where, firstly, the lower of the two prices is minimal, and, secondly, the other price is also the minimal possible for the given first one. If such price tags can't be formed, output «-1 -1».
123456
1 23456
42
2 4
000
-1 -1
Most likely you already know what is a prime number. Just in case, we recall that a prime is a positive integer that has exactly two different positive integer divisors. In fact, this definition greatly limits your consciousness, so let's try to give an equivalent definition of prime numbers...
A prime number is such an integer $$$p \gt 1$$$ that there is no such pair of integers $$$x$$$ and $$$y$$$ that $$$x \times y = p$$$ and $$$1 \lt x \le y \lt p$$$. It seems that nothing has changed, but in fact it greatly expands your consciousness. Perhaps, reading this definition, you thought about prime numbers over the multiplication operation. Yes, this is true if we assume that «$$$\times$$$» is a multiplication operation. But what if "$$$\times$$$" is not a multiplication operation, but a bitwise "OR" operation? Can you now determine whether a number $$$n$$$ is prime or not? Let's check it out!
The single line contains a single integer $$$n$$$ — the number you need to check that it is a prime number over the bitwise "OR" operation.
$$$$$$1 \le n \le 10^{18}$$$$$$
In a single line, print "Yes" if the number is a prime over the bitwise "OR" operation, otherwise print "No".
2
Yes
42
No
Bitwise OR of two non-negative integers $$$a$$$ and $$$b$$$ is the number $$$c = a\ OR\ b$$$, such that each of its digits in binary notation is $$$1$$$ if and only if at least one of $$$a$$$ or $$$b$$$ have $$$1$$$ in the corresponding position in binary notation.
Consider the following numerical sequence which you will explore:
$$$1$$$, $$$11$$$, $$$21$$$, $$$1211$$$, $$$111221$$$, $$$312211$$$, $$$13112221$$$, $$$1113213211$$$...
In this numerical sequence, to get the next number, you need to divide the current one into groups of identical numbers and replace each group with the number of repeated digits and the repeated digit in the group itself (in that order). So, with the number $$$13112221$$$ the following will occur: $$$13112221 \rightarrow 1, 3, 11, 222, 1 \rightarrow 11, 13, 21, 32, 11 \rightarrow 1113213211$$$. It can be seen that this sequence is growing rather rapidly, which makes research very difficult. Fortunately, we can limit ourselves to the last $$$m$$$ digits of the number of this sequence, written in decimal notation, which will allow us to do some research.
Let's start with some simple exploration. Output the last $$$m$$$ digits of the $$$n$$$-th number of the given sequence.
The first line contains two integers $$$n$$$ and $$$m$$$ — the sequence number and the number of the last digits to be output.
$$$$$$1 \le n \le 10^{18}$$$$$$ $$$$$$1 \le m \le 1\,000$$$$$$
In the single line print a single integer — the last $$$m$$$ digits of the $$$n$$$-th number of the sequence. If the length of the $$$n$$$-th number is less than $$$m$$$, then you need to output the number itself.
1 2
1
42 1
1
Fibonacci numbers — well-known integer sequence, where $$$F_0 = 0$$$, $$$F_1 = 1$$$ and $$$F_n = F_{n - 1} + F_{n - 2}$$$ for $$$n \gt 1$$$.
Lesha doesn't like this sequence and all the numbers $$$x$$$, such that we can get positive Fibonacci number by crossing out several digits. For example, Lesha doesn't like number $$$193$$$, because it is possible to cross $$$9$$$ out and get $$$F_6 = 13$$$.
Your task is to find the number of integers from $$$0$$$ to $$$n$$$ which Lesha likes.
The first line contains a single integer $$$t$$$ — the number of test cases.
Each of the following $$$t$$$ lines contains a single integer $$$n$$$ — number, until which you have to count numbers which Lesha likes.
$$$$$$1 \le t \le 10$$$$$$ $$$$$$0 \le n \le 10^{18}$$$$$$
Print $$$t$$$ lines, each of them should contain a single integer — the answer for the test case.
2 4 2019
2 125
In the first test suitable numbers are 0 and 4.
Given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ positive integers. You need to find a number of pairs $$$(L, R)$$$ (where $$$L \le R$$$) such that the following condition holds: $$$a_L \bmod a_{L+1} \bmod \dots \bmod a_R = a_R \bmod\ a_{R-1} \bmod \dots \bmod a_L$$$, where $$$\bmod$$$ is defined as operation of taking the remainder of the division.
The first line contains an integer $$$n$$$ — the size of the array.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ — the elements of the array.
$$$1 \le a_i \le 3 \cdot 10^5$$$
Print a single integer — number of pairs $$$(L, R)$$$, satisfying the given condition.
2 5 5
3
3 8 3 5
4
Andrew loves to watch biathlon races, and, like many other fans, he loves the red-haired Josya. For many years of watching the races Andrew has collected enough statistics about each biathlete in the upcoming race. Now he wants to calculate the probability that Josya will be on the podium in the upcoming individual race, and asks you for help.
The individual race consists of $$$5$$$ laps and $$$4$$$ shooting lanes ($$$2$$$ shootings from prone position and $$$2$$$ shootings from standing position). There are $$$5$$$ rounds and $$$5$$$ targets at each shooting stage. Each miss adds one minute to the athlete's time.
We have some information about each biathlete. We know the lap time, as well as the probability to hit the target from the prone and standing position. For simplicity let us consider that all athletes spend the same amount of time on the shooting late. Josya starts at the first number.
At the end of the race, the athlete takes the place of $$$X$$$, equal to the number of athletes who ran the race strictly faster, plus one. All the athletes who took first, second or third place will be on the podium. Note that several athletes can share the one place.
The first line contains one integer $$$n$$$ — number of participants in the race.
In each of the following $$$n$$$ lines there are three numbers $$$time_i, down_i, up_i$$$, where $$$time_i$$$ is the integer lap time in seconds, $$$down_i$$$ is the probability to hit the target from the prone position, $$$up_i$$$ is the probability to hit the target from the standing position. $$$up_i$$$ and $$$down_i$$$ are real numbers with exactly three digits after the decimal point.
$$$$$$1 \leq n \leq 50000$$$$$$ $$$$$$1 \leq time_i \leq 600$$$$$$ $$$$$$0 \leq down_i, up_i \leq 1$$$$$$
Output the only real value — probability of Josya to get on the podium. The absolute or relative error must not exceed $$$10^{-9}$$$.
4 45 0.700 0.700 60 0.800 0.800 90 0.900 0.900 120 1.000 1.000
0.675394632273
Berland — an independent state from $$$n$$$ cities, some of which are connected with $$$n-1$$$ roads in such a way that it is possible to reach any city from any other city using these roads. The time required to traverse a road using a car is known.
Administration of Berland calculated the minimal time to drive from one city to the other city, for all the pairs of cities and are horrified how old the roads are. It is time to make innovations! Specifically, $$$m$$$ times the administration takes two cities $$$u, v$$$ and replaces all the roads on the shortest path from $$$u$$$ to $$$v$$$ with innovative ones. If the road required $$$w$$$ time to drive before, then after the replacement of this road the time will be $$$\lfloor \sqrt{w} \rfloor$$$. After some road became innovative, it can become even more innovative. Other words, one road can be updated several times.
Unfortunately, the renovation will be held by you. Calculate the sum of the shortest paths between all pairs of cities before the innovations and after each replacement of path. As these sum can be large, print it modulo $$$10^9 + 7$$$.
The first line contains two integers $$$n, m$$$ — denoting the number of cities and queries, respectively.
Each of the following $$$n-1$$$ lines contains three integers $$$u, v, w$$$ — denoting the cities connected by road and the time required to drive this road.
Each of the following $$$m$$$ lines contain two integers $$$u, v$$$ — denoting that innovations are held on the path between them.
$$$$$$1 \le n, m \le 2\cdot10^5$$$$$$ $$$$$$1 \le u, v \le n, 1 \le w \le 10^6$$$$$$
Print $$$m+1$$$ lines, each of them should contain a single integer — initial sum and $$$m$$$ answers to the queries modulo $$$10^9 + 7$$$.
5 3 1 2 4 2 3 4 1 4 9 1 5 16 1 5 1 3 1 4
140 92 72 48
Andrew decided to give a gift to one of his $$$n$$$ guests. In order to choose the lucky one, Andrew decided to arrange a lottery. To do this, he took $$$2n$$$ cards with numbers from $$$1$$$ to $$$2n$$$, mixed them and gave two cards to each guest. The gift will be given to the guest, whose sum of the numbers on the cards is the maximum. However, after Andrew handed out the cards, he realized that there could be several winners. He asks you to calculate the probability that he will not have to look for additional gifts.
The only line contains one integer $$$n$$$. $$$$$$1 \leq n \leq 10^5$$$$$$
Let the answer to the problem be an irreducible fraction $$$\frac{P}{Q}$$$.
Output $$$P \times Q^{-1}$$$ modulo $$$10^9+7$$$ as the answer. It is guaranteed that $$$Q$$$ is not divisible by $$$10^9+7$$$.
2
666666672