Filiberto is very careful when giving gifts to any of his friends.
He has found in the street a string $$$S$$$ containing only lowercase English characters and he remembered that his friend Alan is a lover of strings!
When Alan sees a string, he immediately searches in his very weird dictionary (one that contains all the possible string letters) for that word in lexicographically order until he finds it and learns its meaning. But Alan does not like to spend a lot of time looking in the dictionary or he will become angry.
As Alan's birthday is coming soon, Filiberto wants to give him the string $$$S$$$ as a gift, but he does not want Alan to become angry because it could take a lot of time to look for its meaning in the dictionary.
Filiberto can rearrange the string $$$S$$$ by changing the order of the characters of the string. As Filiberto is focused on creating new problems for the 11th edition of the Annual Programming Contest, he asks you to solve the following problem:
Given the string $$$S$$$, you need to print the best rearrangement of the string to give to Alan as a gift.
The first contains an integer $$$N$$$ $$$(1 \le N \le 10^7)$$$ - representing the length of the string.
The second line contains a string $$$S$$$ consisting of lowercase English characters - the string Filiberto has found in the street.
Output one line containing the best rearrangement of the string $$$S$$$ to give to Alan as a gift.
3 mac
acm
4 geso
egos
Alice and Bob love playing the classic Nim game, in which the two players take turns removing stones from distinct piles. In each turn, a player must remove a positive number of stones from a single pile. The player that cannot make a move loses the game.
But now there is a problem: they don't have any piles of stones to play with! So, they are thinking of buying some piles of stones in the Nim Store. Nim Store offers piles inside a box, so that its size is unknown until the client pays for it. It is known that there are $$$K$$$ possible sizes for the piles: $$$c_1, c_2, ..., c_k$$$, and all of them can be chosen with the same probability.
Alice always makes the first move when playing with Bob, so she is wondering what is the probability to have a winning strategy, if they buy $$$M$$$ piles of stones, assuming that the number of stones in the piles is equiprobable and the size of the piles is independent from each other.
Help Alice to calculate this probability. It can be shown that it is in the form of a fraction $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q \neq 0$$$, $$$P \leq Q$$$. Output the value of $$$P*Q^{-1} \mod 998244353$$$.
The first line contains two integers numbers $$$M$$$ and $$$K$$$ ($$$1 \leq M \leq 10^9$$$, $$$1 \leq K \lt 2^{17}$$$) - the number of piles that Alice and Bob are going to buy and the number of different sizes of the piles.
The second line contains $$$K$$$ different integers numbers $$$c_1, c_2, ..., c_k$$$ ($$$1 \leq c_i \lt 2^{17}$$$) - the size of piles offered by Nim store.
Print one integer $$$P*Q^{-1}$$$ - the probability that Alice has a winning strategy modulo $$$998244353$$$.
2 2 1 3
499122177
11 1 5
1
7 3 1 2 3
50665352
In the first sample, Alice and Bob are buying two piles, and the possible sizes for them are $$$1$$$ and $$$3$$$. The possible ordered combinations of sizes are $$$(1,3)$$$, $$$(3,1)$$$ $$$(1,1)$$$ and $$$(3,3)$$$. It can be shown that Alice only has a winning strategy in $$$(1,3)$$$ and $$$(3,1)$$$. So, the probability is $$$\frac{1}{2}$$$.
While in his circuits class, Oscar was asked to build the following circuit:
That is:
- We have a DC (Direct Current) voltage source of $$$V$$$ Volts that feeds the whole circuit.
- There is a capacitor of capacitance $$$C$$$ Farads and an inductor of inductance $$$L$$$ Henrys, both connected in parallel.
- We have a resistor of resistance $$$R$$$ Ohms connected in series with the previous block.
- The initial current of the inductor and the initial voltage of the capacitor are both zero.
And then he was asked to measure the voltage $$$V_r(t)$$$ in the resistor, by varing all the parameters. To accomplish that, he will use the oscilloscope available in the electronic lab to graph the value of $$$V_r(t)$$$ with respect to time (in seconds). He noticed some amazing pattern: $$$V_r(t)$$$ tends to stabilize at the value of the voltage input $$$V$$$ after some few seconds of oscillation, no matter what are the values of $$$R,L,C$$$ (but they must satisfy $$$L \lt 4R^2 C$$$), as shown in the graph below (the graph corresponds to the sample test case):
Oscar doesn't like at all that this behaviour tends to overshot and undershot the voltage $$$V_r(t)$$$ because that's bad in many daily-life applications (for example, in analog filters it can damage all the electronic elements due to the excesive voltage). He also doesn't have many resistors, inductors nor capacitors in his toolbox to experiment, so he asks you to find the minimum and maximum values for $$$V_r(t)$$$ and the time at which they ocurr before it stabilizes, without having to build physically the circuit.
In the only line of input there are four space-separated real numbers: $$$V$$$, $$$R$$$, $$$L$$$ and $$$C$$$, the parameters of the circuit described above. It is guaranteed that $$$1 \leq V \leq 20$$$, $$$0.1 \leq R, L, C \leq 20$$$ and $$$L \lt 4R^2 C$$$.
Print two lines of output, each with two real numbers:
- In the first line: the time in seconds at which the minimum value occurs and then the minimum value itself in Volts.
- In the second line: the time in seconds at which the maximum value occurs and then the maximum value itself in Volts.
The absolute or relative error of the answers should not exceed $$$10^{-6}$$$.
6 3.7 0.3 0.2
0.348848049 4.430980248 1.129139119 6.926100394
Here is a quick remainder about how circuits work:
- The current flowing into a node must be the same as current flowing out of that node. For example, in the above circuit, we have $$$I_r(t)=I_l(t)+I_c(t)$$$.
- Around a closed loop, the sum of the voltage rises must be equal to the sum of the voltage drops. For example, in the above circuit, we have $$$V = V_r(t) + V_l(t)$$$ and $$$V_c(t) = V_l(t)$$$.
- The governing law of the three elements presented in the above circuit is:
- For resistor with resistance $$$R$$$ Ohms, we have $$$V_r(t)=RI_r(t)$$$.
- For an inductor with inductance $$$L$$$ Henrys, we have $$$V_l(t)=L\frac{d}{dt}I_l(t)$$$.
- For a capacitor with capacitance $$$C$$$ Farads, we have $$$I_c(t)=C\frac{d}{dt}V_c(t)$$$.
Recently, a startup by a group of students has become more popular and there are plans for expanded offices. Bryan got an internship in this company and his task is to manage its internal network.
The company will acquire some computers over time. Initially, there is only a computer with $$$id=1$$$. When a new computer is added to the network, it's directly connected to a computer with $$$id=p$$$. The $$$id$$$ of the new computer is the minimum positive integer that has not been used as the $$$id$$$ of any other computer.
To determine the performance of the internal network, Bryan is required to answer several queries about what is the minimum number of computers through which a message must go if it is sent from computer with $$$id=u$$$ to computer with $$$id=v$$$ (start and end are also counted). Also, when a new computer is added, Bryan has to determine this number for a message sent from the new computer to the computer with $$$id=1$$$, since it is the most important computer. The computers have enough information to determine the optimum way to send a message to another computer.
Since there could be many computers in the network, Bryan needs your help to write a program that answers the queries. Note that the queries are encoded.
The first line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2*10^5$$$) $$$-$$$ the number of queries.
Each of the next $$$Q$$$ line describes a query. It contains a integer $$$t$$$ ($$$t \in [1,2]$$$) $$$-$$$ the type of query.
The queries will be encoded. Let $$$last$$$ be the answer for the last query answered and let $$$curr$$$ be the number of computers connected in the network so far. Initially $$$last=0$$$ and $$$curr=1$$$.
- If $$$t=1$$$, then one integer $$$p'$$$ follows ($$$0 \leq p' \leq 2*10^5$$$). Set $$$p=(p'+last)\%curr+1$$$. It means that a new computer is connected to the computer with $$$id=p$$$. Increase the value of $$$curr$$$ by one.
- If $$$t=2$$$, then two integers $$$u'$$$ and $$$v'$$$ follow ($$$0 \leq u', v' \leq 2*10^5$$$). Set $$$u=(u'+last)\%curr+1$$$ and $$$v=(v'+last)\%curr+1$$$. It means that a message is sent from computer $$$u$$$ to computer $$$v$$$.
If the query is of type $$$1$$$, print the number of computers through which a message must go if it is sent from the new computer to computer with $$$id = 1$$$.
Otherwise print the amount of computers through which the message must go if it is sent from computer $$$u$$$ to computer $$$v$$$.
7 1 0 1 2 1 2 1 2 2 0 4 2 1 2 2 2 1
2 2 3 3 4 2 3
6 1 1 2 1 2 1 0 1 1 2 0 3 2 2 2
2 2 2 2 3 1
In the first sample, the new computers are connected as follows
- Add new computer with $$$id=2$$$ and connect it to computer with $$$id=1$$$.
- Add new computer with $$$id=3$$$ and connect it to computer with $$$id=1$$$.
- Add new computer with $$$id=4$$$ and connect it to computer with $$$id=2$$$.
- Add new computer with $$$id=5$$$ and connect it to computer with $$$id=2$$$.
And actual queries of the second type are:
- $$$u=4$$$ and $$$v=3$$$
- $$$u=1$$$ and $$$v=2$$$
- $$$u=5$$$ and $$$v=4$$$
Last month in Mexico City there were a lot of forest fires and air quality in the capital was terrible for human bodies.
Air quality is measured with the Air Quality Index, or AQI. The AQI works like a thermometer that runs from 0 to 500 degrees. However, instead of showing changes in the temperature, the AQI is a way of showing changes in the amount of pollution in the air.
As the AQI was very high, government recommended to people to avoid outdoor activities or they could be exposed to some diseases. As air quality worsened day by day, the government of the capital decided to suspend classes for a couple of days because the situation could be dangerous for children and teenagers.
Now, they are worried about missing a lot of classes such that children will be less prepared for the future. They have built an artificial intelligence that predicts the AQI for $$$N$$$ days and they need you to solve the following problem:
Given the AQI for the next $$$N$$$ days, the name of the beginning day and a number $$$X$$$ (representing the minimum number of AQI such that on that specific day classes will be suspended), print the number of days such that classes will be suspended.
Each day name will be represented by any of the following strings: "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" and "Sunday" (without the double quotes).
Please note that there are no classes on weekends in Mexico City.
The first line contains $$$N$$$, $$$dayName$$$ and $$$X$$$ $$$(1 \le N \le 10^6, 0 \le X \le 500)$$$ - representing the number of days, the first day's name and the minimum amount of AQI such that classes will be suspended.
Second line contains $$$N$$$ integers $$$a_i$$$ $$$(0 \le a_i \le 500)$$$ - The AQI for each of the $$$N$$$ days.
Print the number of days such that classes will be suspended.
10 Wednesday 6 1 2 3 4 5 6 7 8 9 10
5
5 Saturday 223 90 372 191 282 223
2
5 Sunday 269 90 372 191 282 223
2
In the first test case the only days that are greater or equal than 6 are the last five elements. These days are also weekdays.
In the second test case three AQI days are greater or equal than 223, but the second day is Sunday and classes won't be suspended on this day because there are no classes on weekends in Mexico City.
As you may know, Freddy is a big fan of chocolate, so he decided to open his own Chocolate factory.
He has been working for several months without any issues but this week he faced a problem. The chocolate machine is not working correctly.
He usually produces $$$a$$$ chocolates per day but the machine is defective now, so it can currently produce $$$b$$$ chocolates each day.
In order to fix the machine, Freddy will need $$$k$$$ consecutive days to do maintenance; he can not produce any chocolate during this time neither sell any of them, but after finishing, the chocolate factory will be restored to its full production.
Initially, no orders are pending. The factory receives updates of the form $$$d_i$$$, $$$a_i$$$ indicating that $$$a_i$$$ chocolates have been requested for the $$$d_i$$$-th day (adding this quantity to the previous number of chocolates requested on this day). The owner can decide to sell as many or as few chocolates in each of the days. Note that chocolates produced on a day $$$i$$$ can be used in later days.
As orders come in, Freddy would like to know the maximum number of chocolates he will be able to sell if the maintenance starts on a given day $$$p_i$$$.
Help Freddy answer these questions.
The first line contains five integers $$$n$$$, $$$k$$$, $$$a$$$, $$$b$$$ and $$$q$$$ ($$$1 \le k \le n \le 10^{5}$$$, $$$1 \le b \lt a \le 10^{5}$$$, $$$1 \le q \le 2*10^{5}$$$) - the number of days, the length of the repair time, the production rates of the factory, and the number of updates, respectively.
The next $$$q$$$ lines contain the descriptions of the queries. Each query is of one of the following two forms:
$$$\bullet$$$ 1 $$$d_i$$$ $$$a_i$$$ ($$$1 \le d_i \le n$$$, $$$1\le a_i \le 10^{4}$$$), representing an update of $$$a_i$$$ chocolates on day $$$d_i$$$, or
$$$\bullet$$$ 2 $$$p_i$$$ ($$$1 \le p_i \le n - k + 1$$$), representing a question: at the moment, how many chocolates can be sold if Freddy decides to start maintenance on day $$$p_i$$$?
It's guaranteed that the input will contain at least one query of the second type.
For each query of the second type, print a line containing a single integer — the maximum number of chocolates that the factory can sell all $$$n$$$ days.
5 2 2 1 8 1 1 2 1 5 3 1 2 1 2 2 1 4 2 1 3 2 2 1 2 3
4 6 4
Abraham and Filiberto have been arguing a lot during the last two months. They haven't decided which problems are going to be used in the 11th edition of the Annual Programming Contest.
As the date of the competition is coming soon, they both prepared different problem sets and now they have several problems that can be used in this contest. Both of them labeled their problems by difficulty $$$d$$$ and have arrange them into 2 different arrays, proposing the order that the problems should have during the competition.
Abraham and Filiberto are both very foolish, they proposed the order of the problems and don't want to change it in any way. That means that if a problem $$$A$$$ appears before a problem $$$B$$$ in the original array proposal, then in the final problem set, $$$A$$$ has to appear before problem $$$B$$$.
After some time of discussing how to choose the problems for the competition, they agreed with the following deal:
- They will choose the same quantity of problems from both proposals.
- If a problem with difficulty $$$D$$$ is chosen from Abraham's array, then a problem with the same difficulty must be chosen from Filiberto's array.
- Problems must be ordered by strictly increasing difficulty in the final problem set.
- And the order of problems in the final problem set, has to preserve the original order in the arrays proposal.
They want to maximize the number of problems that can be used in this competition.
As they are very tired to solve this problem, they ask for your help to compute the answer.
The first line contains two integer numbers $$$n$$$ and $$$m$$$ $$$(1 \le n,m \le 10^4)$$$ - size of Filiberto and Abraham's arrays proposal.
Second line contains $$$n$$$ integers $$$d_i$$$ $$$(1 \le d_i \le 10^9)$$$ - representing the difficulties of Filiberto's array proposal.
Next line contains $$$m$$$ integers $$$x_i$$$ $$$(1 \le x_i \le 10^9)$$$ - representing the difficulties of Abraham's array proposal.
Print one integer - maximum number of problems that can be used in the competition.
6 5 1 2 1 2 1 3 2 1 3 2 1
4
In the test case you can select 1st and 6th element from the first array and 2nd and 3rd from the second array.
The final problem set difficulties will look as: [1, 1, 3, 3].
Note that numbers marked as bold belong to Abraham's array proposal and they appear in the same order as in the original array.
Studying at ESCOM is not easy, sometimes you can feel a stressful environment almost everywhere! But to get over it, our friend Laura and her boyfriend Lalo decided to create a local radio station called Heartbreaker, where they transmit news about the daily life in ESCOM, some good music and podcasts too.
To make that possible, Lalo concluded that they will need to transmit $$$n$$$ sinusoidal waves with the same angular frequency $$$\omega$$$ (in $$$\text{rad}/\text{s}$$$), each with his own amplitude $$$A_i$$$ and phase $$$\phi_i$$$ (in $$$\text{rad}$$$). That is, the $$$i^{th}$$$ wave will be of the form $$$f_i(t)=A_i \sin(\omega t + \phi_i)$$$, and they will transmit the new wave given by the sum $$$f(t)=f_1(t)+f_2(t)+\cdots+f_n(t)$$$.
But suddenly Laura notices that it will be very expensive to transmit all these $$$n$$$ waves at the same time, so she thinks of the wonderful fact that they can find another single sinusoidal wave with the same frequency of the form $$$A \sin(\omega t + \phi)$$$ which is equivalent to transmit each of the $$$n$$$ waves individually, so they will only have to transmit one wave! Help them to find that mysterious wave.
The first line contains two values: the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and the angular frequency $$$\omega$$$ of all the waves given by a real number $$$(0.1 \leq \omega \leq 100)$$$.
The next $$$n$$$ lines contain two real numbers $$$A_i$$$ ($$$0.1 \leq A_i \leq 100$$$) and $$$\phi_i$$$ ($$$0 \leq \phi_i \lt 2\pi$$$), indicating the amplitude and the phase of the $$$i^{th}$$$ wave.
Output one line with two real values: $$$A$$$ ($$$A \geq 0$$$) and $$$\phi$$$ ($$$0 \leq \phi \lt 2\pi$$$), the amplitude and the phase of the resulting wave. The absolute or relative error of the answers should not exceed $$$10^{-6}$$$.
8 66.82 93.22 5.53 48.58 0.86 15.31 5.39 5.66 4.12 48.53 6.09 6.60 1.42 21.15 0.06 4.27 5.47
185.184472750 6.019915094
Today is Princess Star's birthday, she's now 14 years old! As the tradition says, she will be given both the magic wand and the book of spells that have been inherited in his family from generation to generation, so she can train and become the new Queen of the kingdom of Mewni soon.
But bad things happened, she couldn't control all of the power of the magic wand and almost destroys everything! So, in order to keep her safe (and all the people of the kingdom), her parents decide to send her to the safest possible place of the universe: the Earth, so she can train there, learn to use his magic powers and go to school.
Her magic wand works as follows: suppose that in the $$$i^{th}$$$ day it has a capacity of $$$c_i$$$ units, and for every spell that she does, she uses one unit. Of course, if the capacity goes to zero, she won't be able to use it in the rest of that day.
She will be in Earth for exactly $$$n$$$ days numbered from $$$0$$$ to $$$n-1$$$. Her parents will give her $$$n^2$$$ units of capacity distributed among the $$$n$$$ days in the following manner: every pair $$$(i,j)$$$ such that $$$0 \leq i,j \lt n$$$ will contribute to the day with number $$$d_{i,j}$$$ one unit of capacity, where $$$d_{i,j}=(i \times j)\text{ mod }n$$$.
If she passes this easy task, she will be able to return. As a good human, help her to determine the daily capacity of her magic wand while she's at Earth.
The first and only line contains the value of $$$n$$$ ($$$1 \leq n \leq 2.2 \times 10^6$$$), the number of days that Star will be at Earth. Yes, most of the princesses in Mewni live that long!
Output $$$n$$$ lines, each containing the values of $$$c_0, c_1, \ldots, c_{n-1}$$$ in that order.
6
15 2 6 5 6 2
You're given two positive integers $$$A$$$ and $$$B$$$, and a string $$$P$$$, representing their product but with a missing digit indicated with an $$$*$$$. Find the missing digit.
It's guaranteed that the missing digit isn't $$$0$$$.
The first line contains three integers $$$a$$$, $$$b$$$ and $$$p$$$ ($$$1 \leq a, b \lt 10^6$$$, $$$1 \leq p \lt 2*10^6$$$) $$$-$$$ the number of digits in $$$A$$$, $$$B$$$ and $$$P$$$ respectively.
The second line contains positive number $$$A$$$.
The third line contains positive number $$$B$$$.
The fourth line contains string $$$P$$$ $$$-$$$ the product of $$$A$$$ and $$$B$$$ with a missing digit.
Print one integer representing the missing digit in $$$P$$$.
1 1 2 3 8 2*
4
2 2 3 10 10 *00
1