Ellie is an elephant searching for a prize. He is given $$$n$$$ baskets of peanuts and is told to find the basket that has a unique number of peanuts. Every other basket has exactly 1 other basket that has the same number of peanuts that it has. In formal terms, if a basket has $$$p$$$ peanuts, then exactly 1 other basket will have exactly $$$p$$$ peanuts also. Determine how many peanuts are in the basket that has a unique number of peanuts.
The first and only line of input will contain $$$n$$$ integers ($$$1 \leq n \leq 10000$$$)., representing the number of peanuts in each of the $$$n$$$ baskets. Each basket can have $$$x$$$ peanuts, where ($$$1 \leq x \leq 10000$$$).
Determine the number of peanuts in the basket that has a unique number of peanuts.
6 7 8 7 6
8
1 1 2 2 3
3
You are in quite the pickle! While playing Super Auto Pets 2 (the new version where you face two opponents at once), you are left in a situation where your only pet left is an owl.
In Super Auto Pets 2, your two opponents (one behind you, one in front) can send enemies towards you at specific times. Luckily, due to its ability to swivel its neck 180 degrees, your owl pet can attack enemies in both directions!
You will be given information regarding the times that enemies will show up behind and in front of your owl pet, but the catch is that the owl can only attack in a single direction at a particular time. Attacking is instant, but the owl can't attack enemies that have not shown up yet.
Knowing this, can you figure out whether your owl pet will survive, or whether it will be overwhelmed by enemies on both sides!
The input will begin with a line containing two space-separated integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$), denoting the number of enemies that will appear in front of the owl and behind the owl, respectively.
The next line will contain $$$n$$$ space-separated integers, the $$$i$$$-th of which, $$$f_i$$$ ($$$1 \leq f_i \leq 10^9$$$), represents the time that the $$$i$$$-th enemy will appear in front of the owl. It is guaranteed that these times will be unique.
The final line will contain $$$m$$$ space-separated integers, the $$$i$$$-th of which, $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$), represents the time that the $$$i$$$-th enemy will appear behind the owl. It is guaranteed that these times will be unique.
The output should consist of a single line containing the phrase "You Lose" (no quotation marks) if your owl pet will become overwhelmed by two enemies at once or "You Win" (no quotation marks) otherwise.
3 5 1 2 3 4 5 6 7 8
You Win
2 2 999 1000 1 1000
You Lose
After spending years as a nematologist, you've finally acquired yourself a pet worm. Unfortunately, since it's your first pet worm, you're unsure of your ability to maintain its welfare.
Your worm begins with $$$F$$$ fullness. Every day, you feed it, increasing its fullness by $$$A$$$. Every night, it consumes energy, losing $$$B$$$ fullness.
Your worm will finally be happy as soon as it reaches or exceeds $$$1000$$$ fullness.
Given the worm's initial fullness and your feeding regimen, determine how many days it will take before the worm gets full (or that it will never become full).
A single line with values $$$0 \leq F \leq 999$$$, $$$1 \leq A, B \leq 100$$$.
The day on which the worm becomes full, or $$$-1$$$ if this never occurs.
900 50 25
3
500 10 10
-1
Gregorio is building a rat army! By themselves, rats are small and fairly weak. However, they have a secret ability: in the midst of battle, they can call upon reinforcements, causing a rat swarm!
Gregorio finds it difficult to keep track of each rat during battle, especially since they keep calling for reinforcements. As a result, he only knows the total number of rats after the battle is won (Gregorio always wins).
In particular, the rats summon reinforcements in an orderly way, so Gregorio knows the total number of rats is always a perfect power. A perfect power is a number $$$y$$$ such that there exist integers $$$x, k$$$ where $$$y = x^k$$$, $$$k \gt 1$$$.
However, for any given $$$y$$$, there may be multiple values $$$x, k$$$ that satisfy the criteria. Gregorio has several different rat species, and he uses exactly one species for each battle. Each species corresponds to a single value $$$x$$$ which is the same for a given species across all battles.
Raising different species is expensive, so Gregorio tries to have as few rat species as possible. Gregorio has a list of battles that he has won, along with the final number of rats for each (a perfect power). Now he wants to know: between all the battles, what's the minimum number of rat species he could own and still be consistent with the battle data?
The first line contains one integer $$$N$$$ representing the number of battles. ($$$1 \le N \le 10^5$$$)
The next line contains $$$N$$$ integers $$$a_1, a_2, ... , a_n$$$ representing the final number of rats after each battle. It is guaranteed that each $$$a_i$$$ is a perfect power. ($$$1 \le a_i \le 10^9$$$)
Print out a single integer, the minimum number of rat species Gregorio could own which is consistent with the battle data. In other words, the minimum number of distinct values $$$x_1, x_2, ...$$$ such that for each $$$a_i$$$, there is some $$$x_j$$$ and some other integer $$$k$$$ such that $$$a_i = x_j^k$$$.
5 512 64 243 25 32768
3
In the example:
Remi the rabbit is really a refined robber, randomly ransacking real ranches regarding their rotund roots.
Remi is planning her largest heist yet! There are $$$n$$$ farms in a line from which she plans to steal carrots from. In the dead of night, she plans to visit some of the farms, eating the carrots along the way to nourish her for the rest of the heist.
Each of the farms has an associated carrot quality, $$$a_i$$$. Regardless of which farm they are from, all carrots have a nourishment value of $$$k$$$, meaning that if Remi eats carrots from farm $$$i$$$, she has enough energy to visit farms $$$i+1 \ldots i+k$$$. Remi starts out with enough energy to visit farms $$$1 \ldots k$$$.
Remi is looking to only eat the highest quality carrots, and would like to maximize the quality of the worst carrot she must eat to pass farm $$$n$$$. Can you help her?
The first line contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$).
The next line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ represents the quality of the carrots on farm $$$i$$$.
Output a single integer, the maximum value of the lowest quality carrot Remi must eat to get past all $$$n$$$ farms.
5 3 3 2 5 1 4
5
5 3 4 5 2 1 3
3
Penguin has a very special skill: she is a fitness trainer! She is always helping her friends out by training them to be stronger.
Her $$$N$$$ friends (numbered $$$1$$$ through $$$N$$$) are getting ready for the prestigious International Tug-o-war Competition (ITOWC). The competition lasts $$$D$$$ days and her friends will be competing as $$$T$$$ (potentially overlapping) teams defined as a contiguous array of numbers.
Being professionals, Penguin's friends already have a lot of training. Specifically, friend $$$i$$$ currently has strength $$$s_i$$$. Each team's strength is the sum of each team member's strength.
Penguin wants the best for her friends and has devised a training plan for them! Before each day of the competition, Penguin will train some of her friends, making them more equipped to compete the next day! Each friend that is trained will permanently increase their strength by $$$1$$$.
Given a list of teams, their initial training statuses, and Penguin's training plan, help Penguin compute the strength of each of the teams on each day.
The first line contains three integers, $$$1 \leq N \leq 10^4$$$, $$$1 \leq T \leq 1000$$$, and $$$1 \leq D \leq 100$$$. The second line will contain $$$N$$$ integers $$$0 \leq s_i \leq 1000$$$, the strengths of each friend. The next $$$T$$$ lines will contain two integers, $$$1 \le a_i, b_i \le N$$$, where all friends from $$$a_i$$$ to $$$b_i$$$ inclusive will be on team $$$i$$$. The last $$$D$$$ lines contain an integer $$$1 \leq Q \leq 1000$$$, then $$$Q$$$ more numbers for the friends Penguin will be training.
Print out $$$D$$$ lines, each containing the performance of the teams for that day (following the example format below).
4 3 2 1 2 4 1 1 3 2 4 2 2 2 1 4 3 1 2 3
Day 1: 8 8 2 Day 2: 11 10 3
Terry the T-Rex loves typing! The only problem is that his extremely short arms severely limit his typing speed.
Terry has a message that he would like to send to his friend Perry the Pterodactyl. His message consists of a series of lowercase English letters and spaces (no punctuation, etc.).
Terry employs the classic hunt-and-peck method of typing: his index claws initially rest upon any key(s) that Terry chooses, and then for each letter in the message, Terry may move either of his index claws to the desired key and press it.
Terry's keyboard layout is shown above (though we only care about the lowercase English letters). Any spaces in the message may be ignored, as Terry will simply use his head to bash the space bar instead of bothering to use his claws. Otherwise, for each letter that Terry types, there is a cost associated with moving his claw from an old position to a new one.
The cost of moving a claw is equal to the Manhattan distance between the two keys (assuming that the keys are organized in a grid as shown above). Note that there is no additional cost associated with actually pressing a key.
Terry would like to know: based on his initial choice of claw positions and which claw he chooses to use to type each letter of the message, what is the minimum cost to send his message to Perry?
The input will consist of a single line $$$S$$$, containing Terry's message to Perry ($$$1 \leq |S| \leq 10^5$$$). The message will consist of lowercase English letters and spaces, and there will be no extraneous spaces (i.e. the message will not begin or end in a space and there will never be more than one space in a row).
Output should consist of a single integer, the minimum cost for Terry to send his message to Perry.
hello world
10
qpw
1
The Dragon is a Tier 6 Animal, available in the base game and Pack 1. Every time a Tier 1 Animal is bought, the Dragon buffs all friends (excluding the Dragon), giving them +1/+1, +2/+2, or +3/+3 depending on the level of the Dragon.
The sequel to Super Auto Pets, SAP+, allows you to send teams into battle with unlimited size! Each pet that is part of a team contributes a set number of "stat points" to the "power level" of a team, which is the sum of the stat points of individual pets after buffs are applied. Stat points and buffs are highly dependent on the order in which a player adds pets to a team, and more skilled players are better at maximizing the power levels of their teams through optimal play.
A classic dragon contributes 14 of its stat points to a team's power level in addition to buffing every other pet on the team by ADDING 2 stat points when added. A super dragon contributes 14 of its stat points to a team's power level in addition to buffing every other pet on the team by MULTIPLYING their stat points by 2 when added. For example, if we were to add a classic dragon and then a super dragon, the power level of the team would be 42. However, if we were to add a super dragon and then a classic dragon, the power level of the team would be 30 instead.
Danny, a newbie to SAP+, has $$$A$$$ classic dragons and $$$B$$$ super dragons available to form a team, but decides to add the $$$A+B$$$ pets to his team one at a time in uniformly random order (any ordering is equally likely) as he does not have an understanding of optimal gameplay. Can you help Danny compute the expected value of the power level of his team?
The first and online line of input contains two space-separated integers $$$A$$$ and $$$B$$$ ($$$1 \leq A, B \leq 30$$$), representing the number of classic dragons and the number of super dragons, respectively, Danny has available to add to his SAP+ team in some random order.
Output a single number representing the expected power level of Danny's team. Answers within $$$10^{-4}$$$ of the judge solution will be accepted.
1 1
36.0000000000
1 2
77.3333333333
2 1
60.6666666667
Pesky the Fish has been one the player's favorite pets. However, after a losing streak, the player threatens to turn Pesky into the Sushi item on Turn 9 if they lose another game! To prevent this, Pesky starts training on an obstacle course.
The obstacle course can be described as an $$$n \times n$$$ grid, where each row and each column is numbered from $$$1$$$ to $$$n$$$. Each row is also assigned some value $$$x_i$$$, and each column is assigned some value $$$y_i$$$. To move around in the obstacle course, Pesky can either move horizontally or vertically. If Pesky moves horizontally, the difficulty of the path can be represented by the product of:
Similarly, if Pesky moves vertically, the difficulty of the path is the product of:
In other words, the difficulties can be represented by the formulas below:
Pesky must do $$$q$$$ swims, in which Pesky starts at the start $$$(r_1, c_1)$$$ and chooses a series of moves until it reaches the end $$$(r_2, c_2)$$$. Though the stakes are high, Pesky is lazy, so it wants to find a path where the maximum difficulty across all moves is minimized. For each of these swims, can you determine the minimum possible value of the maximum difficulty?
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^3$$$): the height and length of the square grid.
The next line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^5$$$): the values of each row.
The next line contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$1 \leq y_i \leq 10^5$$$): the values of each column.
The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$): the number of queries.
The following $$$q$$$ lines contain four integers $$$r_1, c_1, r_2, c_2$$$ ($$$1 \leq r_1, c_1, r_2, c_2 \leq n, (r_1, c_1) \neq (r_2, c_2)$$$). $$$(r_1, c_1)$$$ is the start position, and $$$(r_2, c_2)$$$ is the end position.
For each of the $$$q$$$ queries, print a single integer: the minimum possible value of the maximum difficulty on any sequence of moves from the start to the end.
2 1 1 1 100 3 1 1 1 2 1 1 2 1 1 1 2 2
101 2 101
5 1 10 100 1 100 1 100 10 1 100 5 1 1 5 5 5 4 5 3 1 2 1 3 4 1 4 4 1 4 5 4
10100 1010 101 6 101
The Dog is a Tier 3 Pet, available in the Standard Pack and Expansion 1. Whenever a friend is summoned, the Dog will either gain Attack or Health. The stat raised will be chosen at random. If the friend is summoned in battle, the stat boost will only last for that battle; but if the friend is summoned outside of battle, the stat boost will be permanent. - Super Auto Pets Wiki
The $$$N$$$ creatures in the world of Super Auto Pets are friends with some number (possibly 0) of other pets in the world. Each pet is labeled with a unique integer ID between $$$0$$$ and $$$N-1$$$ (inclusive). After being knocked out by a pet with far higher stat boosts, the dog (whose unique ID is 0) has forgot how many friends they have. However, the dog has been able to ask how many friendships (which are bidirectional among animals) each of the other $$$N-1$$$ creatures has within the world. The dog would like to know the number of possibilities for the number of friends they have given what they know about the number of friends all other creatures have.
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$) that represents the number of pets in the world of Super Auto Pets. The second line of input contains $$$N-1$$$ space-separated integers $$$f_i$$$ ($$$1 \leq i \lt N$$$, $$$0 \leq f_i \lt N$$$) that represent the number of other pets creature $$$i$$$ is friends with in the world.
Print a single integer representing the number of possibilities for the number of friends the dog has.
3 2 2
1
3 1 1
2
3 0 2
0