hackercupai/hackercup huggingface dataset:
Problem: homework (2015 round1)

Your first-grade math teacher, Mr. Book, has just introduced you to an amazing
new concept — primes! According to your notes, a prime is a positive integer
greater than 1 that is divisible by only 1 and itself.

Primes seem fun, but without giving you and your 6-year-old colleagues time to
consider their implications, he's promptly gone on to define another term:
primacity. He explains that the primacity of an integer is the number of
distinct primes which divide it. For example, the primacity of 12 is 2 (as
it's divisible by primes 2 and 3), the primacity of 550 is 3 (as it's
divisible by primes 2, 5, and 11), and the primacity of 7 is 1 (as the only
prime it's divisible by is 7).

Following his lesson, Mr. Book has given you homework with some rather mean
questions of the following form: Given 3 integers **A**, **B**, and **K**, how
many integers in the inclusive range [**A**, **B**] have a primacity of
exactly **K**?

Mr. Book probably expects his little homework assignment to take you and your
classmates the rest of the year to complete, giving him time to slack off and
nap during the remaining math classes. However, you want to learn more things
from him instead! Can you use the skills you've learned in your first-grade
computer science classes to finish Mr. Book's homework before tomorrow's math
class?

### Input

Input begins with an integer **T**, the number of homework questions. For each
question, there is one line containing 3 space-separated integers: **A**,
**B**, and **K**.

### Output

For the **i**th question, print a line containing "Case #**i**: " followed by
the number of integers in the inclusive range [**A**, **B**] with a primacity
of **K**.

### Constraints

1 ≤ **T** ≤ 100  
2 ≤ **A** ≤ ** B** ≤ 107  
1 ≤ **K** ≤ 109  

### Explanation of Sample

In the first test case, the numbers in the inclusive range [5, 15] with
primacity 2 are 6, 10, 12, 14, and 15. All other numbers in this range have
primacity 1.



Sample input:
5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2


Sample output:
Case #1: 5
Case #2: 7
Case #3: 2
Case #4: 0
Case #5: 1
Problem: autocomplete (2015 round1)

Since you crave state-of-the-art technology, you've just purchased a phone
with a great new feature: autocomplete! Your phone's version of autocomplete
has some pros and cons. On the one hand, it's very cautious. It only
autocompletes a word when it knows exactly what you're trying to write. On the
other hand, you have to teach it every word you want to use.

You have **N** distinct words that you'd like to send in a text message in
order. Before sending each word, you add it to your phone's dictionary. Then,
you write the smallest non-empty prefix of the word necessary for your phone
to autocomplete the word. This prefix must either be the whole word, or a
prefix which is not a prefix of any other word yet in the dictionary.

What's the minimum number of letters you must type to send all **N** words?

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the integer **N**. Then, **N** lines
follow, each containing a word to send in the order you wish to send them.

### Output

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

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **N** ≤ 100,000  

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

**NOTE:** The input file is about 10-20MB. 

### Explanation of Sample

In the first test case, you will write "h", "he", "l", "hil", "hill", for a
total of 1 + 2 + 1 + 3 + 4 = 11 characters.



Sample input:
5
5
hi
hello
lol
hills
hill
5
a
aa
aaa
aaaa
aaaaa
5
aaaaa
aaaa
aaa
aa
a
6
to
be
or
not
two
bee
3
having
fun
yet


Sample output:
Case #1: 11
Case #2: 15
Case #3: 11
Case #4: 9
Case #5: 3
Problem: text_editor (2016 quals)

You have a list of **N** distinct words, consisting of only lowercase letters.
You'd like to print any **K** words from this list, one per page, in any
order.

You will accomplish this using a very basic text editor. It supports 3 types
of operations: typing a letter, deleting the previous letter, and printing the
current document. Note that it does not allow the cursor to be moved! This
means that the first operation may only add a letter to the end of the
document, and the second may only delete the last letter (if any). Due to
issues with memory leakage, you also need to remember to leave the document
completely empty after you've printed your **K** words!

What's the minimum number of operations required to get the job done?

As an example, let's say that you want to print 3 of the following 5 words:

    a
    hair
    box
    awesome
    hail

One optimal sequence of 15 operations is as follows:

  * \- type 'h', 'a', 'i', and 'r' (document = 'hair') 
  * \- print 
  * \- backspace (document = 'hai') 
  * \- type 'l' (document = 'hail') 
  * \- print 
  * \- backspace 4 times (document = empty) 
  * \- type 'a' (document = 'a') 
  * \- print 
  * \- backspace (document = empty) 

### Input

Input begins with an integer **T**, the number of sets of words you want to
print. For each set, there is first a line containing the space-separated
integers **N** and **K**. The next **N** lines contain the set of words, one
per line.

### Output

For the **i**th set of words, print a line containing "Case #**i**: " followed
by the minimum number of operations required to print **K** of the words and
then leave the document empty.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **K** ≤ **N** ≤ 300  
The total length of all **N** words in each set will be at most 100,000
characters.  



Sample input:
5
3 3
x
y
z
2 1
loooong
tiny
4 3
fff
fffff
ff
ffff
5 3
a
hair
box
awesome
hail
8 6
fox
of
xfox
foo
foxxx
off
foff
foox


Sample output:
Case #1: 9
Case #2: 9
Case #3: 11
Case #4: 15
Case #5: 26
Problem: high_security (2016 quals)

A top-secret algorithmic research facility has decided to up its security by
hiring guards to keep watch over the premises. After all, they don't want
anyone sneaking in and learning the answers to questions such as "does P =
NP?" and "what are the solutions to the 2016 Facebook Hacker Cup problems?".

When viewed from above, the facility can be modeled as a grid **G** with 2
rows and **N** columns. The **j**th cell in the **i**th row is either empty
(represented by **Gi,j** = ".") or occupied by a building (**Gi,j** = "X"),
and the grid includes at least one empty cell.

Guards may be potentially stationed in any of the empty cells. A guard can see
not only their own cell, but also all contiguous empty cells in each of the 4
compass directions (up, down, left, and right) until the edge of the grid or a
building. For example, in the grid below, the guard ("G") can see every cell
marked with an asterisk ("*"):

    .*.X.X..
    *G*****X

What is the minimum number of guards required such that every empty cell in
the grid can be seen by at least one of them?

### Input

Input begins with an integer **T**, the number of facilities that need
guarding. For each facility, there is first a line containing the integer
**N**. The next line contains the grid cells **G1,1** to **G1,N** in order.
The third line contains the grid cells **G2,1** to **G2,N** in order.

### Output

For the **i**th facility, print a line containing "Case #**i**: " followed by
the number of guards required to guard the facility.

### Constraints

1 ≤ **T** ≤ 200  
1 ≤ **N** ≤ 1,000  

### Explanation of Sample

In the first case, one solution is to place three guards as follows:

    .G.X.XG.
    ....G..X



Sample input:
5
8
...X.X..
.......X
5
.X.X.
.XXX.
7
.....X.
.X.....
9
..X.X.X..
..X...X.X
15
.X..........X..
.X...XX.X.X....


Sample output:
Case #1: 3
Case #2: 3
Case #3: 2
Case #4: 5
Case #5: 6
Problem: price (2016 quals)

You've managed to become a contestant on the hottest new game show, The Price
is Correct!

After asking you to come on down to the stage, the show's host presents you
with a row of **N** closed boxes, numbered from 1 to **N** in order, each
containing a secret positive integer. A curtain opens to reveal a shiny, new
tricycle — you recognize it as an expensive, top-of-the-line model.

The host then proceeds to explain the rules: you must select a contiguous
sequence of the boxes (boxes a..b, for some 1 ≤ a ≤ b ≤ **N**). Your chosen
boxes will then be opened, and if the sum of the numbers inside is no greater
than the price of the tricycle, you win it!

You'd sure like to win that tricycle. Fortunately, not only are you aware that
its price is exactly **P**, but you've paid off the host to let you in on the
contents of the boxes! You know that each box **i** contains the number
**Bi**.

How many different sequences of boxes can you choose such that you win the
tricycle? Each sequence is defined by its starting and ending box indices (a
and b).

### Input

Input begins with an integer **T**, the number of times you appear on The
Price is Correct. For each show, there is first a line containing the space-
separated integers **N** and **P**. The next line contains **N** space-
separated integers, **B1** through **BN** in order.

### Output

For the **i**th show, print a line containing "Case #**i**: " followed by the
number of box sequences that will win you the tricycle.

### Constraints

1 ≤ **T** ≤ 40  
1 ≤ **N** ≤ 100,000  
1 ≤ **P** ≤ 1,000,000,000  
1 ≤ **Bi** ≤ 1,000,000,000  

### Explanation of Sample

In the first case no sequence adds up to more than 50, so all 10 sequences are
winners. In the fourth case, you can select any single box, or the sequences
(1, 2), (1, 3), and (2, 3), for 9 total winning sequences.



Sample input:
5
4 50
10 10 10 10
4 50
51 51 51 51
3 1000000000
1000000000 1000000000 1000000000
6 6
1 2 3 4 5 6
10 77
12 3 52 25 9 83 45 21 33 3


Sample output:
Case #1: 10
Case #2: 0
Case #3: 3
Case #4: 9
Case #5: 18
Problem: boomerang_constellations (2016 quals)

The night sky can be modeled as an infinite 2D plane. There are **N** stars at
distinct positions on this plane, the **i**th of which is at coordinates
(**Xi**, **Yi**).

A boomerang constellation is a pair of distinct equal-length line segments
which share a single endpoint, such that both endpoints of each segment
coincide with a star's location.

Two boomerang constellations are distinct if they're not made up of the same
unordered pair of line segments. How many distinct boomerang constellations
can you spot?

### Input

Input begins with an integer **T**, the number of nights on which you look out
at the sky. For each night, there is first a line containing the integer
**N**. Then, **N** lines follow, the **i**th of which contains the space-
separated integers **Xi** and **Yi**.

### Output

For the **i**th night, print a line containing "Case #**i**: " followed by the
number of boomerang constellations in the night sky.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **N** ≤ 2,000  
-10,000 ≤ **Xi**, **Yi** ≤ 10,000   

### Explanation of Sample

On the first night, every pair of stars is a unique distance apart, so there
are no boomerang constellations. On the second night, there are 4 boomerang
constellations. One of them consists of the line segments (0,0)-(0,2) and
(0,2)-(0,4).



Sample input:
5
3
0 0
0 1
0 3
5
0 0
0 1
0 2
0 3
0 4
4
0 0
0 100
100 0
100 100
4
0 0
-3 4
0 5
-5 0
6
5 6
6 5
7 6
6 7
7 8
8 7


Sample output:
Case #1: 0
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 12
Problem: carnival_coins (2016 round2)

At the local carnival you find a midway game advertising "TONS OF FABULOUS
PRIZES". Certainly a fabulous prize or two would make your time worthwhile. It
turns out that "TONS" is actually a bit of of an understatement. There are in
fact _infinitely_ many prizes available. Consequently, the game operator is
willing to give you a chance to score multiple prizes in a single game (for a
nominal fee).

After you hand over your money, the game operator gives you **N** coins. Each
coin has the same probability **p** of landing on heads when flipped (and
consequently probability 1 - **p** of landing on tails). She also gives you a
goal, an integer **K**.

As long as you still have some coins remaining, you can select any number of
them and flip them all simultaneously. These coins are then taken away. If at
least **K** of them land on heads, you win a prize. If you play optimally,
what is the expected number of prizes you'll manage to win?

### Input

Input begins with an integer **T**, the number of times you play the game. For
each attempt, there is a line containing the space-separated values **N**,
**K** and **p**. **N** and **K** are integers, and **p** is given with at most
16 decimal places.

### Output

For the **i**th attempt, print a line containing "Case #**i**: " followed by
the expected number of prizes you'll win. Your output should have at most 10-6
absolute or relative error.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **N** ≤ 3,000  
1 ≤ **K** ≤ 3,000  
0 ≤ **p** ≤ 1  

### Explanation of Sample

In the first case, flipping the coins together gives you a 75% chance of
winning a prize. If you flip them separately, you get a 50% chance on each
flip. The latter approach is better, giving you 1 expected prize rather than
0.75 expected prizes. In the second case, it is optimal to partition the ten
coins into two sets of five. In the third case, it is optimal to flip all ten
coins at once.



Sample input:
5
2 1 0.5
10 5 0.9
10 5 0.1
3000 50 0.123
3000 50 0.987


Sample output:
Case #1: 1.000000000
Case #2: 1.180980000
Case #3: 0.001634937
Case #4: 5.712907306
Case #5: 56.182751225
Problem: costly_labels (2016 round2)

You've got yourself an unrooted tree with **N** nodes — that is, a connected,
undirected graph with **N** nodes numbered from 1 to **N**, and **N** \- 1
edges. The **i**th edge connects nodes **Ai** and **Bi**.

You'd like to spend as little money as possible to label each node with a
number from 1 to **K**, inclusive. It costs **Ci,j** dollars to label the
**i**th node with the number **j**.

Additionally, after the whole tree has been labelled, you must pay **P** more
dollars for each node which has at least one pair of neighbours that share the
same label as each other. In other words, for each node **u**, you must pay
**P** dollars if there exist two other nodes **v** and **w** which are both
adjacent to node **u**, such that the labels on nodes **v** and **w** are
equal (note that node **u**'s label is irrelevant). You only pay the penalty
of **P** dollars once for a given central node **u**, even if it has multiple
pairs of neighbours which satisfy the above condition.

What's the minimum cost (in dollars) to label all **N** nodes?

### Input

Input begins with an integer **T**, the number of trees. For each tree, there
is first a line containing the space-separated integers **N**, **K**, and
**P**. Then, **N** lines follow, the **i**th of which contains the space-
separated integers **Ci,1** through **Ci,K** in order. Then, **N** \- 1 lines
follow, the **i**th of which contains the space-separated integers **Ai** and
**Bi**

### Output

For the **i**th tree, print a line containing "Case #**i**: " followed by the
minimum cost to label all of the tree's nodes.

### Constraints

1 ≤ **T** ≤ 30  
1 ≤ **N** ≤ 1,000  
1 ≤ **K** ≤ 30  
0 ≤ **P** ≤ 1,000,000  
0 ≤ **Ci,j** ≤ 1,000,000  
1 ≤ **Ai**, **Bi** ≤ **N**  

### Explanation of Sample

In the first case, there is only one node which must be painted the only
possible color for 111 dollars. In the second case, there is only one color,
so a penalty of 8 dollars must be paid since node 2 has two neighbors with the
same color. In total we pay 1 + 2 + 4 + 8 = 15 dollars. In the third case,
it's optimal to paint nodes 1 and 2 with color 1, and node 3 with color 2. The
total cost is 4 + 8 + 3 = 15 dollars.



Sample input:
5
1 1 1
111
3 1 8
1
2
4
1 2
2 3
3 2 10
4 7
8 9
2 3
1 2
2 3
4 2 99
0 1
0 1
0 1
0 0
4 1
2 4
4 3
4 3 99
0 1 0
0 1 0
0 1 0
0 0 0
4 1
2 4
4 3


Sample output:
Case #1: 111
Case #2: 15
Case #3: 15
Case #4: 99
Case #5: 1
Problem: boomerang_decoration (2016 round2)

As an experienced boomerangist, you take great pride in your trusty boomerang,
and you'd like to be able to show it off! Unfortunately, it doesn't look quite
right yet...

Like all boomerangs, yours is symmetrical in shape, with two **N** millimetre-
long halves. However, what's not necessarily symmetrical is its paint job —
each millimetre-long section of each half has been painted some color. There
are 26 possible colors, represented by uppercase letters ("A" to "Z"), and the
**i**th section of the left half (counting from the left end) has color
**Ai**, while the **i**th section of the right half (counting from the right
end) has color **Bi**. You'd like your boomerang to be completely symmetrical
(which is the case when the **i**th section in the left half has the same
color as the **i**th section in the right half, for all 1 ≤ **i** ≤ **N**) as
soon as possible!

To that end, you're enlisting the help of your two best friends, Jack and
Jill, to repaint the left half of your boomerang until it matches the right
half. Every second, Jack may paint over a "prefix" of the left half with a
solid color, while Jill may simultaneously paint over a disjoint "suffix". In
other words, every second, Jack and Jill will each select a color (from "A" to
"Z"), Jack will select a value **x** (0 ≤ **x** ≤ **N**), and Jill will select
a value **y** (0 ≤ **y** ≤ **N - x**). Then, Jack will repaint the first **x**
sections of the left half of the boomerang with his color, while Jill will
repaint the last **y** sections of the left half of the boomerang with her
color. Painting over a section completely overwrites its previous color.

What's the minimum amount of time (in seconds) it can take Jack and Jill to
make your boomerang completely symmetrical?

### Input

Input begins with an integer **T**, the number of boomerangs you want to
decorate. For each boomerang, there is first a line containing the integer
**N**, then two lines that each contain a string of length **N**. The **i**th
character of the second line is **Ai**. The **i**th character of the third
line is **Bi**.

### Output

For the **i**th boomerang, print a line containing "Case #**i**: " followed by
the minimum number of seconds it will take Jack and Jill to make your
boomerang's paint job symmetrical.

### Constraints

1 ≤ **T** ≤ 75  
1 ≤ **N** ≤ 100,000  

### Explanation of Sample

The first boomerang is already symmetrical, so no work needs to be done. The
second boomerang can be made symmetrical in 1 second. Jack will cover the
first millimetre with 'C', and Jill will cover the third millimetre with 'A'.
The third boomerang takes 2 seconds to paint. One possible solution is for
Jack to paint the first two millimetres with 'A' and then the first millimetre
with 'B'.



Sample input:
5
3
ABC
ABC
3
ABC
CBA
3
ABC
BAC
9
FOXENRULE
NOREAALLY
19
DOYOULIKEBOOMERANGS
OOBOOOOVVBOOEAAAGGS


Sample output:
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 3
Case #5: 4
Problem: snakes_and_ladders (2016 round2)

As the owner of a vast collection of fine ladders, you would like to display
them to potential onlookers. You've decided to stand your **N** ladders up
vertically, with their bases at distinct points on a horizontal number line.
The **i**th ladder's base is at position **Xi**, and it has height **Hi**.

The local snake population has taken an interest in your ladders. As everyone
knows, snakes love nothing more than to suspend themselves horizontally above
the ground! In particular, a snake of length **L** is able to suspend itself
between the tops of two ladders **a** and **b** if and only if they meet the
following conditions:

  * \- the ladders are exactly **L** units apart (|**Xa** \- **Xb**| = **L**) 
  * \- the ladders are of equal height (**Ha** = **Hb**) 
  * \- there are no taller ladders in between them (there exists no ladder **c** such that min{**Xa**, **Xb**} < **Xc** < max{**Xa**, **Xb**} and **Hc** > **Ha**) 

A number of snakes are planning to take up residence amongst your ladders. In
particular, for every position in which a snake could suspend itself (in other
words, for every distinct, unordered pair of ladders **a** and **b**), one
snake will move in of the appropriate length.

You'll have no choice but to take care of these snakes, of course. To feed a
snake of length **L**, it'll cost you **L**2 dollars daily. To prepare your
budget, you'd like to calculate how many dollars you'll be spending each day
on your new pets!

### Input

Input begins with an integer **T**, the number of sets of ladders you own. For
each set, there is first a line containing the integer **N**. Then, **N**
lines follow, the **i**th of which contains two space-separated integers,
**Xi** and **Hi**.

### Output

For the **i**th set of ladders, print a line containing "Case #**i**: "
followed by the daily feeding cost of all the snakes that move in, modulo 109
\+ 7.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **N** ≤ 200,000  
0 ≤ **Xi**, **Hi** ≤ 1,000,000,000

### Explanation of Sample

In the first case, one snake will move in between your two ladders. It will
have length 20, so it will cost 202 = 400 dollars a day to feed. In the third
case, one snake will move in between the ladders of height 3, and another will
move in between the ladders at X = 2 and X = 3. The first snake has length 3,
and the second has length 1. The total cost is therefore 32 \+ 12 = 10.



Sample input:
5
2
10 100
30 100
3
10 100
30 100
40 100
5
1 3
4 3
3 2
5 2
2 2
8
5 6
8 1
9 5
13 5
15 6
16 6
19 7
100 6
4
1 1000000000
1000 1000000000
1000000 1000000000
1000000000 1000000000


Sample output:
Case #1: 400
Case #2: 1400
Case #3: 10
Case #4: 238
Case #5: 14991178
Problem: boomerang_farm (2016 round3)

You're a proud boomerang farmer, like your father before you (and his father
before him, but quite unlike his grandfather). Your boomerang field can be
modelled as a 2D grid of square cells, with **M** rows and **N** columns. Each
cell contains a boomerang lying flat on the ground, in one of four possible
orientations called A, B, C, and D:

![]({{PHOTO_ID:263973168278076}})

For example, your field might look as follows:

![]({{PHOTO_ID:572878846700654}})

As you can see, there are 2 points at which pairs of boomerangs are touching
one another at their endpoints. As all boomerang farmers know, that could
stunt the growth of your precious boomerangs!

Fortunately, you can salvage the situation by rotating boomerangs by integer
multiples of 90 degrees. In particular, rotating a single boomerang by 90
degrees either clockwise (for example, changing its orientation from A to B)
or counter-clockwise (for example, from A to D) takes 1 minute. You may rotate
a single boomerang multiple times.

You have **K** minutes of free time that you can use to fix up your field as
well as you can (though you don't have to use all of this time). What's the
minimum number of pairs of touching boomerangs that you can end up with at the
end of this time? For example, given 2 minutes to work on the above field, you
could rotate the top-right boomerang counter-clockwise and the bottom-left one
clockwise to end up with no touching boomerangs:

![]({{PHOTO_ID:3313736538657036}})

### Input

Input begins with an integer **T**, the number of fields. For each field,
there is first a line containing the space-separated integers **M**, **N**,
and **K**. Then, **M** lines follow, the **i**th of which contains a string of
length **N** representing the **i**th row of the field as described above.

### Output

For the **i**th field, print a line containing "Case #**i**: " followed by the
minimum number of touching boomerang pairs that will remain after you work the
field optimally.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **M**, **N** ≤ 100  
0 ≤ **K** ≤ 1,000  

### Explanation of Sample

The fifth field is the example given above.



Sample input:
5
1 1 0
A
1 2 0
CD
1 2 400
CD
2 2 1
CD
BA
2 3 2
DBD
CAD


Sample output:
Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 3
Case #5: 0