There are $$$n$$$ dogs all facing clockwise in a circle with $$$n$$$ evenly spaced points. They are all feeling energetic and want to chase the dog in front of them by running over $$$v_i$$$ points. Sometimes, this causes them to miss their target. Being a dog photographer, you want to find the earliest time $$$t$$$ and position $$$p$$$ that the dogs will all be at one point, such that you can take a picture of all of the dogs together. Of course, you have limited time to take the photos, so at $$$t = 1001$$$, you will decide to take pictures of other groups of dogs and leave.
The first integer will contain $$$n (1\leq n\leq 1000)$$$. The next lines will each contain $$$n$$$ integers $$$v_i (1\leq v_i \leq 100, 0\leq i\leq n - 1)$$$, where the $$$i$$$-th dog starts at position $$$i$$$ at $$$t = 0$$$.
Two space-separated integers, the earliest time $$$t$$$ and position $$$p$$$. If all the dogs cannot be at one point, print $$$-1$$$
3 1 2 3
2 2
You have been struggling to organize your wardrobe for years now. But what's the point? After all, sticking all your clothes in a big pile hasn't failed you yet.
The pile works as follows. Initially, it starts out empty. Each time you clean some clothing, you'll throw it on top of the pile. Whenever you need a new outfit, you'll grab whichever article of clothing is on top of the pile to wear.
However, once in a while it comes time to run the Iditarod, and you can't just pick any outfit. To make sure you win the race, you need your trusty snowcoat! When this happens, you carefully remove your trusty snowcoat from the pile, leaving the ordering of all other clothing the same.
One day (today), you start thinking about the simplicity of your outfit selection scheme. It almost feels like it could be written as an algorithm...
The first line of input contains a single integer $$$T (1 \leq T \leq 1000)$$$, representing the number of events that will occur. Then, $$$T$$$ lines follow, each representing a single action you perform. Each line will be in one of the following forms:
- $$$\text{put }s$$$: put the clothing item $$$s$$$ onto the pile ($$$1 \leq |s| \leq 10$$$). $$$s$$$ will only consist of alphanumeric characters. $$$s$$$ will be distinct from the names of any other clothing items in the pile.
- $$$\text{get}$$$: take an article of clothing off the pile to wear, and output its name. If the pile is empty, output "$$$\text{empty}$$$".
- $$$\text{iditarod}$$$: search through your pile for an article of clothing named "snowcoat". If you can find the snowcoat, output "$$$\text{winner winner chicken dinner :)}$$$" and remove it from the pile. Otherwise, output "$$$\text{oopsimcold :(}$$$".
For each of the $$$\text{get}$$$ or $$$\text{iditarod}$$$ events, output the appropriate response. It is guaranteed that at least one of these events will exist.
6 put shirt put snowcoat iditarod iditarod put shirt2 get
winner winner chicken dinner :) oopsimcold :( shirt2
In preparation for this year's Iditarod, you plan to practice racing on a new hill.
The hill can be considered an array of size $$$N$$$ where each index corresponds to a position on the hill. The value of each element represents the height of snow at that position on the hill. Index $$$0$$$ represents the start of the hill and index $$$N-1$$$ represents the end of the hill. Since the hill slopes upwards, the height of snow is monotonically increasing from the start to the end of the hill.
To ensure it is safe to traverse, you want to analyze the hill before you begin. You want to answer $$$Q$$$ queries where each query contains an integer $$$K$$$. For each query, find the smallest interval $$$[a,b]$$$ on the hill where the sum of the snow heights is exactly $$$K$$$ units.
If multiple of these intervals exist, output the interval closest to the start of the hill. It is guaranteed that such an interval exists somewhere on the hill.
The first line of input contains two numbers $$$N$$$ and $$$Q$$$. $$$(1 \leq N \leq 100,000)$$$ $$$(1 \leq Q \leq 100)$$$
The next line of input contains $$$N$$$ numbers representing the hill array. $$$(1 \leq a_i \leq N)$$$
The next Q lines each contain an integer $$$K$$$. $$$(1 \leq K \leq N^2)$$$
For each query, please output integers $$$a \space b$$$ (0-indexed) representing the start and end index of the desired interval $$$[a, b]$$$ respectively.
6 3 2 2 3 4 5 6 4 7 16
3 3 2 3 0 4
10 5 1 1 1 2 2 4 6 7 9 9 1 16 2 10 7
0 0 7 8 3 3 5 6 7 7
Passionate fans of the Iditarod Trail Sled Dog Race have created their own version here in Austin, the Austin Longhorn Race.
This year's Austin Longhorn Race features competitors hailing from all over Texas. Interestingly, news of treasure at checkpoints along the route have spread. One team, UT Lemons, has obtained top-secret information about where and when the treasure will appear.
There are $$$N$$$ checkpoints at which the treasure will appear. Each treasure will appear at coordinates ($$$X_i$$$, $$$Y_i$$$) and at time $$$T_i$$$ for $$$(1 \leq i \leq N)$$$. Each treasure is worth $$$V_i$$$ gold coins.
Every team starts from $$$(0, 0)$$$ at time = $$$0$$$, and moves at a rate of one unit distance per unit time. UT Lemons will be able to obtain the treasure at checkpoint $$$i$$$ if they are at $$$X_i$$$, $$$Y_i$$$ at time $$$T_i$$$. The total treasure value is the sum of individual treasure values. Please help UT Lemons determine the maximum amount of treasure they can obtain (measured in gold coins).
The first line contains one integer, $$$N$$$ ($$$1 \leq N \leq 5000$$$).
The next $$$N$$$ lines contain four integers, $$$X_i$$$, $$$Y_i$$$, $$$T_i$$$, $$$V_i$$$ ($$$1 \leq i \leq N$$$, $$$0 \leq X_i, Y_i, T_i, V_i \leq 10^9$$$).
A single integer representing the total number of gold coins that UT Lemons can obtain by taking the best route.
3 1 1 100 10 2 2 40 8 20 20 25 1000
18
2 15 20 25 100 7 24 25 50
100
It's time for the Iditarod Sled Dog Race! The Iditarod is an intense race that stretches from Willow, Alaska all the way to Nome, Alaska. The race can take a couple weeks to complete, so it's important to find places to take a break.
Dallas Seavey is one of the competitors in the race, and he has a favorite number $$$M$$$. In the race, there is a checkpoint every mile, but Dallas will only stop at the $$$i$$$th checkpoint if $$$i$$$ is relatively prime with $$$M$$$. (Stopping at any other checkpoint would be bad luck.)
Two numbers are relatively prime if they share no common factors other than 1. You are given this special number $$$M$$$, and a list of $$$N$$$ integers. Dallas wants to know: for each integer $$$a_i$$$ in the list, what is the $$$a_i$$$th-smallest positive integer that is relatively prime with $$$M$$$?
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^6, 2 \le M \le 10^5$$$). The second line contains $$$N$$$ integers $$$a_1, a_2, …, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
Print out one line containing $$$N$$$ positive integers, where the $$$i$$$th integer is the $$$a_i$$$th-smallest positive integer that is relatively prime with $$$M$$$. Note that 1 is relatively prime with every number.
3 6 3 7 12
7 19 35
The Iditarod Trail Sled Dog Race (ITSDR) is coming up, and a rather unexpected competitor rolls up to the starting line... Farmer John! Of course, unlike the average ITSDR contestant, Farmer John employs the help of his cows instead of dogs. Farmer John realizes that, since cows are a bit lazy and hard to motivate compared to dogs, he may need quite a lot of them to ensure his victory in the race.
So, he decides to appoint his favorite cow, Bessie, to form a team for him. Farmer John's farm contains an infinite number of cows of two types: spotted and brown. Any two cows of the same type are indistinguishable. Bessie is tasked with selecting a total of $$$N$$$ cows to form an ordered team. Farmer John considers a team "good" if there are no consecutive sequences of spotted cows of length $$$K$$$ or greater. For example, if Bessie suggests a team that looks like "BSSSB" and $$$K = 2$$$, then Farmer John would not consider this team good because there are $$$3$$$ spotted cows in a row.
The day before the race, Farmer John provides Bessie with the values of $$$N$$$ and $$$K$$$. Since she is so short on time, Bessie asks you to come up with an efficient algorithm to calculate the number of "good" teams that she could form under the given constraints. Note that two teams are considered distinct if the cows at least one position differ in type. Since the number of "good" teams may be unfathomably large, Farmer John would simply like to know the answer modulo $$$10^9 + 7$$$.
The input will consist of a single line containing two integers, $$$N$$$ and $$$K$$$ ($$$1 \leq K \leq N \leq 10^6$$$).
Output a single integer representing the number of "good" teams modulo $$$10^9 + 7$$$.
5 3
24
6 2
21
Balto is a Siberian Husky who is getting ready to compete in the Great Alaskan Sled Dog Race. The Great Alaskan Sled Dog Race is a grueling competition that takes place over several days. During the race, teams of sled dogs traverse a treacherous path through snow-covered terrain. As a result, he will need to train hard.
In preparation for the race, Balto is practicing in an area that consists of $$$N$$$ villages numbered from $$$1$$$ to $$$N$$$. Each village has a "left" and "right" trail leading to another checkpoint.
Balto has a peculiar way of practicing: he starts at a village and runs $$$K$$$ times to the left, then $$$K$$$ times right, $$$K$$$ times left again, and finally $$$K$$$ times to the right again.
Your task is to help Balto answer $$$Q$$$ queries about where he will end up after completing the course. Each query contains two integers, the starting village and the number of times $$$K$$$ that he will go left or right.
Given the village's left and right path destinations as well as a series of queries, help Balto determine where he will end up, for each query.
The first line of input contains an integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ - the number of villages on the path.
Each of the next $$$N$$$ lines contains two integers, the indices of the villages on the "left" and "right" trails respectively.
The next line contains an integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ - the number of queries.
Each of the next $$$Q$$$ lines contains two integers, the starting village and the number of times $$$K$$$ ($$$1 \leq K \leq 10^9$$$) Balto must run the course.
For each query, print a single integer denoting the village where Balto will end up after completing the course.
3 2 3 3 1 1 3 3 1 1 1 2 3 1
1 3 3
April, the reigning monarch of Mayland, is planning this years March March. March March is an annual tradition for the monarchy travel between the various cities of Mayland, following the same track as this year's Iditarod.
Mayland consists of $$$n$$$ cities, labelled $$$1 \ldots n$$$. Historically, these labels represented a ranking of the cities. To show off the kingdom in its best light, the March March starts off by visiting cities in order: starting at city $$$1$$$, then city $$$2$$$, then eventually ending at city $$$n$$$, in the hopes that by then, most people have already lost interest and gone home.
However, times are changing. As the March March gets more and more extravagant, only $$$m$$$ one-way roads between the cities are suitable for use in the March March. Moreover, some of these labels haven't been changed in centuries, and may no longer be accurate for today's cities! April is concerned: it might not even be possible to hold a proper March March this year, which would also ruin the sled race!
Thankfully, April has an idea. She can use some of the Mayland's treasury to construct a new one way road from any city to any other, for a price of $$$c$$$. However, she may be able to spare some money by changing the labels of cities! Of course, a city $$$i$$$ will happily take a new label $$$j$$$ if $$$j \lt i$$$. But to appease the citizens, April will need to pay $$$d$$$ to convince a city to take on a worse label. April wonders: what is the cheapest way she can make this years March March a success?
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 20, 1 \leq m \leq \frac{n(n-1)}{2}$$$), representing the number of cities and one-way roads, respectively.
The second line contains two integers, $$$c$$$ and $$$d$$$ ($$$1 \leq c,d \leq 10^6$$$), representing the cost to build a one-way road and the cost to convince a city to assume a worse ranking, respectively. All roads will be distinct.
Finally, the last $$$m$$$ lines contain two integers $$$a$$$ and $$$b$$$ each ($$$1 \leq a,b \leq n, a \not= b$$$), representing a one-way road that already exists from city $$$a$$$ to city $$$b$$$.
Output a single integer, the minimum cost needed to make a suitable March March.
6 5 3 5 1 2 2 3 3 5 5 4 4 6
5
6 5 3 10 1 2 2 3 3 5 5 4 4 6
9
In the first case, it is optimal for April to relabel city $$$4$$$ to city $$$5$$$, and city $$$5$$$ to city $$$4$$$. She does not need to build any roads, so she only pays $$$5$$$ total to convince city $$$4$$$ to take a worse label.
In the second case, the cost of relabelling cities has gone up. It is now optimal for April to just build roads from $$$3$$$ to $$$4$$$, $$$4$$$ to $$$5$$$, and $$$5$$$ to $$$6$$$.