hackercupai/hackercup huggingface dataset:
Problem: alien_game (2011 finals)

Aliens on the Unknown planet have a tradition of playing a game called Loiten.
It is played by two players who alternate turns. There are **N** buckets with
apples standing in one line in front of the players. They are numbered from
left to right with integers starting from 1.

In one turn a player can select one of the buckets, which is not the first and
not the last and has a positive number of apples in it, and move all of that
bucket's apples to the bucket adjacent to the left and at the same time move
all of them to the bucket adjacent to the right. That's right, the number of
apples can be negative as it is a really strange planet. Thus, if there are 3
consecutive buckets with the number of apples being **x**, **y**, **z**, then
you can perform the move if **y** is greater than zero. The resulting capacity
of the buckets will be as follows: **x+y**, **-y**, **z+y**. The first player
who can't make a move loses.

You happen to know one of the aliens from the Unknown planet, named Popo. He
is a very good Loiten player, and has reached the Loiten Finals. On the day
prior to the game, he found out the number of apples in each of the buckets.
Unfortunately, his memory is not that good, and he can't remember the number
of apples in the **P**-th bucket. He just remembers that it is a number with
absolute value not greater than **F**.

Now, he is asking you to help him to calculate his chances. The players at the
Finals are so good that they only make optimal moves to maximize their chance
of winning. If neither player can win, the game is considered a draw. You are
to find the number of possible apple counts for the bucket with an unknown
number of apples where Popo will win. Popo is also sure that he is the one to
make the first turn.

## Input

The first line of the input file consists of a single number **T**, the number
of test cases. Each test case begins with a line containing two integers
**N**, the number of buckets and **P**, the number of the bucket with the
unknown amount of apples. It is followed by a line containing **N** integers,
the numbers of apples in the corresponding buckets. The **P**th number on this
line is the positive integer **F** and corresponds to the constraint on the
number of apples in the **P**-th bucket.  
  

## Output

Output **T** lines, with the answer to each test case on a single line, the
number of possible values for unknown bucket.  
  

## Constraints

**T** = 50  
1≤ **P** ≤ **N** ≤ 2,000.  
1≤ **F** ≤ 1,000,000,000,000.  
The number of apples in each bucket at the start of the game has an absolute
value not greater than 1,000,000,000,000.



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


Sample output:
Case #1: 2
Case #2: 1
Case #3: 5
Case #4: 2
Case #5: 2
Problem: polynomial_factoring (2011 round1c)

A polynomial in `x` of degree **D** can be written as:

    aDxD + aD-1xD-1 + ... + a1x1 + a0

In some cases, a polynomial of degree `**D**` can also be written as the
product of two polynomials of degrees `**D1**` and `**D2**`, where `**D = D1
\+ D2**`. For instance,

    4 x2 + 11 x 1 + 6 = (4 x1 + 3) * (1 x1 + 2)

In this problem, you will be given two polynomials, denoted `**F**` and
`**G**`. Your task is to find a polynomial `**H**` such that `**G** * **H** =
**F**`, and each `ai` is an integer.

## Input

You should first read an integer `**N ≤ 60**`, the number of test cases. Each
test case will start by describing `**F**` and then describe `**G**`. Each
polynomial will start with its degree `0 ≤ **D** ≤ 20`, which will be followed
by `**D**+1` integers, denoting `a0, a1, ... , aD`, where `-10000 ≤ ai ≤
10000`. Each polynomial will have a non-zero coefficient for it's highest
order term.

## Output

For each test case, output a single line describing `**H**`. If `**H**` has
degree `**DH**`, you should output a line containing `**DH** \+ 1` integers,
starting with `a0` for `**H**`. If no `**H**` exists such that `**G*H=F**`,
you should output "no solution".



Sample input:
5
2 6 11 4
1 3 4
2 1 2 1
1 1 1
2 1 0 -1
1 1 1
1 1 1
2 1 2 1
5 1 1 1 1 1 1
3 1 1 1 1


Sample output:
Case #1: 2 1
Case #2: 1 1
Case #3: 1 -1
Case #4: no solution
Case #5: no solution
Problem: risky_slide (2011 round1c)

Being a confident and accomplished programmer, you are naturally widely
considered to be one of the preeminent dancers of your generation.
Unfortunately this means your dancing is under considerable public scrutiny,
and your critics are often quick to point out when your moves seem to be
getting stale. To prevent such a debacle, you are working on a new maneuver
you're calling "the risky slide".  
  
You haven't worked out some of the details like flourishes or vocalizations
that will accompany the risky slide, but you do know that the core of the move
is a standing slide across a stretch of dance floor. You need to perfect the
execution of your slide, so you are looking for the ideal spot in your
apartment to practice.  
  
You live a fairly ascetic lifestyle, so your apartment is a simple rectangle
with a tiled floor and no furniture or contents of any kind. You will practice
the risky slide by starting out standing at the edge of some tile and running
parallel to one of the walls of the apartment, and at the transition between
some pair of tiles you will go from running to sliding. Your goal is to
achieve the longest possible slide, with distance measured as the number of
tiles you completely traverse during the slide (partial traversal doesn't
count).  
  
This would be an easy problem, but the style of the tiles in your apartment
introduces a complication. Each tile has a particular stickiness that affects
both how well you can run and how well you can slide on it. Each tile has a
stickiness rating between 1 and 9, inclusive. The stickiness affects your
movement as follows:  
Running across a tile with stickiness **s** grants **s** units of kinetic
energy. For example, a tile with stickiness 9 is not slippery at all and you
can run across it very efficiently, whereas a tile with stickiness 1 is quite
slippery and does not help you increase your kinetic energy much as you run
across it.  
Sliding across a tile with stickiness **s** robs you of **s** units of kinetic
energy. If a tile would reduce your kinetic energy below 0, you stop sliding
somewhere in the middle of the tile and fail to traverse it completely.  
  

## Input

Your input will consist of a single integer **N** followed by a newline and
**N** test cases. Each case begins with a line containing integers **R** and
**C**, the number of rows and columns, respectively, of tiles in your
apartment. This will be followed by **R** lines, each containing a string of
length **C**, describing the layout of the tiles in your apartment. The value
of each element in these strings is the stickiness as defined above of the
corresponding tile.  
  

## Output

Output, for each test case and separated by newlines, the maximal possible
number of complete tiles that you can traverse in a single slide through your
apartment.  
  

## Constraints

**N** ≤ 20  
1 ≤ **R**, **C** ≤ 50  
Characters representing tiles will all be between '1' and '9', inclusive.



Sample input:
5
1 1
5
2 3
112
324
5 5
55555
51115
51915
51115
55555
1 4
5222
1 5
52222


Sample output:
Case #1: 0
Case #2: 2
Case #3: 3
Case #4: 2
Case #5: 3
Problem: n_factorful (2011 round1c)

A number is called **n**-factorful if it has exactly **n** distinct prime
factors. Given positive integers **a**, **b**, and **n**, your task is to find
the number of integers between **a** and **b**, inclusive, that are
**n**-factorful. We consider 1 to be 0-factorful.  
  

## Input

Your input will consist of a single integer **T** followed by a newline and
**T** test cases. Each test cases consists of a single line containing
integers **a**, **b**, and **n** as described above.  
  

## Output

Output for each test case one line containing the number of **n**-factorful
integers in [**a**, **b**].  
  

## Constraints

**T** = 20  
1 ≤ **a** ≤ **b** ≤ 107  
0 ≤ **n** ≤ 10



Sample input:
5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000 0


Sample output:
Case #1: 2
Case #2: 2
Case #3: 0
Case #4: 8
Case #5: 1
Problem: billboards (2012 quals)

We are starting preparations for Hacker Cup 2013 really early. Our first step
is to prepare billboards to advertise the contest. We have text for hundreds
of billboards, but we need your help to design them.

The billboards are of different sizes, but are all rectangular. The billboard
widths and heights are all integers. We will supply you with the size in
inches and the text we want printed. We want you to tell us how large we can
print the text, such that it fits on the billboard without splitting any words
across lines. Since this is to attract hackers like yourself, we will use a
monospace font, meaning that all characters are of the same width (e.g.. 'l'
and 'm' take up the same horizontal space, as do space characters). The
characters in our font are of equal width and height, and there will be no
additional spacing between adjacent characters or adjacent rows. If you print
a word on one line and print the next word on the next line, you do not need
to print a space between them.

Let's say we want to print the text "Facebook Hacker Cup 2013" on a 350x100"
billboard. If we use a font size of 33" per character, then we can print
"Facebook" on the first line, "Hacker Cup" on the second and "2013" on the
third. The widest of the three lines is "Hacker Cup", which is 330" wide.
There are three lines, so the total height is 99". We cannot go any larger.

### Input

The first line of the input file contains a single integer T: the number of
test cases. T lines follow, each representing a single test case in the form
"W H S". W and H are the width and height in inches of the available space. S
is the text to be written.

### Output

Output T lines, one for each test case. For each case, output "Case #t: s",
where t is the test case number (starting from 1) and s is the maximum font
size, in inches per character, we can use. The size must be an integral number
of inches. If the text does not fit when printed at a size of 1", then output
0.

### Constraints

  * 1 ≤ T ≤ 20 
  * 1 ≤ W, H ≤ 1,000 
  * The text will contain only lower-case letters a-z, upper-case letters A-Z, digits 0-9 and the space character 
  * The text will not start or end with the space character, and will never contain two adjacent space characters 
  * The text in each case contains at most 1,000 characters 



Sample input:
5
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup


Sample output:
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7
Problem: alphabet_soup (2012 quals)

Alfredo Spaghetti really likes soup, especially when it contains alphabet
pasta. Every day he constructs a sentence from letters, places the letters
into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Facebook
Hacker Cup starts today! Thus, he decided to construct the phrase "HACKERCUP".
As he already added the letters to the broth, he is stuck with the letters he
originally selected. Help Alfredo determine how many times he can place the
word "HACKERCUP" side-by-side using the letters in his soup.

### Input

The first line of the input file contains a single integer T: the number of
test cases. T lines follow, each representing a single test case with a
sequence of upper-case letters and spaces: the original sentence Alfredo
constructed.

### Output

Output T lines, one for each test case. For each case, output "Case #t: n",
where t is the test case number (starting from 1) and n is the number of times
the word "HACKERCUP" can be placed side-by-side using the letters from the
sentence.

### Constraints

  * 1 < T ≤ 20 
  * Sentences contain only the upper-case letters A-Z and the space character 
  * Each sentence contains at least one letter, and contains at most 1,000 characters, including spaces 



Sample input:
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP


Sample output:
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1
Problem: auction (2012 quals)

You have encountered a new fancy online auction that offers lots of products.
You are only interested in their price and weight. We shall say that product A
is strictly preferred over product B if A costs less than B and is not heavier
(they may be of equal weight) or if A weighs less and is not more expensive
(they can have equal price).

We shall call a product A a bargain if there is no product B such that B is
better than A. Similarly, we shall call a product C a terrible deal if there
exists no product D such that C is better than D. Note that according to our
definitions, the same product may be both a bargain and a terrible deal! Only
wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The
number of products, N, is too large for your human-sized brain though.
Fortunately, you discovered that the auction manager is terribly lazy and
decided to sell the products based on a very simple pseudo-random number
generator.

If product i has price Pi and weight Wi, then the following holds for product
i+1:

  * Pi = ((A*Pi-1 \+ B) mod M) + 1 (for all i = 2..N) 
  * Wi = ((C*Wi-1 \+ D) mod K) + 1 (for all i = 2..N) 

You carefully calculated the parameters for the generator (P1, W1, M, K, A, B,
C and D). Now you want to calculate the number of terrible deals and bargains
on the site.

### Input

The first line of the input file contains a single integer T: the number of
test cases. T lines follow, each representing a single test case with 9 space-
separated integers: N, P1, W1, M, K, A, B, C and D.

### Output

Output T lines, one for each test case. For each case, output "Case #t: a b",
where t is the test case number (starting from 1), a is the number of terrible
deals and b is the number of bargains.

### Constraints

  * 1 ≤ T ≤ 20 
  * 1 ≤ N ≤ 1018
  * 1 ≤ M, K ≤ 107
  * 1 ≤ P1 ≤ M 
  * 1 ≤ W_1 ≤ K 
  * 0 ≤ A,B,C,D ≤ 109



Sample input:
5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19


Sample output:
Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1
Problem: monopoly (2012 round2)

In a certain business sector there are currently N small companies, each
having just a single employee. These employees are numbered 1 through N.

The business sector is about to be transformed into a monopoly. This will
happen through a series of mergers, until there is only one company. A single
merger involves two companies. In a merger, the president of one company
becomes the direct report of the president of the other company, preserving
the rest of the hierarchies of both companies.

You will be given the descriptions of all mergers. Depending on how they are
performed (which of the two presidents involved becomes the president of the
new company), the hierarchy can of the final company can take different
shapes. We want the hierarchy of the final company to be as shallow as
possible. The task is to find the smallest possible number of levels in the
final hierarchy.

There is also a limit D on the number of direct reports any employee can have.
Because of this limit, there may be only one way to accomplish a certain
merger, or it might even be impossible. However, there will always be some way
to accomplish all the mergers.

### Input

The first line contains the number of test cases T.

Each test case starts with a blank line. The next line contains two integers,
N and D.

Each of the following N-1 lines describes a single merger, with two integers
between 1 and N. These are the employees whose companies are merging. The two
employees will never already be part of the same company.

The mergers must be performed in the order in which they are given.

### Constraints

5 ≤ T ≤ 20  
2 ≤ N ≤ 30,000  
1 ≤ D ≤ 5,000  
The input test cases will be such that it is possible to accomplish all
mergers.  

### Output

For each of the test cases numbered in order from 1 to T, output "Case #i: "
followed by a single integer, the smallest number of levels in the final
hierarchy.

### Examples

In the first example, we have N=3 and D=2. The first merger happens between
the companies of employees 1 and 2. In the resulting company we can have
employee 1 as the president with 2 as his report, or vice versa. Next this
company merges with the company of employee 3. If we have employee 3 become
the president, the hierarchy will be a chain 3-1-2 or 3-2-1. If 1 or 2 become
the president, that president will have the other two employees as direct
reports. This last hierarchy has two levels.



Sample input:
5

3 2
1 2
1 3

3 1
1 2
1 3

4 2
4 2
2 1
3 2

5 2
5 2
4 5
2 1
3 1

6 3
6 1
4 2
1 4
5 6
3 6


Sample output:
Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 3
Case #5: 4
Problem: sequence_slicing (2012 round2)

Let **S** be a sequence of **N** natural numbers. We can define an infinite
sequence **MS** in the following way: **MS**[k] = **S**[k mod **N**] + **N** *
floor(k / **N**). Where k is a zero based index.

For example if the sequence **S** is {2, 1, 3} then **MS** would be {2, 1, 3,
5, 4, 6, 8, 7, 9, 11, 10, 12...}

Now consider a subsequence of **MS** generated by picking two random indices
**a**, **b** from the range [**0**..**R**] inclusive, and taking all the
elements between them, that is: **MS**[min(**a**, **b**)..max(**a**, **b**)].

If we use the same **MS** as in the example above and **a** = 2, **b** = 5
then our subsequence would be {3, 5, 4, 6}.

Your task is to calculate the probability that the selected subsequence has at
least **K** distinct elements. **a** and **b** are selected independently and
with a uniform distribution. The result should be printed as a fraction. See
the "Output" section for clarification.

### Input

The first line of the input file contains an integer **T**. This is followed
by **T** test cases, each of which has two lines.

The first line of each test case contains three integers separated by spaces,
**N**, **K**, and **R**.  

The second line contains **N** space separated integers, **S**[0] through
**S**[**N**-1].

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 2,000  
1 ≤ **K** ≤ **R** ≤ 1,000,000,000  
1 ≤ **S**[i] ≤ 100,000

### Output

For each of the test cases numbered in order from 1 to **T**, output "Case
#**i**: " followed by the probability that the selected subsequence of **MS**
has at least **K** distinct elements. The probability should be expressed as a
fraction **p**/**q**, where **p** and **q** represent the numerator and
denominator respectively and are relatively prime (that is they share no
common positive divisors except 1).

If the probability is 0 or 1 output 0/1 or 1/1 respectively.

### Examples

In the first example there are 36 different subsequences to consider. 6 of
them have only a single number, and the remaining 30 have at least 2 different
numbers, so the answer is 5/6.

The second example is similar, but now the sequence looks like {2, 1, 5, 5, 4,
8}. There are 8 subsequences with less than 2 distinct numbers: the six single
number subsequences plus (a=2, b=3) and (a=3, b=2) which both result in {5,5}.
That gives a probability of (36 - 8) / 36 = 7/9.

The third example uses the same sequence as the second example, but now we
want to have subsequences with at least 4 different numbers. All pairs of
indices that have this property are: (0,4), (0, 5), (1, 5), (4, 0), (5, 0),
and (5, 1). Six out of thirty six results in a probability of 1/6.



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


Sample output:
Case #1: 5/6
Case #2: 7/9
Case #3: 1/6
Case #4: 0/1
Case #5: 998005995006/1000002000001
Problem: divisor_function_optimization (2012 round3)

Let **d(N)** be the number of positive divisors of positive integer **N**.
Consider the infinite sequence **x(n) = d(n)a / nb, n = 1, 2, 3, …** where
**a** and **b** are fixed positive integers. It can be shown that this
sequence tends to zero. Hence it attains its maximum. Denote it by **p/q**
where **p** and **q** are co-prime positive integers. Your task is for given
**a** and **b** find **p** and **q** modulo **M = 109+7**. But to keep input
and output small you will be given tuples **(b1; b2; a1; a2; c)** and need to
calculate the sum of **(p mod M)** for all pairs **(a; b)** such that **b1 ≤ b
≤ b2**, **a1 ≤ a ≤ a2** and ** a ≤ c*b**, and the same sum for **q**-values.

### Input

The first line contains a positive integer **T**, the number of test cases.
**T** test cases follow. The only line of each test case contains five space
separated positive integers **b1, b2, a1, a2** and **c**.

### Output

For each of the test cases numbered in order from **1** to **T**, output "Case
#i: " followed by a space separated pair of integers: the sum of **(p mod M)**
for all pairs **(a; b)** mentioned above and the sum of **(q mod M)** for all
such pairs. Note that you need to find the sum of residues not the residue of
sum (see testcase 3 as a reference).

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **b1** ≤ **b2** ≤ 10,000  
1 ≤ **a1** ≤ **a2** ≤ 250,000  
1 ≤ **c** ≤ 25  
in each testcase the total number of pairs **(a; b)** for which the answer
should be calculated does not exceed 100,000  



Sample input:
5
1 1 1 3 10
1 2 1 88 3
1 10 1 50 5
1 1 1 15 15
30 33 1 29 25


Sample output:
Case #1: 1540 37
Case #2: 2377233 1491
Case #3: 75232917907 54682660016
Case #4: 5956707232 7441063226
Case #5: 116 116