You've been birdwatching all day, and it's finally sunset!
Any second now, the $$$n$$$ pigeons will be flying home back to their nests. As you wait an anticipation, you realize something: there are only $$$m$$$ nests in the tree! Some of the pigeons will need to share a nest in order to have somewhere to sleep at night.
It would be quite uncomfortable to share a nest with other pigeons, so a natural question arises: if the pigeons rest optimally, how many pigeons must there be in the fullest nest?
There is only one line of input, which contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^{18}$$$). $$$n$$$ represents the number of pigeons returning home, and $$$m$$$ represents the number of nests.
Output a single integer, the number of pigeons in the fullest nest if the pigeons distribute among the nests optimally.
15 5
3
4 3
2
In the first test case, the pigeons can evenly distribute themselves, yielding 3 pigeons in each of the 5 nests.
In the second test case, no matter how they arrange themselves, there will always be a nest containing at least 2 pigeons.
UT Austin has decided to adopt a flamingo on campus named Freddy.
They have allowed students to feed Freddy for the next $$$n$$$ days. However, Freddy has days when he needs to fast and cannot consume food. Assuming that the day he arrived on campus is day 1, there are a couple of rules that Freddy has for the days that he fasts. He will fast on days that are divisible by a certain number $$$k$$$. He has one exception to this rule - he will not fast on a day if the day number is divisible by $$$k^2$$$. Calculate the number of days that Freddy will fast for the next $$$n$$$ days.
There will be one line of input containing two integers. The first integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ represents the number of days that Freddy will be on campus. The second integer represents $$$k$$$ $$$(1 \leq k \leq 100)$$$.
Output the number of days that Freddy will be fasting in the next $$$n$$$ days.
25 5
4
200 10
18
For the first test case, there are 5 multiples of 5 between 1 and 25. However, since day 25 is divisible by 5, there are 4 days that Freddy will fast.
For the second test case, there are 20 multiples. However, Freddy will not fast on day 100 and 200, leaving 18 fasting days.
Percy the peacock is quite the fancy peacock, and loves to go to peacock parties! For each party, he adorns a set of colorful feathers to look his best.
However, he recently realized that despite owning many different colors, Percy only wears a handful of colors. The problem is, Percy leaves all his colorful feathers in a pile – taking the top one off when he attends a party, and putting it back on top when he's done. In fact, the only time the color he wears ever changes is when he buys a new set of feathers!
Instead of taking from the top of the pile, Percy has now decided to take his next set of feathers from the bottom of the pile, in the hopes that he can go show off all his colors at the peacock parties. Can you help him figure out what colors he will wear to each party?
The first line of input is a single integer, $$$1 \leq n \leq 2 \cdot 10^5$$$, denoting the number of days.
Then, follow $$$n$$$ lines, where the $$$i$$$th line contains what Percy does on the $$$i$$$th day. This will be one of:
- $$$1$$$ $$$c$$$: Percy buys a set of feathers with color $$$c$$$, which is a string of at most 10 characters. These feathers go on the top of the pile.
- $$$2$$$: Percy attends a party with the bottommost set of feathers, and puts them back on top of the pile after he comes back from the party. It is guaranteed that the pile is not empty when this happens.
For each day when Percy attends a party, output the color of the feathers he wears to the party.
10 1 red 1 blue 1 green 2 2 1 yellow 2 2 2 2
red blue green red blue yellow
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