hackercupai/hackercup huggingface dataset:
Problem: new_years_resolution (2015 quals)

Alex's New Year's resolution for 2015 is to eat healthier foods. He's done
some research and has found out that calories come from three main sources,
called macronutrients: protein, carbohydrates, and fat. Alex wants to get the
right balance of protein, carbohydrates, and fat to have a balanced diet. For
each available food, Alex can only choose to eat it or not eat it. He can't
eat a certain food more than once, and he can't eat a fractional amount of a
food.

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, the first line consists of three space-separated integers: **GP**,
**GC**, and **GF**, which represent the amount of protein, carbohydrates, and
fat that Alex wants to eat. The next line has the number of foods for that
test case, an integer **N**. The next **N** lines each consist of three space-
separated integers: **P**, **C**, and **F**, which represent the amount of
protein, carbohydrates, and fat in that food, respectively.

### Output

For each test case _i_, print a line containing "Case #_i_: " followed by
either "yes" if it is possible for Alex to eat the exact amount of each
macronutrient, or "no" if it is not possible.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 20  
10 ≤ **GP**, **GC**, **GF** ≤ 1000  
10 ≤ **P**, **C**, **F** ≤ 1000  



Sample input:
5
100 100 100
1
100 100 100
100 100 100
3
10 10 40
10 30 10
10 60 50
100 100 100
5
40 70 30
30 10 40
20 20 50
10 50 90
40 10 20
292 264 512
20
909 302 261
705 597 823
291 51 126
28 697 57
593 31 826
311 256 57
292 14 47
29 730 716
12 529 146
768 16 439
37 472 15
350 192 34
163 468 238
69 173 10
203 72 690
424 875 213
223 593 292
151 46 10
88 90 16
773 653 711
991 827 352
20
29 560 929
139 681 102
144 853 10
84 729 80
218 20 67
140 80 901
428 20 500
520 970 128
422 419 30
413 101 192
467 448 501
32 939 684
34 20 38
251 317 132
588 437 10
648 21 79
391 25 14
499 22 24
854 77 361
405 25 20


Sample output:
Case #1: yes
Case #2: no
Case #3: yes
Case #4: no
Case #5: yes
Problem: cooking_the_books (2015 quals)

Every business can make use of a good accountant and, if they're not big on
following the law, sometimes a bad one. Bad accountants try to make more money
for their employers by fudging numbers without getting caught.

Sometimes a bad accountant wants to make a number larger, and sometimes
smaller. It is widely known that tax auditors will fail to notice two digits
being swapped in any given number, but any discrepancy more egregious will
certainly be caught. It's also painfully obvious when a number has fewer
digits than it ought to, so a bad accountant will never swap the first digit
of a number with a 0.

Given a number, how small or large can it be made without being found out?

### Input

Input begins with an integer **T**, the number of numbers that need tweaking.
Each of the next **T** lines contains a integer **N**.

### Output

For the _i_th number, print a line containing "Case #_i_: " followed by the
smallest and largest numbers that can be made from the original number **N**,
using at most a single swap and following the rules above.

### Constraints

1 ≤ **T** ≤ 100  
0 ≤ **N** ≤ 999999999  
**N** will never begin with a leading 0 unless **N** = 0  



Sample input:
5
31524
897
123
10
5


Sample output:
Case #1: 13524 51324
Case #2: 798 987
Case #3: 123 321
Case #4: 10 10
Case #5: 5 5
Problem: laser_maze (2015 quals)

Standard mazes lose their mystery as one grows older. But throw in some
lasers, and suddenly you've got yourself a recipe for cross-generational
appeal. The object in any maze is to find your way from your starting point to
some goal. In a _Laser Maze_ you must additionally contend with laser turrets.

A laser turret is a stationary pillar that both blocks your movement and fires
lasers from one side. Every time you take a step (either up, down, left, or
right), every laser turret in the maze then rotates 90 degrees clockwise, and
then shoots a momentary laser blast in the direction that it is facing.
Needless to say, if you find yourself in the path of one of these lasers, you
won't be around long enough to find a way out. A wall is a stationary pillar
that blocks your movement, but does not fire lasers.

Lasers are powerful, but they do not pass through walls or laser turrets. The
laser turrets respond to your movements, so you can't stand still and wait for
the turrets to turn. If you reach the goal, but are immediately shot by a
laser, your efforts will have been in vain, so make sure you reach the goal
safely.

### Input

Input begins with an integer **T**, the number of mazes you'll explore. For
each maze, there is first a line containing two integers, **M** and **N**, the
height and width of the maze, respectively. The next **M** lines contain **N**
characters each, describing the maze:

. (empty space)  
# (wall)  
S (starting position)  
G (goal)  
< > ^ v (laser turrets)  

The four symbols for laser turrets signify turrets that are initially pointing
left, right, up, or down respectively before you take your first step.

### Output

For the _i_th maze, print a line containing "Case #_i_: " followed by the
smallest number of steps necessary to get to the exit without being hit by a
laser, or the string "impossible'' if there is no way to reach the goal
safely.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **M**, **N** ≤ 100  
Each maze will contain exactly one 'S' and exactly one 'G'.



Sample input:
5
2 5
##^##
S...G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G


Sample output:
Case #1: 6
Case #2: 4
Case #3: 3
Case #4: impossible
Case #5: 8
Problem: lazy_sort (2015 round2)

Much to Mr. Book's amazement, his entire first-grade math class has completed
the enormous amount of homework that he assigned only the day before. Being
hyperactive little kids, the grade-schoolers have dumped their homework, one
page per student, unceremoniously in a pile on Mr. Book's desk.

There are **N** students in Mr. Book's class, and they each have a distinct
integer student ID from 1 to **N**. Mr. Book wants the homework to be sorted
by student ID with the page from student #1 at the top, all the way down to
the page from student #**N** at the bottom. As we know, Mr. Book is a lazy
fellow. He's not going to put much effort into sorting the pile himself.

As he considers the pile before him, Mr. Book decides that he'll sort the
homework as follows: Every time he moves a page, he'll only move it from the
original pile to his finished stack, which initially starts empty.
Furthermore, he'll only move the top or bottom page of the remaining original
pile, and he'll only place it on the top or bottom of his neat destination
stack.

Is it possible for Mr. Book to sort the homework with such a method?

### Input

Input begins with an integer **T**, the number of test cases. For each case,
there are two lines. The first contains the integer **N**. The second contains
a permutation of the integers from 1 to **N**. These are the students' IDs in
the order their homework appears in the pile, from bottom to top.

### Output

For the **i**th case, print a line containing "Case #**i**: " followed by
"yes" if Mr. Book can sort the homework by student ID, or "no" if he can't.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 50,000  

### Explanation of Sample

In the first case, Mr. Book can just keep moving the top of the pile to the
top of his final stack, which will reverse the order of the pages.

In the fourth case, one approach is for Mr. Book to move pages 4, 3, 2, and 1
to the top of his final stack, and then move 5 and 6 to the bottom.



Sample input:
5
4
1 2 3 4
4
1 3 2 4
9
2 4 3 1 5 9 6 7 8
6
4 3 2 1 6 5
5
3 4 5 1 2


Sample output:
Case #1: yes
Case #2: no
Case #3: no
Case #4: yes
Case #5: yes
Problem: all_critical (2015 round2)

In the game _Theatrhythm Final Fantasy_, you poke a screen with a stick to the
beat of various songs. The goal is to poke the screen as accurately as
possible. If you hit a note at just the right time, you're awarded a
**critical**. Every song is broken into 20 sections, and if you get a
**critical** on every note in a section, then you get that section's golden
**critical bar**.

You would like to collect all 20 **critical bars** for every song. Songs vary
in difficulty, but each song has a fixed probability **p**, which is the
chance that you manage to secure any one **critical bar** on a single
playthrough. The chances are independent, so for any given pair of sections,
the probability of getting both **critical bars** in a single playthrough is
**p**2, and so on. **Critical bars** are saved between playthroughs, so you
don't have to win all of the **critical bars** in a single play of the song.
You might win the first 10 on one play, and then the last 10 on another.

On average, how many times will you have to play a song to win all 20
**critical bars**?

### Input

Input begins with an integer **T**, the number of songs you'll play. For each
song, there is a line containing a floating point number, **p**, the
probability of winning any particular **critical bar** on a single play of the
song.

### Output

For each song, output the expected number of times you need to play the song
before acquiring all 20 **critical bars**, rounded to five decimal points.

Absolute errors of up to 10-5 will be ignored.

### Constraints

1 ≤ **T** ≤ 20  
0.01 ≤ **p** ≤ 1.0  



Sample input:
5
0.1
0.12
0.123
0.1234
0.12345


Sample output:
Case #1: 34.64694
Case #2: 28.64398
Case #3: 27.91171
Case #4: 27.81676
Case #5: 27.80493
Problem: autocomplete_strikes_back (2015 round2)

This morning you woke up with an uncontrollable urge to send a text message
made up of **K** distinct words. But, can you believe it? Your new phone just
crashed and all of the words are missing from its dictionary! You used to have
**N** words in there, and you certainly don't have time to add all of them
back right now.

Your plan is to just choose **K** of the **N** possible words, add them to
your phone's dictionary, and then text each of them. To text a certain word,
you must either type the word itself, or any nonempty prefix of it which is
not a prefix of any other word in the dictionary.

What's the minimum number of letters you must type to send your message of
**K** words?

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the space-separated integers **N** and
**K**. Then, **N** lines follow, each containing a word that used to be in
your phone's dictionary.

### Output

For the **i**th test case, print a line containing "Case #**i**: " followed by
the minimum number of characters you need to type to send your text message.

### Constraints

1 ≤ **T** ≤ 20  
2 ≤ **N** ≤ 4,000  
1 ≤ **K** ≤ min(**N**-1, 100)  

The **N** words will have a total length of no more than 20,000 characters.  
The words are made up of only lower-case alphabetic characters.  
The words are pairwise distinct.  

### Explanation of Sample

In the first case, one option is to choose the words "tin", "tinny",
"gigantic", and "tilts". You can then text these words by typing "tin",
"tinn", "g", and "til", respectively, for a total of 3+4+1+3=11 letters.



Sample input:
5
6 4
tin
tiny
tinny
gigantic
tilt
tilts
3 2
apple
apricot
cherry
5 3
a
aa
aaa
aaaa
aaaaa
5 3
the
quick
brown
fox
jumped
8 7
cork
work
card
ward
font
front
word
sword


Sample output:
Case #1: 11
Case #2: 2
Case #3: 6
Case #4: 3
Case #5: 13
Problem: gentrification (2015 round3)

The residents of Townsville have made it clear to the mayor that they're
greatly concerned about gentrification, a process by which wealthy people move
into the city in large numbers, displacing the people who currently live
there. The mayor of Townsville knows a thing or two about this, and she would
like to put the people's minds at ease by determining the worst-case scenario.

Townsville is made up of **N** neighbourhoods, with **M** one-way roads
running between them. The **i**th road runs from neighbourhood **Ai** to
neighbourhood **Bi**. A swarm of rich migrants will move to the city all at
once, immediately gentrifying any neighbourhood they decide to move into.

The mayor knows the following facts about these new affluent residents: First,
they like to visit other gentrified neighbourhoods. If there's a way of
getting from their home neighbourhood to another gentrified neighbourhood,
they will surely go visit. Second, they never walk anywhere; they only drive.
Consequently, they'll get very angry if they end up in some neighbourhood with
no way to drive back home.

Putting these facts together, it means that if rich migrants move into and
gentrify any two neighbourhoods **u** and **v**, then it must be the case that
there is a series of roads connecting **u** to **v** if and only if there is a
series of roads connecting **v** to **u**.

Given this self-imposed constraint, and the layout of the roads in Townsville,
what is the maximum number of neighbourhoods that can be gentrified?

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the space-separated integers **N** and
**M**.

Then, **M** lines follow, the **i**th of which contains the space-separated
integers **Ai** and **Bi**.

### Output

For the **i**th test case, print a line containing "Case #**i**: " followed by
the maximum possible number of gentrified neighbourhoods.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 500  
1 ≤ **M** ≤ 20,000  
0 ≤ **Ai**, **Bi** < **N** for all 1 ≤ **i** ≤ **N**  
**Ai** ≠ **Bi** for all 1 ≤ **i** ≤ **N**   

### Explanation of Sample

In the first test case, you can get from any neighbourhood to any other
neighbourhood, so they can all be gentrified.

In the second test case, any single neighbourhood can be gentrified, but
that's it. If any two neighbourhoods are gentrified, there would be a path
from one to the other, but no path back.



Sample input:
5
4 4
0 1
1 2
2 3
3 0
4 3
0 1
1 2
2 3
6 6
0 1
1 0
2 3
3 2
4 5
5 4
6 8
0 1
1 0
2 3
3 2
4 5
5 4
0 2
1 4
4 4
0 1
0 2
1 3
2 3


Sample output:
Case #1: 4
Case #2: 1
Case #3: 6
Case #4: 4
Case #5: 2
Problem: fox_blocks (2015 finals)

Today, Mr. Fox is taking it easy by playing with some blocks in a 2D world.
Each block is an inch-by-inch square, and there are **N** stacks of blocks in
a row, with the **i**th stack having **Hi** blocks. For example, if **N**=6
and **H**={3, 1, 5, 4, 1, 6}, then the collection of blocks looks like this
(where an "X" denotes a block):

    .....X
    ..X..X
    ..XX.X
    X.XX.X
    X.XX.X
    XXXXXX

Ever curious, Mr. Fox would like to answer **Q** questions about his blocks
(without actually modifying them), the **i**th one being as follows:

"If I were to consider only the stacks from **Ai** to **Bi** inclusive,
getting rid of all of the other blocks, how many square inches of water would
my block structure be able to hold?"

As one might imagine, a given square inch can hold water if it doesn't contain
a block itself, but there is a block both somewhere to its left and somewhere
to its right at the same height. For example, if you were to take **Ai**=2 and
**Bi**=6, you would be left with the following block structure to consider
(where an "*" denotes an inch-by-inch square which can hold water):

    ....X
    .X**X
    .XX*X
    .XX*X
    .XX*X
    XXXXX

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 300,000  
1 ≤ **Q** ≤ 300,000  
1 ≤ **Hi** ≤ 109  
1 ≤ **Ai** ≤ **Bi** ≤ **N**  

### Input

Input begins with an integer **T**, the number of block structures Mr. Fox
has. For each structure, there is first a line containing the space-separated
integers **N** and **Q**. The next line contains the space-separated integers
**Hi**. Then follow **Q** lines, the **i**th of which contains the space-
separated integers **Ai** and **Bi**.

### Output

For the **i**th structure, print a line containing "Case #**i**: " followed by
the sum of the answers to the **Q** questions modulo 109+7.

### Explanation of Sample

In the first case, we consider prefixes of the block structure. The answers to
the queries are 0, 0, 0, 0, 0, 5, 5, 7, 7, 18, 18 for a total of 60.



Sample input:
5
11 11
2 4 5 3 2 6 1 3 1 8 1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
5 3
10 1 1 1 10
1 5
1 2
4 5
5 3
10 1 5 1 10
1 5
1 3
3 5
5 1
1 2 3 4 5
1 5
7 7
2 1 2 1 2 1 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7


Sample output:
Case #1: 60
Case #2: 27
Case #3: 31
Case #4: 0
Case #5: 9
Problem: fox_lochs (2015 finals)

Mr. Fox is going on a trip to Scotland to witness its many beautiful lochs!
He's heard that skimboarding is a fun pastime, somewhat similar to surfing,
and he'd like to give it a try while he's there.

He soon finds himself on a flat beach by the side of a loch. The beach can be
represented by an infinite 2D plane, with **N** axis-aligned rectangular pools
of shallow water on it. The **i**th pool has a pair of opposite corners at
coordinates (**x1**, **y1**) and (**x2**, **y2**). All of the pools can
arbitrarily overlap with one another, the result being that there's shallow
water everywhere within the union of the pools' rectangles (including right on
its edges), and no water anywhere else (Mr. Fox isn't brave enough to venture
into the loch itself yet!).

Mr. Fox would like to get a running start and then launch himself across the
water at some location, skimboarding across the pools in a straight line until
he hits a point with no water. In other words, his skimboarding debut will
consist of a line segment contained within the union of the pools' rectangles
(inclusive of borders). What's the maximum length this line segment can have?

### Input

Input begins with an integer **T**, the number of places Mr. Fox goes
skimboarding. For each place, there is first a line containing the integer
**N**. Then **N** lines follow, the **i**th of which contains the space-
separated integers **x1**, **y1**, **x2**, and **y2**.

### Output

For the **i**th place, print a line containing "Case #**i**: " followed by the
length of longest possible skimboarding path rounded to 6 decimal places.

Absolute errors of up to 2e-6 will be ignored.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 20  
-1,000,000 ≤ **x1** < **x2** ≤ 1,000,000   
-1,000,000 ≤ **y1** < **y2** ≤ 1,000,000   

### Explanation of Sample

In the first case, (2, 0) to (5, 5) is an optimal path.



Sample input:
5
2
2 0 4 3
3 2 5 5
1
0 0 3 4
3
0 0 3 2
0 1 3 3
0 2 3 4
3
0 0 1 1
2 0 4 2
5 0 8 3
3
-3 -3 3 3
-2 -2 2 2
-1 -1 1 1


Sample output:
Case #1: 5.830952
Case #2: 5.000000
Case #3: 5.000000
Case #4: 4.242641
Case #5: 8.485281
Problem: fox_focks (2015 finals)

Mr. Fox has opened up a fabulous Fock farm! A Fock is a cute little animal
which can have either red, green, or blue fur (these 3 possible colors can be
numbered 1, 2, and 3, respectively). Furthermore, a Fock's fur color can
change every second!

Mr. Fox owns a flock of **N** Focks, with the **i**th one initially having a
color of **Ci**. Every second, if the **i**th Fock currently has a color of
**a**, it will switch to having a color of **b** for the next second with
probability **Pi,a,b**%. All Focks change color simultaneously.

After a very large amount of time has gone by, Mr. Fox will take a single
photo of all of his Focks to help advertise his farm. In particular, he picks
an integer **t** at uniform random from the range [10100, 101000] and waits
that many seconds. He's hoping that the photo will make it look like his farm
has a well-balanced mix of Fock colors — it'll be no good if the photo ends up
featuring a strict majority of a single color (that is, strictly more than
**N**/2 of the Focks having the same color). What's the probability of this
occurring?

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 50,000  
1 ≤ **Ci** ≤ 3 for all **i**  
0 ≤ **Pi,a,b** ≤ 100 for all **i**, **a** and **b**  
**Pi,a,1** \+ **Pi,a,2** \+ **Pi,a,3** = 100 for all **i** and **a**  

### Input

Input begins with an integer **T**, the number of Fock farms Mr. Fox has. For
each farm, there is first a line containing the integer **N**. Then, for each
Fock **i**, 4 lines follow. The first of these lines contains the integer
**Ci**. The next three lines contain three space-separated integers each, with
the **b**th integer on the **a**th line being **Pi,a,b**.

### Output

For the **i**th farm, print a line containing "Case #**i**: " followed by the
probability that the **i**th picture contains a strict majority of some color
of Fock, rounded to 6 decimal places.

Absolute errors of up to 2e-6 will be ignored.

### Explanation of Sample

In the first case, the first Fock never changes color, so it'll still have
color 1 in the photo. The second Fock is likely to have color 2 for a while,
but by the time the photo is taken, it'll certainly have color 3. The third
Fock will have either color 2 or 3 in the photo, with equal probability.
Therefore, the photo will have a 50% chance of having a strict majority of
color 3, and a 50% chance of no strict majority.



Sample input:
5
3
1
100 0 0
0 100 0
0 0 100
2
100 0 0
0 99 1
0 0 100
2
100 0 0
0 50 50
0 50 50
3
1
100 0 0
0 100 0
0 0 100
2
100 0 0
0 100 0
0 0 100
3
100 0 0
0 100 0
0 0 100
3
1
100 0 0
0 100 0
0 0 100
2
100 0 0
0 100 0
0 0 100
2
100 0 0
0 100 0
0 0 100
3
1
34 33 33
33 34 33
33 33 34
2
34 33 33
33 34 33
33 33 34
3
34 33 33
33 34 33
33 33 34
3
1
10 20 70
30 30 40
50 20 30
2
30 10 60
90 5 5
15 15 70
3
98 1 1
98 1 1
98 1 1


Sample output:
Case #1: 0.500000
Case #2: 0.000000
Case #3: 1.000000
Case #4: 0.777778
Case #5: 0.812282
Problem: winning_at_sports (2015 round1)

In the game of _Sports_, the object is have more points than the other team
after a certain amount of time has elapsed. Scores are denoted by two hyphen-
separated integers. For example, scores may include 3-2, 4-1, or 10-0. The
first number is how many points you've scored, and the second is the number of
points scored by the opposing team. You're very good at _Sports_, and
consequently you always win. However, you don't always achieve victory the
same way every time.

The two most extreme kinds of victory are called **stress-free** and
**stressful**. In a **stress-free** victory, you score the first point and
from then on you always have more points than your opponent. In a
**stressful** victory, you never have more points than your opponent until
after their score is equal to their final score.

Given the final score of a game of _Sports_, how many ways could you arrange
the order in which the points are scored such that you secure a **stress-
free** or **stressful** win?

### Input

Input begins with an integer **T**, the number of games you'll play. For each
game, there is one line containing the final score of the game in the format
described above.

### Output

For the **i**th game, print a line containing "Case #**i**: " followed by two
space-separated integers, the number of ways you can achieve a **stress-free**
or **stressful** win, respectively. Since these numbers may be very large,
output them modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 100  

Since you always win, the first number in any final score will always be
larger than the second. Both scores will be non-negative integers not
exceeding 2000.

### Explanation of Sample

In the third test case, you can get a stress-free win by scoring points 1, 2,
and 4, or points 1, 2, and 3. You can get a stressful win by scoring points 2,
4, and 5, or points 3, 4, and 5.



Sample input:
5
2-1
3-1
3-2
10-5
1000-500


Sample output:
Case #1: 1 1
Case #2: 2 1
Case #3: 2 2
Case #4: 1001 42
Case #5: 70047606 591137401