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.
Egypt's Queen, Cleopatra, has seduced Mark Antony, one of the triumvirs of the Roman Republic. Rome's domestic problems have put the empire in dire straits, but Cleopatra begs Antony to stay with her in Alexandria. Antony proposes that they play a parlor game to decide if he stays; if Cleopatra wins, he will stay, but otherwise, Antony will leave.
The game is played upon a table with $$$N$$$ card-shaped spaces, and every space has a positive integer at most $$$100$$$ engraved in it. Each player is initially dealt $$$N$$$ cards, and a single random integer in the range $$$[1, 10^{100}]$$$ is written on every card. Cleopatra will begin by viewing the number engraved on each space, and then will place exactly one card into every space on the table. Antony will then view the numbers and positions of Cleopatra's cards on the table in addition to the engraved numbers, and place his cards in the same fashion as Cleopatra. For each space, the player with the higher number on their card within that space receives points equivalent to the number engraved in the space. If both players place the same number on a space, no one gets any points.
Given that Antony plays optimally, Cleopatra would like to know the expected number of points she will score if she uses the highest scoring strategy to assess the likelihood of Antony staying. Can you help the Queen of Egypt?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100$$$) as described above. The second line of input contains $$$N$$$ space-separated positive integers at most $$$100$$$ that denote the numbers engraved into the spaces on the playing table.
Print a single number representing the expected number of points Cleopatra will score in the game. Answers within $$$10^{-6}$$$ of the true expectation will be accepted.
2 1 2
1.3333333333
3 5 7 11
9.2000000000
King Henry V is marching out to war against the French with his fierce and valiant army! He has $$$n$$$ soldiers that are standing together side to side in a line, and he wishes to take contiguous subarrays of these soldiers to form attack squadrons and effectively lead his army into war.
Each of the $$$n$$$ soldiers has a Duke that they pledge fealty to, given by a specific type, $$$t_i$$$. If two soldiers share the same $$$t_i$$$ value, they pledge fealty to the same Duke. To avoid potential rebellion, King Henry wants to avoid picking a squadron that has over $$$k$$$ soldiers that pledge fealty to the same Duke. Also, to ensure each attack squadron has sufficient camaraderie, if there exists some soldier in the squadron that pledges fealty to a specific Duke, there must exist $$$k$$$ soldiers that pledge fealty to that Duke so that each soldier has company. To summarize these constraints, there must be either $$$0$$$ soldiers that pledge fealty or $$$k$$$ soldiers that pledge fealty for any given Duke in a valid attack squadron.
Given these constraints, King Henry wants to know the number of possible attack squadrons that he can form successfully. Write a program to calculate the answer!
The first line consists of two integers $$$n$$$ and $$$k$$$ $$$(1 \leq k, n \leq 10^5)$$$. The next line consists of $$$n$$$ space separated integers $$$t_i$$$ $$$(1 \leq t_i \leq 10^5)$$$, which gives the ID of the Duke that the $$$i$$$th solider in line pledges fealty to.
Output a single integer giving the number of possible squadrons that King Henry V can form.
5 3 1 1 1 1 1
3
5 1 1 1 2 2 3
7
In the first sample, any subarray of size $$$3$$$ is valid.
In the second sample, all of the subarrays with a single element and the subarrays $$$[1, 2]$$$ and $$$[2, 3]$$$ will satisfy King Henry V's desired property.