UTPC Contest 09-02-22 Div. 2 (Beginner)
A. Love Your Llama
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Larry the Llama loves eating grass. Since raising Larry, you have noticed that Larry's Vitamin L levels seem to have some correlation with the amount of grass that he eats. Over the years, you've come to realize that in a period of 7 days, Larry's Vitamin L level after those 7 days will be the difference between the maximum number of pounds of grass eaten in that week subtracted by the minimum number of pounds of grass eaten in that week. Determine what you would expect Larry's Vitamin L level to be at after 7 days of eating grass.

Input

The first and only line of input will contain 7 integers, representing the amount of grass eaten in each day of the week. In one day, Larry can eat $$$x$$$ pounds of grass, where ($$$1 \leq x \leq 100$$$).

Output

Print a single number - the Vitamin L level that Larry should have after 7 days of eating grass.

Examples
Input
1 2 3 4 5 6 7
Output
6
Input
1 1 1 1 1 1 1
Output
0

B. Cows Drink Milk
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

What do cows drink? Milk!

At least, that's what Bessie thinks. Bessie the cow loves milk, and has decided today is the day to pay homage to her favorite drink in the form of her newest art installation: The Wall of Milk. The Wall of Milk is just a row of $$$n$$$ glasses, each containing the exact same amount of milk. Bessie has already collected $$$n$$$ glasses of milk, but she still needs to even them out to make The Wall of Milk.

Of course, Bessie could just drink some of the milk from each glass until they were all equal, but she quickly realizes that she could pour the milk from one glass to another! Hooves aren't the best for holding glasses though, so to minimize the chance of ruining her art piece Bessie only pours some milk from one glass to another at most once. Given this, she wonders: how high can The Wall of Milk be?

Input

The first line contains a single integer, $$$1 \leq n \leq 10^5$$$, representing the number of glasses Bessie has.

The next line then contains $$$n$$$ integers $$$1 \leq a_1, \ldots, a_n \leq 10^9$$$, where $$$a_i$$$ represents the units of milk in glass $$$i$$$.

Output

Output a single number, the maximum amount of milk in every glass that Bessie could achieve.

Examples
Input
5
1 2 3 4 5
Output
2
Input
3
1 5 5
Output
3.0
Note

In the first test case, Bessie can pour one unit of milk from the third glass into the first glass, so the glasses now contain [2, 2, 2, 4, 5] units of milk respectively. Then Bessie can create a Wall of Milk with height 2 by drinking from the fourth and fifth glasses. It can be shown that this is the maximum height Bessie can achieve.

C. Ellie the Elephant
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$).

Output

Determine the number of peanuts in the basket that has a unique number of peanuts.

Examples
Input
6 7 8 7 6
Output
8
Input
1 1 2 2 3
Output
3

D. Owl Defense
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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!

Input

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.

Output

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.

Examples
Input
3 5
1 2 3
4 5 6 7 8
Output
You Win
Input
2 2
999 1000
1 1000
Output
You Lose

E. Feed Worm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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).

Input

A single line with values $$$0 \leq F \leq 999$$$, $$$1 \leq A, B \leq 100$$$.

Output

The day on which the worm becomes full, or $$$-1$$$ if this never occurs.

Examples
Input
900 50 25
Output
3
Input
500 10 10
Output
-1

F. Rats Rats
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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$$$)

Output

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$$$.

Example
Input
5
512 64 243 25 32768
Output
3
Note

In the example:

  • $$$512 = 8^3$$$
  • $$$64 = 8^2$$$
  • $$$243 = 3^5$$$
  • $$$25 = 5^2$$$
  • $$$32768 = 8^5$$$
This corresponds to 3 distinct values for $$$x$$$: 3, 5, and 8. It can be shown that this is the minimum possible number of distinct $$$x$$$ values.

G. Carrot Thief
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

Output a single integer, the maximum value of the lowest quality carrot Remi must eat to get past all $$$n$$$ farms.

Examples
Input
5 3
3 2 5 1 4
Output
5
Input
5 3
4 5 2 1 3
Output
3

H. Penguin Problems
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

Print out $$$D$$$ lines, each containing the performance of the teams for that day (following the example format below).

Example
Input
4 3 2
1 2 4 1
1 3
2 4
2 2
2 1 4
3 1 2 3
Output
Day 1: 8 8 2 
Day 2: 11 10 3 

I. Tyrannosaurus Typing
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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?

Input

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

Output should consist of a single integer, the minimum cost for Terry to send his message to Perry.

Examples
Input
hello world
Output
10
Input
qpw
Output
1

J. Dragon Buffs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

Output a single number representing the expected power level of Danny's team. Answers within $$$10^{-4}$$$ of the judge solution will be accepted.

Examples
Input
1 1
Output
36.0000000000
Input
1 2
Output
77.3333333333
Input
2 1
Output
60.6666666667