Ophelia got asked out by Hamlet today! She is beyond jubilant and wants to celebrate. She goes to her personal garden and starts picking out roses for the occasion. Ophelia is curious about the total number of petals she has counted at certain points, and as such, starts counting the number of petals for each rose she picks. Unfortunately, Ophelia is quite poor at arithmetic, and wants you to help keep track of the total number of roses at any time.
Ophelia will give you a stream of queries of two types. The first type of query will be of the form $$$R\;c_i$$$, telling you that the $$$i^{th}$$$ rose has $$$c_i$$$ petals. The second type of query will be of the form $$$T$$$, where you must output the total number of petals.
The first line will contain $$$n (1 \le n \le 10^5)$$$, the total number of queries that Ophelia has.
The next $$$n$$$ lines will each contain a query $$$R\;c_i$$$ (where $$$0 \le c_i \le 10^3$$$), or $$$T$$$.
For every query $$$T$$$, output the total number of rose petals counted up to that point on a separate line.
5 R 3 R 1 T R 2 T
4 6
Ophelia got word that Hamlet has gone missing. Yesterday was supposed to be a date with Hamlet, and now Ophelia is saddened by the fact that not only was she abandoned by her date but also that she wouldn't be able to even see him in the near future. She is now sad. Ophelia goes to her personal garden and starts picking out roses in sadness. Ophelia is curious about the average number of petals she has counted at certain points, and as such, starts counting the number of petals for each rose she picks. Unfortunately, Ophelia is quite poor at arithmetic, and wants you to help keep track of the average number of roses at any time.
Ophelia will give you a stream of queries of two types. The first type of query will be of the form $$$R\;c_i$$$, telling you that the $$$i^{th}$$$ rose has $$$c_i$$$ petals. The second type of query will be of the form $$$A$$$, where you must output the average number of petals.
The first line will contain $$$n (1 \le n \le 10^5)$$$, the total number of queries that Ophelia has.
The next $$$n$$$ lines will each contain a query $$$R\;c_i$$$ (where $$$0 \le c_i \le 10^3$$$), or $$$A$$$. It is guaranteed that a query $$$A$$$ will not be given when no roses have been counted.
For every query $$$A$$$, output the average number of rose petals counted up to that point on a separate line. Your answer for each query will be correct if it is within an absolute or relative error of $$$10^{-6}$$$.
5 R 3 R 2 A R 5 A
2.500000000 3.333333333
Juliet is anxiously waiting for Romeo to return to Verona so they can go get married. She has a garden with $$$n$$$ flower beds arranged in a circle. She starts at the flower bed $$$1$$$ and starts walking clockwise around the circle at an ever-increasing pace. If she is currently at flower bed $$$c$$$ at the start of minute $$$i$$$, by the end of that minute she will briefly stop and rest at flower bed $$$c + i$$$ and then immediately continue walking from that point at the start of the minute $$$i + 1$$$ (i.e. by the end of minute $$$1$$$ she stops and rests at flower bed $$$2$$$ and then at the start of minute $$$2$$$ she starts walking and at the end of minute $$$2$$$ she has stopped and rested at flower bed $$$4$$$). Flower bed $$$n$$$ is followed by flower bed $$$1$$$ in the circle.
Juliet could be waiting for an infinitely long amount of time because she hasn't heard at all from Romeo so the Nurse is curious if Juliet will end up stopping and resting at all the $$$n$$$ flower beds in the circle during her walk.
The input is a single line containing a single integer $$$n$$$ ($$$1 \leq n \leq 10^{4}$$$) representing the number of unique flower beds within Juliet's garden.
Output YES if Juliet will ever stop and rest at all the flower beds in her garden while waiting for Romeo and NO otherwise.
2
YES
3
NO
Double double, toil and trouble... The Weird Sisters are heating ingredients for a new concoction to mix into a big mixing pot, but their cauldron for heating recently broke! They have a list of essences to throw into a cauldron to heat in order, but they only have time to heat the cauldron a certain number of times before they need to cast their spell. Each essence needs to be fully in the cauldron (i.e. cannot be split), and all essences are in liquid form.
The Weird Sisters need to purchase a cauldron big enough to finish the spell in time, but are still economical. Can you help them find the smallest size of cauldron that will help them finish in time?
First line of input are two integers $$$1 \leq n \leq 5 \cdot 10^5$$$ and $$$1 \leq k \leq 10^6$$$, the number of essences that must be heated and the number of times they can heat respectively.
The next line contains $$$n$$$ integers, the volume of each essence $$$1 \leq a_i \leq 10^6$$$ in order that needs to be heated.
One integer $$$v$$$, the volume of cauldron needed to finish heating in $$$k$$$ rounds.
3 1 3 1 2
6
4 2 3 1 2 2
4
The historic Globe Theatre in London is the well known venue of many of Shakespeare's work. Due to the limited space in the Globe Theatre and the British national hobby of "queuing", the theatre has a very interesting seating procedure, akin to that of an airplane.
To populate the $$$N$$$ seats of the Globe, each audience member is given a ticket with a single number $$$1...N$$$. As they arrive, they're instructed to queue up, that is, stand in such a way that they are behind all lower tickets and in front of all higher tickets.
To ensure that they join in the correct ordering, the staff have instituted a special rule. As soon as an audience member joins the line, they must declare the ticket held by the person currently in front of them.
Given the order of arrivals, help the staff by determining the expected responses.
A single integer, $$$1 \leq N \leq 10^5$$$, the number of ticketholders.
The next $$$N$$$ lines each contain a ticketholder.
For each ticketholder, the ticketholder in line before them, or $$$-1$$$ if no one comes before them.
5 4 1 3 5 2
-1 -1 1 4 1
Willy Shakes was a prominent playwright, but many people never realized he had a very special process for writing 3-act plays. To streamline his writing, he would write many acts, then piece them together after the fact.
Willy would begin by writing $$$N$$$ acts. He would then rate each act on two metrics: comedy and tragedy. For act $$$i$$$, these ratings are given as two integers, $$$c_i$$$ and $$$t_i$$$. To make his plays exciting, he requires a very specific structure, in which each act is strictly more comedic and tragic than the previous.
He can pick any three acts that would follow this structure to make a play. Given the number of acts and the acts that he has written thus far, help Willy determine the number of $$$3$$$-act plays he can create.
A single integer $$$1 \leq N \leq 10^5$$$.
$$$N$$$ lines, each containing a $$$c_i$$$ and $$$t_i$$$, where $$$1 \leq c_i, t_i \leq 1000$$$.
A single integer, the number of $$$3$$$-act plays that can be made.
6 1 1 2 1 2 2 3 2 4 3 4 3
6
Make sure your values aren't overflowing :)
When the world is falling apart around her, Ophelia finds comfort in flowers and the powerful meaning possessed by each one. In fact, she likes to grow flowers in her garden and give them to her dearest friends as gifts.
Ophelia has decided to plant a new garden, in which she wants to grow $$$N$$$ unique flowers. She knows that each flower $$$f_i$$$ takes $$$d_i$$$ days to grow from a seed into a mature plant that Ophelia can then harvest and give away. So if she plants all $$$N$$$ flowers starting on the same day, it will take $$$\max\{d_1,...,d_N\}$$$ days for all of the flowers Ophelia planted to have finished maturing. However, Ophelia recently got her hands on $$$F$$$ pounds of Super-Gro medieval flower fertilizer, where each pound of fertilizer, when applied to a flower, shortens the growth time for that flower by a single day. Of course, it takes any flower at least a day to fully grow, so the Super-Gro fertilizer can't shorten the growth time below one day.
Help Ophelia grow all of her flowers as quickly as possible! If she plants the seeds for all $$$N$$$ flowers starting on the same day and makes good use of her fertilizer, what is the shortest number of days that it will take for all of Ophelia's flowers to reach maturity?
The first line of input contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, denoting the number of unique flowers Ophelia wants to plant. $$$N$$$ lines follow, each containing the unique name (consisting of all upper-case letters and no spaces) of the $$$i^{th}$$$ flower $$$f_i$$$, followed by an integer $$$d_i$$$ $$$(1 \leq d_i \leq 10^6)$$$ which is the number of days it will take for the flower $$$f_i$$$ to mature.
After those lines, the last line of input contains a single integer $$$F$$$ $$$(0 \leq F \leq 10^{12})$$$ which is the number of pounds of fertilizer Ophelia can use to accelerate the growth of her plants.
Output a single integer that is the minimum number of days it will take for Ophelia's flowers to all reach maturity.
7 ROSEMARY 10 PANSY 14 FENNEL 7 COLUMBINE 12 RUE 6 DAISY 7 VIOLET 3 37
4
Ophelia can achieve an optimal growth time of $$$4$$$ days in this example by using $$$6$$$ lbs of fertilizer on the rosemary, $$$10$$$ on the pansy, $$$3$$$ on the fennel, $$$8$$$ on the columbine, $$$2$$$ on the rue, $$$3$$$ on the daisy, and $$$0$$$ on the violet. This uses only $$$32$$$ out of her $$$37$$$ pounds of fertilizer.
After the death of her father Polonius, coupled with her troubles with Hamlet, Ophelia has descended into madness. Unable to comprehend everything that is happening, she decides to retreat from the world. Ophelia goes to her personal garden and starts picking out roses in madness. Ophelia is curious about confidence intervals for the average number of petals as she goes through roses, and as such, she starts counting the number of petals for each rose she picks. Unfortunately, Ophelia is quite poor at mathematics, and wants you to help with this task.
Ophelia will give you a stream of queries of two types. The first type of query will be of the form $$$R\;c_i$$$, telling you that the $$$i^{th}$$$ rose has $$$c_i$$$ petals. The second type of query will be of the form $$$C\;t_i$$$, where Ophelia wants a $$$95\%$$$ confidence interval for the true average of the number of rose petals, based on the last $$$t_i$$$ roses. More specifically, let $$$\mu$$$ be the average of the last $$$t_i$$$ roses, and $$$\sigma$$$ be the standard deviation for the last $$$t_i$$$ roses. Then, to get a $$$95\%$$$ confidence interval, we would want $$$(\mu - 2\sigma_{\bar{x}}, \mu + 2\sigma_{\bar{x}})$$$.
Note: the confidence interval $$$(\mu - 2\sigma_{\bar{x}}, \mu + 2\sigma_{\bar{x}})$$$ is not exactly a $$$95\%$$$ confidence interval, but we will use this as an approximation for it. The standard deviation for a set of elements is defined as $$$$$$\sigma = \sqrt{\dfrac{\sum_{i = 1}^n (x_i - \mu)^2}{n}}$$$$$$ where $$$n$$$ is the total number of elements. Then, $$$$$$\sigma_{\bar{x}} = \dfrac{\sigma}{\sqrt{n}}$$$$$$
The first line will contain $$$n (1 \le n \le 10^5)$$$, the total number of queries that Ophelia has.
The next $$$n$$$ lines will each contain a query $$$R\;c_i$$$ (where $$$0 \le c_i \le 10^3$$$), or $$$I\;t_i$$$ (where $$$2 \le t_i \le n_i$$$, where $$$n_i$$$ is the number of queries of the first type thus far).
For every query $$$I\;t_i$$$, output $$$\mu - 2\sigma, \mu + 2\sigma$$$ space separated on a separate line. Your answer for each query will be correct if it is within an absolute or relative error of $$$10^{-6}$$$.
5 R 3 R 1 I 2 R 2 I 2
0.585786438 3.414213562 0.792893219 2.207106781
From Witches Cauldron I:
Double double, toil, and trouble... The Weird Sisters are heating ingredients for a new concoction to mix into a big mixing pot, but their cauldron for heating recently broke! They have a list of essences to throw into a cauldron to heat, but they only have time to heat the cauldron a certain number of times before they need to cast their spell. Each essence needs to be fully in the cauldron (i.e. cannot be split), and all essences are in liquid form.
New:
... fire burn and cauldron bubble. The Witches, with your help, have purchased a cauldron. However, they come to the sudden realization that they actually do not need to heat the essences in a specific order, since they are putting them all into the mixing pot at the end anyway!
With this new information, the Weird Sisters would like you to help them figure out how many times they need to heat the cauldron given that they can heat the essences in any order.
The first line contains two integers, $$$1 \leq n \leq 20$$$ and $$$1 \leq k \leq 10^9$$$, the number of essences and the size of the cauldron respectively.
The next line contains $$$n$$$ integers, the volumes of each essence $$$1 \leq a_i \leq k$$$.
A single integer representing the minimum number of times the cauldron needs to be heated to mix all the essences after ordering in an optimal way.
4 10 4 8 6 2
2
10 100 36 16 7 33 2 53 25 48 32 11
3
Hamlet is particularly annoyed with his treacherous 'friends' Rosencrantz and Guildenstern and as they set off on their journey to England, he decides to hand them a challenge that they must solve correctly in order to be welcome back in Denmark. Hamlet, ever a scholar of the math and sciences, decides that he wants to know how many values of $$$k$$$ satisfy the equation:
The first and only line contains four space-separated integers $$$p, x, y, a$$$ where $$$p$$$ is guaranteed to be a prime, $$$2 \leq p \leq 10^{6} + 3$$$, $$$1 \leq x, y, \leq p - 1$$$, and $$$1 \leq a \leq 10^{12}$$$.
Output a single answer representing the number of possible values $$$k$$$ which satisfy the puzzle.
5 2 3 10
3
7 4 6 13
1
In the first test case, we see that $$$k = 2$$$, $$$k = 8$$$ and $$$k = 9$$$ are valid assignments to satisfy the equation.