After an arduous journey through pirate-infested waters, you have finally reached the legendary treasure of Long John Silver. Before you can open the treasure chest, Long John Silver's trusty parrot, Captain Flint swoops down and demands that you solve his math riddle to prove you are worthy of the vast gold Long John Silver left behind. (Below are multiple interpretations of Captain Flint)
Captain Flint tells you that he is currently thinking of a number $$$n$$$ between $$$2$$$ and $$$100$$$ (inclusive). You find out that you may ask him up to $$$20$$$ queries to figure out if the number that he is thinking of is prime or composite. If you guess wrong, give an invalid query, or try to use too many queries, he will tell Long John Silver that you are stealing his gold and Long John Silver is highly protective of his stash so this would not be good.
Captain Flint lets you ask queries of the following type: you can give him a number $$$i$$$ between $$$2$$$ and $$$100$$$ (inclusive) and he will tell you if $$$n$$$ is divisible by $$$i$$$. Given that you have traveled this far for this treasure you want to be absolutely sure that you get the treasure so write an interactive program to determine if Captain Flint's number $$$n$$$ is prime or not.
You can ask a query of the form ? i up to $$$20$$$ times where $$$2 \leq i \leq 100$$$. Make sure that when you print the query you include the end of line character and flush the output. In response, you will receive the string yes if $$$n$$$ is divisible by $$$i$$$ and no otherwise.
When you think you know whether or not $$$n$$$ is prime, you print the answer in the form ! prime if $$$n$$$ is prime and ! composite if not and then stop your program.
To flush you can use the following commands (after printing an integer and end-of-line):
- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
no yes yes
? 50 ? 2 ? 15 ! composite
In the given example, $$$n$$$ is $$$30$$$ so for the first query, $$$50$$$ is not a divisor of $$$30$$$ so it prints no. Then, the next two queries are both divisors of $$$30$$$ so it prints yes both times at which point you know that $$$n$$$ must be composite.
You have recently started a bird-watching tour company! After hiring tour guides and stocking up on binoculars, it's time to talk business.
You know of $$$n$$$ excellent trails in the area. Although the birds come and go, trail $$$i$$$ can have anywhere between $$$a_i$$$ and $$$b_i$$$ birds at any point in time.
We consider two trips to be different if they occur on different paths, or if they encounter different numbers of birds.
You currently have $$$m$$$ potential customers, who each have very specific preferences. Customer $$$i$$$ hopes to see between $$$c_i$$$ and $$$d_i$$$ birds on their trips ($$$1 \leq c_i \leq d_i \leq 10^5$$$). You home to tell these customers how many unique trips could satisfy their specifications, to attract them to your business.
Given $$$N$$$, $$$M$$$, and the associated bird quanitities, help each customer determine how many unique trips matching their specifications they could experience.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^5)$$$, representing the number of known trails, and the number of customers respectively.
The next $$$n$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i \leq b_i \leq 10^5$$$), the number of birds that each trail could have.
The next $$$m$$$ lines contain two integers $$$c_i$$$ and $$$d_i$$$ ($$$1 \leq c_i \leq d_i \leq 10^5$$$), the number of birds each customer hopes to see.
Output $$$m$$$ lines, where the $$$i$$$-th line describes how many unique trips match customer $$$i$$$'s specifications.
3 2 1 8 2 5 5 8 1 3 5 5
5 3
The phoenix is an immortal bird from the folklore of various cultures. In particular, it has the interesting property that when it dies, it bursts into flames and then is reborn from the ashes.
Barblewindow has just acquired himself a baby phoenix, and wishes to track its development. Every day, he records the age of his phoenix in days. Whenever the phoenix dies and is reborn, he restarts the count (i.e. the phoenix is 0 days old on the day it dies and is reborn).
Unfortunately, during one of the phoenix's rebirths, Barblewindow's notes caught fire, so some of his records are missing. Barblewindow knows that a phoenix can only die after it is at least $$$K$$$ days old. Given the remaining records, can you help him determine the maximum number of times his phoenix could have been reborn?
The first line contains two integers $$$N, K$$$, where $$$N$$$ total days have passed since Barblewindow first acquired his phoenix, and a phoenix can only die after it is at least $$$K$$$ days old. $$$(2 \le N \le 10^6, 2 \le K \le N)$$$
The next line contains $$$N$$$ space-separated integers $$$a_1,a_2,...,a_N$$$ $$$(-1 \le a_i \le N)$$$ where:
- $$$a_i = -1$$$ if the $$$i$$$th day's records are missing, or
- the phoenix was $$$a_i$$$ days old on day $$$i$$$ otherwise.
Output a single integer denoting the maximum number of times Barblewindow's phoenix could have been reborn. We consider the phoenix's initial birth (day 0) to be a rebirth.
10 3 0 -1 -1 3 -1 -1 -1 -1 -1 1
3
In the first example, one way to fill in the missing records is as follows: $$$[0, 1, 2, 3, 4, 0, 1, 2, 0, 1]$$$, which corresponds to 3 rebirths including the initial birth.
Doves like to dance. Doves like to go to dances with other doves. Sometimes dove dances look like this:
Today, the doves have planned a dove dance! Dove dances occur sequentially, that is, as a series of events over time. The doves have planned for a dove dance of length $$$Q$$$ units of time.
It just so happens that you have been hired as the bouncer for the dove dance! As the bouncer, it is your responsibility to keep track of the names of the doves that are present at the dove dance.
Initially, the dance has zero doves present. At each point in time, it is possible that a dove may show up at the dance. When this happens, the dove will tell you its name, a string of lowercase English letters ("a"-"z"). We will call these queries of type 1.
Another possible event which can happen at a given point in time is a complaint. Sometimes, doves tend to get too groovy on the dance floor and another dove will report the name of the offending dove to you, the bouncer. If this is the case, it is your responsibility to report back whether or not the name of the offending dove is a prefix of the names of any doves which are currently at the dove dance. Note that the name reported to you need not be the name of any of the doves at the dance, and also note that, being the kind and wholesome bouncer you are, you will never end up removing any doves from the dance.
However, doves are fickle creatures, and sometimes they enjoy changing their identities at whim. The third and final possibility of an event that can happen at a given point in time is that the doves will collectively decide to change their names by doing a little dove twirl. When a dove twirl occurs, all of the doves who are currently at the dance will reverse their names and take on their new identities. We will call these queries of type 3.
The first line of input will consist of a single integer $$$Q\ (1 \leq Q \leq 10^5)$$$, denoting the number of queries. The next $$$Q$$$ lines of input will consist of a single query. Each query line will be in either the form $$$1\ S$$$, $$$2\ T$$$, or $$$3$$$ where $$$\sum{|S|}, \sum{|T|} \leq 10^5$$$. A query of type 1 denotes that dove with a name of $$$S$$$ appears at the dance. A query of type 2 asks whether $$$T$$$ is a prefix of any of the names of doves at the dance. A query of type 3 denotes a reversal of all names of doves currently at the dance.
For each query of type 2, the output should contain a single line containing either a $$$0$$$ or a $$$1$$$ depending on whether or not the queried dove appeared at the dance or not.
5 1 alice 2 alice 3 2 ali 2 ecil
1 0 1
The sample case follows the following sequence of events:
At the first point in time, a dove named "alice" appears at the dance.
At the second point in time, a dove complains to the bouncer regarding a dove named "alice", and the bouncer reports back "1" since "alice" is a prefix of "alice".
At the third point in time, all doves currently at the dance reverse their names, so the only dove at the dance is now named "ecila".
At the fourth point in time, a dove complains to the bouncer regarding a dove named "ali", and the bouncer reports back "0" since "ali" is not a prefix of "ecila".
At the fifth point in time, a dove complains to the bouncer regarding a dove named "ecil", and the bouncer reports back "1" since "ecil" is a prefix of "ecila".
Albatross is a recent fledgling, looking to find a tree of her own to settle down in. As she scours the land, she finds the perfect tree to call her own.
As she approaches the tree, she sees $$$n$$$ different landing locations, connected to each other by $$$n-1$$$ branches. However, as she prepares to land on the tree, she quickly realizes something: this tree has already been claimed by Barbet, another fledgling! In fact, Barbet is very territorial, and he will fight Albatross for control of the tree.
Fledglings fight in a peculiar manner, by taking turns moving around the tree. In a fledgings turn, they must walk along a branch to an adjacent, unoccupied location on the tree. If a fledgling cannot make a move, then they lose the fight and lose ownership of the tree. The fight starts once a challenger fledgling (in this case, Albatross), lands on a tree, with the defender fledging (Barbet) making the first move.
Albatross has yet to pick a location on the tree to land on, but is suddenly worried: she doesn't know where Barbet is located! To complicate matters, both Albatross and Barbet are master logicians, so it may not even been worth fighting over this tree if Albatross will lose most of the time.
Can you figure out how many starting positions of Albatross and Barbet result in Albatross losing the fight?
The first line of input will contain a single integer, $$$2 \leq n \leq 2 \cdot 10^5$$$, denoting the number of locations on the tree.
Then, $$$n-1$$$ lines follow, each containing two integers $$$1 \leq a, b \leq n, a \not= b$$$, representing a branch between locations $$$a$$$ and $$$b$$$.
Output a single integer, representing the number of starting position pairs that end in Albatross losing.
3 1 2 2 3
2
4 1 2 1 3 1 4
6
Image courtesy of https://jspaint.app/ and a trackpad.
Adeleke realizes that the bird flock that she has been watching has a very particular pattern (see a picture of said flock below).
Specifically, she believes that the number of birds in the flock will only be positive integers whose decimal representations contain only the digits $$$3$$$ and $$$8$$$ (so numbers like $$$33$$$, $$$888$$$, and $$$383$$$ are valid but $$$358$$$ is not). Adeleke, being a statistician, wants to compute the following property:
If she chooses a number $$$a$$$ randomly from the interval $$$[a_1, a_2]$$$ and another number $$$b$$$ randomly from the interval $$$[b_1, b_2]$$$. (Each number in $$$[a_1, a_2]$$$ and $$$[b_1, b_2]$$$ - including endpoints of the intervals - is equally likely to be chosen as $$$a$$$ and $$$b$$$ respectively).
She then wants to know what the probability that the interval $$$[\text{min}(a,b), \text{max}(a,b)]$$$ contains exactly $$$k$$$ possible bird flock sizes. Since the probability will be of the form $$$\frac{p}{q}$$$ where both $$$p$$$ and $$$q$$$ are integers, print the integer $$$p \cdot q^{-1}$$$ modulo $$$10^9 + 7$$$.
The input will be a single line containing 5 integers: $$$a_1$$$, $$$a_2$$$, $$$b_1$$$, $$$b_2$$$, and $$$k$$$ separated by a space where $$$1 \leq a_1 \leq a_2 \leq 10^9$$$, $$$1 \leq b_1 \leq b_2 \leq 10^9$$$, and $$$1 \leq k \leq 1000$$$.
Print $$$p \cdot q^{-1}$$$ modulo $$$10^9 + 7$$$ where $$$\frac{p}{q}$$$ represents the probability that the interval contains exactly $$$k$$$ numbers that are possible bird flock sizes.
1 10 1 10 2
260000002
5 6 8 10 1
1
You are a bird in Seattle. As a result, you have been caught out in the rain. You need to travel a certain distance at a certain velocity. What is the amount of rain that hits your body?
If you were a normal bird like a Bali Bird of Paradise or a Long Wattled Umbrellabird, this might be very hard to calculate. Lucky for you, you are one of those exotic birds that are shaped like a rectangular prism, and you fly so that one of your faces is parallel to the ground.
Also, as is well known, Seattle rain is very predictable in many ways. In particular, you can model the rain as a uniform mist of density $$$\rho$$$ such that at any point in time, a chunk of space with volume $$$V$$$ will contain $$$\rho V$$$ rain.
To express the velocities of the rain and yourself, we can set up a rectangular coordinate system, so that your body is axis-aligned. Negative $$$z$$$ denotes the direction of gravity (that is, the direction things fall). The rain falls at a constant velocity, having reached terminal velocity, and has components $$$r_x, r_y, r_z$$$. You yourself are moving at velocity specified by components $$$v_x, v_y, v_z$$$. It is guaranteed that your speed is nonzero. Your body, being a rectangular prism, has lengths $$$x, y, z$$$ in the $$$x, y, z$$$ directions, respectively.
The first line contains the two values, $$$1 \le \rho \le 10^6$$$ and $$$1 \le d \le 10^6$$$, the density of the rain and the distance needing to be traveled, space-separated.
The second line contains three numbers $$$-10^6 \le r_x, r_y, r_z \le 10^6$$$, the velocity components of the rain, space-separated.
The third line contains three numbers $$$-10^6 \le v_x, v_y, v_z \le 10^6$$$, the velocity components of yourself, space-separated. It is guaranteed that at least one of these values is nonzero.
The fourth and last line contains three numbers $$$1 \le x, y, z \le 10^6$$$, the lengths of your body along the $$$x, y, z$$$ axes respectively, space-separated.
Note that any of these values can be general real numbers, not just integers.
A single number, equal to the quantity of rain that hits your rectangular bird body, up to an error of $$$10^{-6}$$$.
1 2 0 0 -1 0 0 1 1 1 1
4
4 3 1 1 1 2 1 2 2 1 1
12
As an avid bird keeper, Georgina has placed a series of $$$n$$$ pellets of bird food of varying qualities $$$1$$$ through $$$n$$$ in a line (there is exactly $$$1$$$ pellet of each quality of bird food) for the neighborhood birds to try and enjoy.
Georgina's pellets have been talked about far and wide among the bird community and as a result, she has $$$q$$$ regular birds that frequent her bird feeders in search of good eats. Georgina wants to ensure each of her regulars have enough food, so she wants to calculate how many pellets that each bird will eat.
Each bird arrives at some location, $$$l_i$$$ in the line of food pellets, travels $$$r$$$ pellets forward, eats all pellets that have quality $$$\geq k_i$$$ on the way, and flies away. If $$$l_i$$$ is far enough forward that the bird cannot travel all $$$r$$$ pellets, the bird will fly away after reaching the last pellet. After the bird leaves, Georgina will replace all the pellets that the bird ate.
Help Georgina calculate how many pellets are eaten by each bird!
One of the regular birds The first line consists of three integers $$$n, q, r$$$ $$$(1 \leq n, q, r \leq 10^5)$$$. The next line consists of $$$n$$$ integers, giving the series of food pellet qualities that Georgina has placed. The next $$$q$$$ lines consist of two integers $$$l_i, k_i$$$ $$$1 \leq l_i, k_i \leq n$$$, which gives the position in the line that the $$$i$$$th bird starts at and the minimum quality food that the $$$i$$$th bird will eat.
For each of the $$$q$$$ bird queries, output the number of pellets that the bird will eat.
5 3 3 4 3 2 5 1 1 2 3 4 2 1
3 1 3
The first bird will eat pellets $$$4, 3, 2$$$. The second bird is quite stingy and will only eat pellet $$$5$$$. The third bird will eat pellets $$$3, 2, 5$$$
The Council of Communist Crows (CCC) has finally garnered enough support amongst the local murders of crows for them to launch a communist revolution! This will, of course, require a redistribution of wealth, and the CCC wants to organize the redistribution such that each of the $$$N$$$ murders of crows ends up happy, with their requests met, and also such that some murders of crows directly exchange wealth, in order to mend their relationship in the new communist society.
Based on their population and contributions to the CCC, each murder $$$i$$$ demands that $$$d_i$$$ shiny things end up in their possession at the end of the redistribution. Further, each murder $$$i$$$ begins with some amount $$$a_i$$$ of previously amassed shiny things, which will be subject to the redistribution. Then, because of their territory layouts in the local area, only some murders have direct access to trade shiny things with some murders, meaning that the movement of shiny things directed by the Council will need to be strategically orchestrated in order for the murders' demands to be met. They want the redistribution to be efficient as well, such that any two murders have at most one direct transfer of wealth between them. Lastly, the CCC has constructed a list of $$$T$$$ direct wealth transfers between specific murders that it will require in the redistribution, in order to force those murders to interact with one another and amend their friendships.
Help the CCC plan the communist revolution! Given the local murders' starting amounts of shiny things, their respective demands, which murders can directly exchange wealth, and which murders the CCC requires to directly transfer wealth, determine whether the murders' various demands can actually be met!
The first line of input contains a single integer $$$N$$$ $$$(2 \leq N \leq 300)$$$, denoting the number of local murders of crows. The next $$$N$$$ lines each contain two space-separated integers $$$a_i$$$ and $$$d_i$$$ $$$(0 \leq a_i, d_i \leq 10^6)$$$, representing the $$$i^{th}$$$ murder's starting amount of shiny things and demanded amount of shiny things respectively.
The next line of input contains a single integer $$$P$$$ $$$(1 \leq P \leq N-1)$$$, denoting the number of pairs of murders that live close enough together to exchange wealth. $$$P$$$ lines follow, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq N)$$$, indicating that the $$$i^{th}$$$ and $$$j^{th}$$$ murders can directly exchange wealth.
Lastly, the next line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq P)$$$, denoting the number of direct transfers required by the CCC. $$$T$$$ lines follow, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq N)$$$, indicating that the $$$i^{th}$$$ murder must transfer at least one shiny thing to the $$$j^{th}$$$ murder (not the other way around) during the redistribution (the $$$i^{th}$$$ and $$$j^{th}$$$ murders are guaranteed to be close enough to exchange wealth).
If the CCC can successfully orchestrate a communist redistribution under the specified demands and constraints, output COMMUNIST REVOLUTION. Otherwise, print NOT GONNA FLY.
4 5 2 3 2 1 4 0 1 3 1 3 2 4 1 4 1 1 4
NOT GONNA FLY
4 5 2 3 2 1 4 0 1 3 1 3 2 4 1 4 1 1 3
COMMUNIST REVOLUTION
In the first test case, because at least one shiny thing must be transferred from murder $$$1$$$ to murder $$$4$$$, it is not possible for both the demands of the murder $$$1$$$ and murder $$$3$$$ to be met.
In the second test case, however, a successful redistribution is possible. For example, if murder $$$1$$$ transfers three shiny things to murder $$$3$$$ (satisfying the transfer requirement from $$$1$$$ to $$$3$$$), and murder $$$2$$$ transfers one shiny thing to murder $$$4$$$, then all of the demands will be met.