It is the day of the Iditarod Trail Sled Dog Race, and you are excited to participate!
As you line up for the race, you notice that a word posted on the letter board outside looks slightly off. For example, the board may say, "COME FOR THE SHIRTS!" instead of "COME FOR THE SPORTS!". Dismayed, you decide to fix the board minutes before the race begins by swapping out the word $$$s$$$ (in this case, "SHIRTS") with the intended word $$$t$$$ (in this case, "SPORTS"). Fortunately, there is a box placed next to the foot of the sign filled with spare, unused letters. However, you see no X's or B's in the box or on the board, so will have to tack together two I's and P's respectively when it comes to making these characters. You are in a hurry, and want to calculate the minimum number of letters you need to put on the board to make it correct again.
The first line contains an uppercase strings $$$s \: (0 \leq |s|\leq 10^5)$$$, the initial word on the board.
The second line contains an uppercase string $$$t \: (0 \leq |t|\leq 10^5)$$$, the end word you wish to transform $$$s$$$ into.
Please output a single integer $$$k$$$, the minimum number of letters you should put on the board to fix the message.
SHIRTS SPORTS
2
PATHS PATHS
0
You can assume that the box of unused letters will not run out of any character during the duration of your swapping.
As an avid watcher of the Iditarod Trail Sled Dog Race, you've decided that you want to enter your dog in the next contest. Every dog that races gets a number assigned to them. Given that your dog has received the number $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, what is the maximum difference between any two permutations of $$$n$$$?
The first and only line of input will contain $$$n$$$ $$$(1 \leq n \leq 10^5)$$$.
Return the maximum difference between any two permutations of $$$n$$$.
4284
5994
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