Santa Claus is already preparing for Christmas 2021. He wants to buy some positive number of presents, such that he will be able to divide them evenly (without remainder) among all eligible (not naughty) children. However, he does not yet know how many eligible children there will be – he only knows that this number will be between $$$a$$$ and $$$b$$$. Therefore, he wants to buy the minimum positive number of presents that can be divided evenly between any number $$$x$$$ of children with $$$x \in \{a,a+1,...,b\}$$$.
He has computed this (possibly huge) number of presents, but he is unsure about the correctness, and he would like your help in performing the following basic sanity check. Are you able to tell him how many zero digits there should be at the end of this number?
The first and only line of the input consists of two space-separated integers $$$a$$$ and $$$b$$$ ($$$1 \le a \le b \le 10^{18}$$$).
Output a single integer – the number of zeros at the end of the number of presents that Santa needs to buy.
Subtask 1 (6 points): $$$b \le 16$$$.
Subtask 2 (7 points): $$$b \le 40$$$.
Subtask 3 (9 points): $$$a = 1$$$ and $$$b \le 200$$$.
Subtask 4 (12 points): $$$b-a \le 10^6$$$.
Subtask 5 (17 points): $$$a = 1$$$.
Subtask 6 (49 points): there are no additional constraints.
1 6
1
10 11
1
First example: If there can be between 1 and 6 children, then Santa needs at least 60 presents (as this is the smallest number that is divisible by all of 1, 2, 3, 4, 5 and 6), and the number 60 has a single zero at the end.
Second example: If there can be either 10 or 11 children, Santa will buy 110 presents.
Luna came up with a wild idea. She lined up her $$$2n$$$ friends into a long line and gave each of them an integer number between $$$1$$$ and $$$n$$$, inclusive. Each number is used exactly twice. Each pair of friends who share the same number forms a couple.
Luna wants to send each of the $$$n$$$ couples on a date. However, it is not that straightforward. In order to send a couple on a date, the two friends forming the couple must stand next to each other in the line, i.e., there cannot be anybody else standing between them.
There are two possible actions that Luna can take:
- She can swap any two friends who stand next to each other in the line.
- If a couple is standing next to each other in the line, Luna can send them on a date. This removes the couple from the line. The remaining friends then shift to fill in the gap in the line.
The actions can be performed in any order. E.g., she can make some swaps, then send some pairs of friends on a date, and then go back to making swaps.
Find and report the minimum number of actions needed to send everybody on a date.
The first line of the input contains a single integer $$$n$$$.
The second line of the input contains $$$2n$$$ single-space separated integers $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) – the sequence of numbers received by the friends in the long line, in order.
The first and only line of the output contains the minimum number of actions Luna must make in order to send every couple on a date.
Subtask 1 (7 points): For each couple there is no person between the two friends forming a couple, and $$$1 \le n \le 100$$$.
Subtask 2 (8 points): For each couple there is at most one person between the two friends forming a couple, and $$$1 \le n \le 100$$$.
Subtask 3 (11 points): The first $$$n$$$ friends in the line received integers from $$$1$$$ to $$$n$$$, each exactly once, not necessarily in order. Furthermore, $$$1 \le n \le 3\,000$$$.
Subtask 4 (16 points): The first $$$n$$$ friends in the line received integers from $$$1$$$ to $$$n$$$, each exactly once, not necessarily in order. Furthermore, $$$1 \le n \le 500\,000$$$.
Subtask 5 (22 points): $$$1 \le n \le 3\,000$$$.
Subtask 6 (36 points): $$$1 \le n \le 500\,000$$$.
3 3 1 2 1 2 3
4
5 5 1 2 3 2 3 1 4 5 4
7
In the first sample, Luna could start by swapping the third and the fourth friend. After this swap the line looks as follows: 3 1 1 2 2 3.
Then, she can send the couple with number 1 and the couple with number 2 on a date (in any order). Once she does so, the two friends with number 3 are now adjacent in line and Luna can send them on a date, too.
Overall this solution takes 4 actions: one swap and three dates.
This is an interactive problem. Your program will communicate with our grader by alternately writing messages to the standard output and reading messages from the standard input.
Sophie is preparing her twins' birthday party. The twins love cookies. For their birthday, they would like to try something new: cookies from the Unique Cookie Tastiness Company (UCTC).
Every cookie produced by UCTC has an integer tastiness value between $$$1$$$ and $$$10^{16}$$$ inclusive. Since Sophie's twins get jealous of each other, each of them must receive cookies with the same sum of tastiness values.
UCTC only accepts orders of exactly $$$n$$$ cookies. In each order the client specifies the tastiness of each of the $$$n$$$ cookies they want.
Staying true to their name, the Unique Cookie Tastiness Company refuses to produce two cookies of the same tastiness for the same client. Sophie must make sure she never orders the same tastiness twice — neither in the same order, nor in two different orders. Sophie has never purchased from UCTC before, so she can order each available tastiness once.
There is one more obstacle in Sophie's way: It is well-known that the delivery service of UCTC is awful. Whenever a client orders $$$n$$$ cookies, only one of those $$$n$$$ cookies actually reaches the client. The rest is eaten along the way by the employees of the delivery service. The client cannot influence which of the $$$n$$$ ordered cookies will actually be delivered to her.
Since the birthday is approaching quickly, Sophie has the time to make at most 101 orders. Your task is to help her.
More specifically, you should do the following:
- First, order the cookies. You can make at most 101 orders, each consisting of exactly $$$n$$$ desired tastiness values. You make one order at a time. Immediately after each order you are given the tastiness of the one cookie that you actually received.
Remember that you are not allowed to use the same tastiness value multiple times, even over multiple orders. (In particular, if you order a cookie with some tastiness $$$t$$$ but it does not arrive, you cannot order a cookie with the same tastiness again.)
- Then, divide the cookies. Once you have received enough cookies, you should distribute some of the received cookies between the twins. Both twins should receive at least one cookie, and each twin should receive cookies with the same total tastiness. You do not have to use all the cookies you received!
Each time your program outputs one or more lines to the standard output, you must follow that action by flushing the output stream. This is necessary to make sure the data you output reaches the grader immediately.
Examples of how this can be done:
- In C++, there are multiple options.
- fflush(stdout);
- std::cout << std::flush;
- std::cout << std::endl; (note that this also prints an extra newline)
- in Java, you can use System.out.flush()
- in Python, you can use sys.stdout.flush()
Your program should perform the following sequence of actions:
- Read the value $$$n$$$ from the standard input.
- At most 101 times:
- First, write one line describing an order of $$$n$$$ cookies to the standard output.
- Then, read the tastiness of the cookie you received from the standard input. It is guaranteed that this value is among the $$$n$$$ values that were in the current order.
- Output three lines describing one valid way to give some of the cookies you received to the twins.
The grader will write each integer onto a separate line.
To order cookies, output a single line with ? followed by $$$n$$$ integers: the tastiness values of the cookies you want to order. Output a single space before each of the $$$n$$$ integers.
Remember that you may make at most 101 orders and that you are not allowed to use the same tastiness value twice.
Once you have ordered enough cookies, output the final three lines that describe which cookies Sophie should give to the twins.
The first of these lines should have the form "! $$$m$$$ $$$k$$$" with $$$m, k \gt 0$$$: the number of cookies the first and the second twin, respectively, should receive.
The second of these lines should contain $$$m$$$ integers separated by single spaces: the tastiness values of the cookies the first twin should receive.
Similarly, the third line should contain $$$k$$$ integers separated by single spaces: the tastiness values of the cookies the second twin should receive.
The output must satisfy the following conditions:
- Each twin should receive at least one cookie.
- Each twin should receive cookies with the same total tastiness.
- Only cookies you actually received after your orders can be used.
- Each of those cookies can only be given to at most one of the twins.
Any output that satisfies these conditions will be accepted. In particular, you can output the selected cookies in any order.
After you output the final three lines, flush the output stream one last time and then terminate your program normally.
Subtask 1 (8 points): $$$n = 1$$$
Subtask 2 (9 points): $$$1 \leq n \leq 2$$$
Subtask 3 (18 points): $$$1 \leq n \leq 25$$$
Subtask 4 (16 points): $$$1 \leq n \leq 200$$$
Subtask 5 (13 points): $$$1 \leq n \leq 1000$$$
Subtask 6 (36 points): $$$1 \leq n \leq 5000$$$
1 13 7 31 12 5 3
? 13 ? 7 ? 31 ? 12 ? 5 ? 3 ! 2 3 7 13 12 5 3
2 7 2 5
? 3 7 ? 2 8 ? 1 5 ! 2 1 2 5 7
Examples of input and output should be read row by row. Your program alternately reads one value from standard input and writes one line (or three lines at the end) to standard output.
The grader chooses which cookie to return arbitrarily. This means that the grader might be adaptive to your queries in some tests, but it might also choose cookies at random in other tests. In particular, for $$$n=2$$$, if you make the same sequence of orders as in the second example, you may receive a different set of cookies.
Farmer John has taken his herd of cows on a hiking excursion in the Alps! After a while, the sky got dark and the excursion was over. However, some cows remained trapped all along the mountain range, and it is up to John to rescue all of them!
The mountain range that the cows are currently traversing can be represented by a series of $$$n$$$ vertices in a vertical 2D plane. We will call these vertices "peaks". The peaks are numbered from 1 to $$$n$$$, in order. Peak $$$i$$$ has coordinates $$$(i, h_i)$$$. The value $$$h_i$$$ denotes the $$$\textbf{altitude}$$$ of peak $$$i$$$. It is guaranteed that $$$h_1,h_2,\ldots,h_n$$$ form a permutation of $$$1 \ldots n$$$. (That is, for each $$$j = 1, ..., n$$$, we have $$$h_i = j$$$ for exactly one $$$i \in \{1,...,n\}$$$.)
For each $$$i$$$ ($$$1\le i \lt n$$$), peaks $$$i$$$ and $$$i+1$$$ are connected by a straight line segment.
As it is nighttime, John cannot travel to any part of the mountain unless he has at least one functioning lantern with him. Luckily, there are $$$k$$$ lanterns available for purchase. For each $$$j$$$ ($$$1 \le j \le k$$$), lantern $$$j$$$ can be bought at peak $$$p_j$$$ for $$$c_j$$$ francs.
Unfortunately, lantern $$$j$$$ only works when John's current altitude is within the range $$$[a_j,b_j]$$$. In other words, whenever John's current altitude is strictly less than $$$a_j$$$ or strictly greater than $$$b_j$$$, lantern $$$j$$$ does not work. Note that lanterns do not break when they leave their range. For example, when John's altitude exceeds $$$b_j$$$, lantern $$$j$$$ will stop working, but as soon as John returns to altitude $$$b_j$$$ the lantern will start working again.
If John is currently at peak $$$p$$$, he can perform one of the following three actions:
- He can buy one of the lanterns that are available at peak $$$p$$$. Once he buys a lantern, he can use it forever.
- If $$$p \gt 1$$$, he can walk to peak $$$p-1$$$.
- If $$$p \lt n$$$, he can walk to peak $$$p+1$$$.
John must never move without a working lantern. He can only walk between two adjacent peaks if at each moment of the walk at least one of the lanterns he already owns will work. (It does not have to be the same lantern during the entire walk.)
For example, suppose that Farmer John is currently located at a peak with altitude $$$4$$$ and wishes to walk to an adjacent peak with altitude $$$1$$$. If John has lanterns that function in the altitude ranges $$$[1,3]$$$ and $$$[3,4]$$$, this will allow him to walk from one peak to the other.
However, if John has lanterns that only function in the ranges $$$[1,1]$$$ and $$$[2,5]$$$, then John will not be able to walk between these two peaks yet: e.g., none of his lanterns will work at altitude $$$1.47$$$.
Your task is to determine the answers to multiple independent questions.
For each $$$1 \le j \le k$$$ satisfying $$$a_j \le h_{p_j} \le b_j$$$, suppose that John begins his search at peak $$$p_j$$$ by buying lantern $$$j$$$. In order to search the entire mountain range, he must then visit every one of the $$$n$$$ peaks at least once by repeatedly performing one of three actions above. For each of these $$$j$$$, determine the minimum total number of francs that John needs to spend in order to search the entire mountain range. (This cost includes the initial purchase of lantern $$$j$$$.)
The first line contains $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq k \leq 2000$$$) – the number of mountain peaks and available lanterns, respectively.
The second line contains $$$n$$$ space-separated integers $$$h_1,h_2,\ldots,h_n$$$ ($$$1 \leq h_i \leq n$$$): the altitude of each peak. It is guaranteed that the values $$$h_i$$$ are a permutation of $$$1$$$ through $$$n$$$.
The $$$j$$$-th of the next $$$k$$$ lines contains four space-separated integers $$$p_j$$$, $$$c_j$$$, $$$a_j$$$, and $$$b_j$$$ ($$$1 \leq p_j \leq n$$$, $$$1 \leq c_j \leq 10^6$$$, $$$1 \leq a_j \leq b_j \leq n$$$) – the mountain peak on which lantern $$$j$$$ can be purchased, its cost and operational range, respectively.
For each $$$j$$$ ($$$1 \le j \le k$$$) output a single line:
- If $$$h_{p_j}$$$ is outside the range $$$[a_j,b_j]$$$, output $$$-1$$$.
- Else, if John cannot search the entire mountain range by first buying lantern $$$j$$$, output $$$-1$$$.
- Else, output the minimum total number of francs that John needs to spend in order to search the entire mountain range if he begins by buying lantern $$$j$$$.
Subtask 1 ($$$9$$$ points): $$$n \le 20$$$ and $$$k \le 6$$$.
Subtask 2 ($$$12$$$ points): $$$n \le 70$$$ and $$$k \le 70$$$.
Subtask 3 ($$$23$$$ points): $$$n \le 300$$$, $$$k \le 300$$$ and $$$h_i = i$$$ for all $$$1 \le i \le n$$$.
Subtask 4 ($$$16$$$ points): $$$n \le 300$$$, $$$k \le 300$$$.
Subtask 5 ($$$40$$$ points): no additional constraints.
7 84 2 3 1 5 6 73 1 2 41 2 1 34 4 1 76 10 1 76 20 6 66 30 5 57 40 1 67 50 7 7
7 -1 4 10 30 -1 -1 -1
If John starts by buying lantern $$$1$$$ on peak $$$3$$$, he can then perform the following sequence of actions:
- walk left twice to peak $$$1$$$
- buy lantern $$$2$$$
- walk right to peak $$$4$$$
- buy lantern $$$3$$$
- walk right to peak $$$7$$$
At this point, John has visited each peak at least once and he spent a total of $$$1+2+4=7$$$ francs.
John can't start by buying lantern $$$2$$$, $$$6$$$, or $$$7$$$, since they don't function at the altitude at which they can be bought. Thus, the answers for each of these lanterns is $$$-1$$$.
If John starts by buying lantern $$$3$$$ or $$$4$$$, he can then visit all peaks without buying additional lanterns.
If John starts by buying lantern $$$5$$$, he must also buy lantern $$$4$$$ later.
If John starts by buying lantern $$$8$$$, he will be stuck at peak $$$7$$$. Even if he also purchases lantern $$$7$$$ as well, he still won't be able to walk from peak $$$7$$$ to peak $$$6$$$.