Hacker Kirill was nostalgically going through his school notebooks on computer science and noticed that the number system was not indicated in some addition problems. He was wondering: is it possible to unambiguously determine the number system that was used for addition only by using the recording of a problem?
Help Kirill — write a program that, with given terms and sum, will unambiguously restore the number system used for addition or inform that unambiguous restoration is not possible.
Proceed from the assumption that the addition is performed correctly.
The first line contains the first term, the second – second term, and the third – sum. To denote numbers use digits from «$$$0$$$» to «$$$9$$$» and capital Latin letters from «$$$A$$$» to «$$$Z$$$».
Terms and sum can be of different lengths, but the length of any of these numbers does not exceed $$$256$$$ digits.
If unambiguous restoration of the number system is not possible, output $$$0$$$; otherwise – output the whole positive base of the number system.
A 6 10
16
1 2 3
0
1 Y Z
0
While visiting the Moon, Neznayika discovered an absolutely new game like Earth's golf. In the Moon golf, the same as Earth's type, one needs to score balls in holes. However, holes are replaced by craters and balls – by meteorites.
Meteorites have different masses. The player's task is to score meteorites to the craters so that the total mass of the scored meteorites is the highest. The rules prohibit scoring more than one meteorite in one crater.
According to the rules of the Moon golf:
The powers of Neznayika are not endless, so the maximum distance he can reach with a meteorite depends on the mass $$$m$$$ of this meteorite and is calculated by the formula $$$ d = \sqrt{10^6 / m}$$$.
Help Neznayika to win – write a program that, using coordinates of craters and meteorite mass, determines the game's optimal strategy. For simplicity, let us assume that Neznayika does not know how to miss, and the strategy simply describes which meteorite should be scored into which crater.
In the first line is given an integer $$$ n $$$ $$$( 1 \leq n \leq 10^4 )$$$ – the number of meteorites. The second line consists of $$$n$$$ integers $$$ w_i $$$ $$$( 1 \leq w_i \leq 10^6 )$$$ separated by spaces – the mass of the meteorites.
The third line consists of the integer $$$ k $$$ $$$( 1 \leq k \leq 10^5 )$$$ – the number of craters on the playing field. In the next $$$k$$$ lines, there are triples of integers $$$ x_i , y_i, r_i $$$ $$$( -2\,000 \leq x_i, y_i \leq 2\,000 $$$, $$$ 1 \leq r_i \leq 10 )$$$ separated by spaces – coordinates of craters'centers and their radiuses.
The first line should contain an integer $$$ r $$$ $$$( 0 \leq r \leq min(n, k))$$$ – the number of meteorites that are supposed to be scored. Then $$$r$$$ lines, each containing two integer numbers $$$ s_i $$$ $$$(1 \leq s_i \leq n )$$$ and $$$ t_i $$$ $$$( 1 \leq t_i \leq k )$$$ – the number of the meteorite and the number of the crater where it should be scored. Meteorites and craters are numbered in the order of appearance in the input data. Numbering starts with one.
3 1 100 10000 3 0 10 1 0 100 1 0 1000 1
3 1 3 2 2 3 1
2 2 3 2 1000 0 1 0 1000 1
0
There are $$$N$$$ cities in the country of Drevlyandia, and each is numbered from $$$1$$$ to $$$N$$$. It is also known that there are bidirectional roads between some of the cities; besides, from each city, you can get to any other in the only way, possibly by passing through other cities. In addition, you need to pay a certain amount for driving on the road. Traveling salesman Alexey has to make $$$Q$$$ trips between pairs of cities, and he wants to find out how much money he has to spend on each trip. However, the fare is calculated by a very strange formula: all driving costs are multiplied, and then the result is taken modulo $$$10^9 + 7$$$. Since Alexey is very bad at counting, he asks you to help him. Your task is to write a program that calculates the cost of each Alexey's trip.
The first line consists of the number $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – quantity of cities in Drevlyandia.
The next $$$N - 1$$$ lines consist of information about roads. Each line has numbers $$$u, v, w~(1\le u, v \le N, 1 \le w \le 10^9, u \ne v)$$$ – numbers of the cities connected by bidirectional roads and the road fare.
The $$$(N+1)$$$-th line consists of the number $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$ – the number of Alexey's trips.
In the following $$$Q$$$ lines, there are pairs of numbers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le N, a \ne b)$$$ – the numbers of the cities between which you should calculate road fares.
Output $$$Q$$$ lines – road fares between the cities by the formula described in the problem description.
6 1 3 3 3 2 5 4 5 6 6 4 9 4 1 10 5 1 3 3 2 5 6 2 4 2 6
3 5 54 150 1350
A modern art gallery commissioned artist Malyavich to paint another masterpiece called «Complex Square». According to the terms of the order, the canvas must:
Malyavich wanted to use all shades of black to create this painting, but to his horror, he discovered that he had used all black paint to make the last masterpiece. There were only four paints left: (Yellow), orange (Orange), pink (Pink), and bright (Lime). Fearing to get something very psychedelic Malyavich decided not to mix paints and work only with these four colors.
Help Malyavich to create a masterpiece – write a program that, with given $$$n$$$, selects the appropriate $$$k$$$ and builds the map of colored squares that does not break the terms stated above or informs that a solution does not exist.
One integer number $$$n$$$ $$$( 1 \leq n \leq 1000 )$$$.
In the first line output the selected number $$$k$$$ $$$(1 \leq k \leq n)$$$ – length of the panting's side.
In the next $$$k$$$ lines output $$$k$$$ symbols. The lines should consist of Latin symbols «Y», «O», «P» or «L» indicating the color of the corresponding «pixel» of the painting. The colored squares can consist of one or several adjoining «pixels».
If there are multiple solutions, print any of them.
If a solution does not exist, output the number «$$$-1$$$» (without quotation marks).
1
1 Y
2
-1
3
-1
4
2 YO OP
Igor, Ira, and Veronica go for a walk outside every day. They especially like to walk along the alley near the house. Veronica especially likes to walk in a stroller and look at everything around her. It is important for Igor and Ira that Veronica walks as long as possible in the fresh air; that's why, when walking with a stroller, Igor and Ira prefer to go in the shade, which is made by the crowns of trees, so the sun shines less on Veronica.
One day Igor thought about a serious question, what is the area of the shade of the trees? Igor, Ira, and Veronica live in the Mathematicians' district; there are $$$n$$$ trees growing in the alley. All the trees are located on one straight line, and each $$$i$$$-th tree is defined by a center coordinate $$$x_i$$$; also, every $$$i$$$-th tree has a perfect shadow in the form of a circle with a radius $$$r_i$$$. It is reliably known that the distance between $$$i$$$-th and $$$j$$$-th trees is not less than the radiuses $$$r_i$$$ and $$$r_j$$$.
Help Igor determine the shadow area that all the trees leave.
In the first line, there is a given integer $$$n$$$ $$$(1\leq n\leq 10^3)$$$ – the amount of trees.
Then in each following line, there are given integers $$$x_i$$$, $$$r_i$$$ $$$(-10^3\leq x_i\leq 10^3, 1\leq r_i\leq 10^3)$$$ – coordinates of $$$i$$$-th tree and radius of its shadow.
It is guaranteed that all the trees have different coordinates. It is guaranteed that $$$|x_i-x_j|\geq max(r_i,r_j)$$$ is true for each $$$i$$$, $$$j$$$.
Output the area of the shaded part of the alley with an accuracy of at least $$$4$$$ decimal places.
3 0 1 2 2 8 3
42.57923071
There are quite many puzzles where one should measure the needed time interval with the help of unevenly burning Bickford (fire-conducting) fuses. For example, with a rope that entirely burns out for $$$1$$$ minute, one can measure $$$30$$$ seconds – for that, the rope should be set on fire from both sides. One can measure $$$45$$$ seconds with two such ropes (for $$$1$$$ minute each) – the first rope should be set on fire from both sides and the second only from one side – at the moment when the first rope burns down ($$$30$$$ seconds), one needs to set on fire the other end of the second rope: it will burn to the end in $$$45$$$ seconds.
Consider a more general problem: let us have $$$ n $$$ Bickford fuses with burning durations $$$ d_1, d_2, \dots, d_n $$$ . Is it possible to use them to measure the time interval $$$Time$$$, if it is allowed to set on fire these ropes either at the initial moment of time or at the moment of burning out of some other rope?
Write a program that solves this problem or informs that there is no solution. If there are several possible solutions, any of them is considered correct.
The first line contains one integer – the amount of Bickford fuses $$$ n $$$ $$$( 1 \leq n \leq 6 )$$$.
The second line contains $$$ n $$$ integers $$$ d_1, d_2, \dots, d_n $$$ $$$( 1 \leq d_i \leq 120) $$$ separated by spaces – burning duration of fuses in seconds.
The third line contains integer $$$ Time $$$ $$$( 1 \leq Time \leq 600 )$$$ – an interval in seconds that should be measured.
The first line contains the amount of used fuses $$$ k $$$ $$$( 1 \leq k \leq n )$$$, or $$$-1$$$ if the solution does not exist.
If the solution exists, there are $$$k$$$ number of lines, each containing one fractional number and three integers separated by spaces: $$$ t_{off}$$$ $$$ num $$$ $$$ t_1 $$$ $$$ t_2 $$$. Each such quad describes the moment of burning down of the fuse $$$ t_{off} $$$ (with precision to $$$ 10^{-10} $$$ sec); the number of the fuse $$$ num $$$, which sides were set on fire in moments of time with indexes $$$t_1$$$ and $$$t_2$$$. Lines should be in ascending order $$$ t_{off} $$$.
Fuses are numbered with numbers $$$ 1, 2, \dots, n $$$ in order of their appearance in input data.
Time moments are numbered with numbers $$$ 1, \dots, k $$$ in order of their appearance in output data. Index $$$0$$$ is given to the begging point of time, and index $$$-1$$$ is used instead of $$$ t_2 $$$ if the second side of the fuse is not set on fire.
If there are multiple solutions, print any of them.
2 60 60 45
2 30 1 0 0 45 2 0 1
1 10 4
-1
Veronica is a very light sleeper and reacts to every sound. Ira watches how Veronica sleeps very carefully. She keeps a diary and records how Veronica sleeps. In a few months, there were a lot of entries in the diary, as many as $$$n$$$ pieces. Each entry in the diary looks like this: $$$hh_1:mm_1:ss_1$$$ – the time when Veronica fell asleep, and $$$hh_2:mm_2:ss_2$$$ – the time when Veronica woke up.
Once the neighbor from above started drilling, making repairs, Veronica woke up from this sound and was very scared, and Veronica cried for a long time. Igor didn't like that his daughter was scared by new sounds. Igor went to deal with a neighbor. When he came to him, he explained the situation politely and showed the diary, explaining that it was highly undesirable to carry out repairs during Veronica's sleeping intervals recorded in the diary; otherwise, Igor would come to the neighbor again to solve this issue.
Help calculate how much time in seconds the neighbor has for repairs each day.
In the first line, one given integer number $$$n$$$ $$$(1\leq n\leq 10^5)$$$ is the number of sleeping intervals in Igor's diary.
Further in each line is given time of Veronika's sleep separated by spaces $$$hh_1:mm_1:ss_1$$$, $$$hh_2:mm_2:ss_2$$$ $$$(0\leq hh_1,hh_2\leq 23,0\leq mm_1,mm_2\leq 59,0\leq ss_1,ss_2\leq 59)$$$ – time of falling asleep and time of waking up.
Each Veronica's sleeping interval is guaranteed to be less than $$$24$$$ hours.
In one line, output the number of seconds for the neighbor's repairs.
5 13:00:00 14:00:00 16:00:00 17:00:00 19:00:00 20:00:00 01:00:00 05:00:00 04:00:00 05:00:00
61200
4 22:49:13 05:22:28 18:50:30 14:32:25 11:34:33 11:28:25 08:55:57 19:49:53
0
2 10:48:15 07:42:04 03:00:33 04:52:08
11171
Veronica learned to crawl, and now she needs to be carefully watched.
Igor and Ira allow her to crawl on a large mat in the room; the mat is a large rectangle with dimensions $$$n$$$ by $$$m$$$. Initially, Veronica is located somewhere on the mat and looks down in the direction of the «V» symbol. Veronica is not allowed to leave the mat and crawl on the floor.
Veronica can move on the mat only to neighboring cells and only in the direction in which she is looking. To move to the next cell, Veronica will need to spend $$$f$$$ seconds; also, Veronica can turn clockwise by $$$90$$$ degrees in $$$r$$$ seconds and turn counterclockwise by $$$90$$$ degrees in $$$l$$$ seconds.
There are several toys «*» scattered on the mat that Veronica is interested in, and several obstacles that she cannot pass or remove «$$$\#$$$»; if the cell is empty, then it is designated «.». Veronica really wants to crawl to some of her toys; it is assumed that Veronica reaches the toy if she lies in the next cell from the toy and looks in the direction of the toy.
Igor and Ira know by experience that if Veronica does not crawl to the toy in $$$t$$$ seconds, she will cry and must be picked up.
Help Igor, Ira and Veronica determine whether Veronica will be able to crawl to any toy or not.
The first line contains six integers $$$n$$$, $$$m$$$, $$$l$$$, $$$r$$$, $$$f$$$, $$$t$$$ $$$(1\leq n,m \leq 10^3, 1\leq l,r,f \leq 100,1\leq t\leq 10^6)$$$ – the width and length of the mat, the number of seconds for Veronica to turn in place clockwise and counterclockwise by $$$90$$$ degrees, the number of seconds for Veronica to move one square forward, the number of seconds that Veronica can move.
Further, a mat is given in $$$n$$$ lines, and each line has a length of $$$m$$$. All lines consist of the characters «.» – the cell is empty, «$$$\#$$$» – there is an insurmountable obstacle in the cell, «*» – there is a toy in the cell, «V» – a symbol of Veronica's location showing her original direction.
Veronica is guaranteed to be positioned correctly on the mat, and the symbol «V» occurs exactly once.
Output «YES» if Veronica manages to reach a toy; otherwise, output «NO».
4 4 10 10 10 70 .... ..V. ###. .*..
YES
4 4 5 5 10 24 .... ..V. .... .*..
NO
This is an interactive problem.
Professor R. has engaged in the study of arrays again. Today he came across an array consisting of $$$N$$$ numbers. A distinctive feature of this array is that it consists only of the numbers $$$0, 1, 2$$$. The professor decided to play the following game with his grandson. The grandson must sort the array by non-decreasing order; he can ask two types of questions:
However, the task turned out to be not so simple: the grandson can ask no more than $$$2N$$$ questions. Since the grandson knows how to sort arrays only by bubble sorting, he asks you to help him solve this problem by writing a program that sorts the array using these operations in no more than $$$2N$$$ queries.
At first, input number $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ in your program — amount elements in the array.
Then your program can make queries:
In any query, the numbers $$$i$$$ and $$$j$$$ must range from $$$1$$$ to $$$N$$$.
After sorting the array, you should output «Sorted!» to the output stream and terminate the program.
If your program makes more than $$$2N$$$ requests or sets an incorrect request (for example, requests an exchange of items whose numbers do not lie in the range from $$$1$$$ to $$$N$$$), it will receive any verdict other than «Accepted».
After each action of your program, output a newline character. After the output of another request, be sure to use the stream cleanup functions so that part of your output does not remain in some buffer. For example, in C++ it is necessary to use the function ,«fflush(stdout)», in Java and Kotlin the call «System.out.flush()» and «stdout.flush()» for Python.
2 1 0
get 1 get 2 swap 1 2 Sorted!
Hacker Kirill watched too many videos on youtube and decided to do needlework. His choice fell on a table lamp – it was decided to make creative decoration. A lampshade made of beads was chosen as a decoration. Individual beads are strung on threads, and the threads are fixed parallel to each other in between two round holders.
The lampshade consists of $$$n$$$ parallel threads. All threads have the same length, and exactly $$$k$$$ beads fit on them. The beads on the threads are placed as tightly as possible, and the threads are fixed in the same way, so the first beads are next to the first beads of neighboring threads, and the $$$k$$$-th beads are next to the $$$k$$$–th ones.
Kirill has beads in two colors – black and white. By changing their position on the threads and the order of the threads themselves, you can get different patterns. Kirill decided to design the lampshade so that two adjacent threads differed from each other in the color of exactly one bead, and there were no two identical threads.
Write a program that helps Kirill to create a scheme of a lampshade from $$$n$$$ threads, having $$$k$$$ beads on each thread, or it should inform that such a scheme does not exist.
Note since the lampshade is attached to the lamp with only one holder, the threads have a beginning, and the threads that are a reflection of each other are different. For example, the threads «BWBW» and «WBWB» are different, although the first one can be made from the second one backwards.
The input consists of two integer numbers $$$ n $$$ $$$( 2 \leq n \leq 10^4 )$$$ and $$$ k $$$ $$$( 2log_{2}n \leq k \leq 100 )$$$, separated by a space.
If there is no solution, the program should output the phrase «No solution» (without quotes).
If a solution exists, the output consists of $$$n$$$ lines of $$$k$$$ characters. Each line describes one thread of the lampshade in the order of adjacency. The first thread is considered adjacent not only to the second but also to the last.
White beads are indicated by a capital Latin «W», and black beads are indicated by a capital «B».
If there are multiple solutions, print any of them.
6 6
BWWWWW BBWWWW WBWWWW WBBWWW BBBWWW BWBWWW
Slava has a set of $$$N$$$ numbers: $$$x_1, x_2, x_3, \dots, x_n$$$. At one turn, he can get a non-empty set $$$y_1, y_2, y_3, \dots, y_m$$$, in which for any $$$i$$$ from $$$1$$$ to $$$m$$$ $$$y_i$$$ is included in the set $$$x_1, x_2, \dots, x_n$$$, and then he can add in the set $$$X$$$ sum of all products of numbers of all the possible subsets $$$y_1, y_2, \dots, y_m$$$. Slava is wondering: how many numbers not superior to $$$L$$$ exist that can be calculated by the above-described method for the finite number of actions? (For better understanding, see the note).
The first line of the input data consists of numbers $$$N$$$ and $$$L$$$ $$$(2 \le N \le 20, 1 \le L \le 10^{12})$$$.
The second line consists of $$$N$$$ numbers $$$x_i$$$ $$$(2 \le x_i \le 15)$$$.
In one line, output the number – the amount of numbers not superior to $$$L$$$ that can be calculated by the above-described method for a finite number of actions.
3 7 2 2 3
2
2 100 14 15
2
Consider set of numbers $$$X = [14, 15], L = 100$$$.
We can get set $$$Y$$$ like that:
$$$[14], [15], [14, 14], [14, 15], [15, 15], [14, 14, 14], \dots$$$
Then we get numbers:
$$$14 + 14 + 14 * 14 = 224$$$
$$$15 + 15 + 15 * 15 = 255$$$
$$$14 = 14$$$
$$$15 = 15$$$
$$$14 + 15 + 14 * 15 = 239$$$
$$$14 + 14 + 14 + 14 * 14 + 14 * 14 + 14 * 14 + 14 * 14 * 14 = 3374$$$
$$$\dots$$$
Among these numbers, only two are not superior to $$$100:~14,~15$$$.
Veronica likes to play with blocks, and she especially likes to build towers. Veronica always tries hard while building towers; she carefully builds them in one row.
This time she built $$$n$$$ towers, each of which had a height of $$$a_i$$$ blocks. After long and hard work, Veronica called her father. As a true connoisseur of art and a real mathematician, Igor has to value the beauty of all buildings at once. Igor thinks that the beauty of all the built in a row towers equals the longest increasing subsequence of their heights.
LIS (the Longest Increasing Subsequence) – is a subsequence where each next element is longer than previous one, so it is the following set of indexes $$$i_1 \ldots i_k$$$, that: $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$, $$$a[i_1] \lt a[i_2] \lt \ldots \lt a[i_k]$$$.
Veronica built quite a lot of towers, help Igor to determine the beauty of Veronica's towers.
In the first line is given an integer number $$$n$$$ $$$(1\leq n \leq 3 \cdot 10^5)$$$ – the amount of towers built by Veronica.
The next line consists of $$$n$$$ integer numbers $$$a_i$$$ $$$(1\leq a_i\leq 10^9, 1\leq i\leq n)$$$ separated by spaces – the height of towers.
In one line, output the number – sequence beauty of Veronica's towers.
5 1 3 5 2 4
3
7 10 1 5 2 6 3 4
4
Igor and Ira are waiting for their family to grow; they will be young parents very soon. The most important question at the moment is how to name the baby.
Igor and Ira argued for a long time about naming the unborn child, but they could not agree. Then they decided to make lists of names that they liked and disliked.
Igor has a list of $$$n_1$$$ names that he likes and a list of $$$m_1$$$ names that Igor does not like. Ira made lists of $$$n_2$$$ names that she likes and $$$m_2$$$ names that she doesn't like. Igor and Ira will choose a name for the future child, such that both have it in the lists of names that they like and no one has it in the lists of names that they don't like.
Help Igor and Ira to determine the names they can use to name the unborn child. Output a possible list of names in lexicographical order.
In the first line are given $$$4$$$ integer numbers $$$n_1$$$, $$$n_2$$$, $$$m_1$$$, $$$m_2$$$ $$$(1 \leq n_1,n_2 \leq 10^3, 0\leq m_1,m_2\leq 10^3)$$$ – the number of names that Igor likes, names that Ira likes, names that Igor doesn't like, names that Ira doesn't like.
All names consist of small Latin letters that are no longer than $$$20$$$ digits. Some names can be repeated in the same list.
Output all names that Igor and Ira like in alphabetical order without repeating the names.
5 4 2 3 kirill ruslan sonya veronika vasya ruslan alina sonya veronika nastya masha sasha masha natasha
ruslan sonya veronika
Veronica learned to talk. For Igor and Ira, this is the great happiness and a whole event. Now Veronica knows only $$$n$$$ words; Igor and Ira wrote down each word in a notebook as a line consisting of small Latin letters.
Igor decided to keep Veronica's first monologue. To do this, Igor wrote down in a notebook the sounds in small Latin letters that Veronica pronounced. After recording, Igor decided to check the correctness of the received line $$$s$$$, whether this line was formed from words that Veronica knows.
Help Igor determine whether he has correctly written down Veronica's monologue in his notebook.
In the first line is given the whole number $$$n$$$ $$$(1\leq n \leq 100)$$$ – the amount of words that Veronica knows.
Then there are $$$n$$$ lines consisting of words that Veronica knows.
Next is the line $$$s$$$ – Veronica's monologue, written in the notebook by Igor. All lines consist of small Latin letters.
It is guaranteed that sum of words' lengths that Veronica knows is not bigger than $$$10^5$$$.
It is guaranteed that the length of the line $$$s$$$ is not bigger than $$$10^5$$$.
Output «YES» if Veronica could pronounce line $$$s$$$; if she could not pronounce line $$$s$$$ – output «NO».
4 bububu mama papa matan bububumatanbububumama
YES