hackercupai/hackercup huggingface dataset:
Problem: peg_game (2011 quals)

At the arcade, you can play a simple game where a ball is dropped into the top
of the game, from a position of your choosing. There are a number of pegs that
the ball will bounce off of as it drops through the game. Whenever the ball
hits a peg, it will bounce to the left with probability 0.5 and to the right
with probability 0.5. The one exception to this is when it hits a peg on the
far left or right side, in which case it always bounces towards the middle.  
  
When the game was first made, the pegs where arranged in a regular grid.
However, it's an old game, and now some of the pegs are missing. Your goal in
the game is to get the ball to fall out of the bottom of the game in a
specific location. Your task is, given the arrangement of the game, to
determine the optimal place to drop the ball, such that the probability of
getting it to this specific location is maximized.  
  
The image below shows an example of a game with five rows of five columns.
Notice that the top row has five pegs, the next row has four pegs, the next
five, and so on. With five columns, there are four choices to drop the ball
into (indexed from 0). Note that in this example, there are three pegs
missing. The top row is row 0, and the leftmost peg is column 0, so the
coordinates of the missing pegs are (1,1), (2,1) and (3,2). In this example,
the best place to drop the ball is on the far left, in column 0, which gives a
50% chance that it will end in the goal.

    x.x.x.x.x
     x...x.x
    x...x.x.x
     x.x...x
    x.x.x.x.x
     G  
    'x' indicates a peg, '.' indicates empty space.

###  Input

You should first read an integer **N**, the number of test cases. Each of the
next **N** lines will then contain a single test case. Each test case will
start with integers **R** and **C**, the number of rows and columns (**R**
will be odd). Next, an integer **K** will specify the target column. Finally,
an integer **M** will be followed by **M** pairs of integer **ri** and **ci**,
giving the locations of the missing pegs.

### Constraints

  * 1 ≤ **N** ≤ 100
  * 3 ≤ **R**,**C** ≤ 100
  * The top and bottom rows will not have any missing pegs.
  * Other parameters will all be valid, given **R** and **C**

###  Output

For each test case, you should output an integer, the location to drop the
ball into, followed by the probability that the ball will end in columns
**K**, formatted with exactly six digits after the decimal point (round the
last digit, don't truncate).

###  Notes

The input will be designed such that minor rounding errors will not impact the
output (i.e. there will be no ties or near -- up to 1E-9 -- ties, and the
direction of rounding for the output will not be impacted by small errors).



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


Sample output:
Case #1: 0 0.375000
Case #2: 1 1.000000
Case #3: 1 1.000000
Case #4: 0 1.000000
Case #5: 0 0.500000
Problem: double_squares (2011 quals)

A double-square number is an integer **X** which can be expressed as the sum
of two perfect squares. For example, 10 is a double-square because 10 = 32 \+
12. Your task in this problem is, given **X**, determine the number of ways in
which it can be written as the sum of two squares. For example, 10 can only be
written as 32 \+ 12 (we don't count 12 \+ 32 as being different). On the other
hand, 25 can be written as 52 \+ 02 or as 42 \+ 32.  
  

### Input

You should first read an integer **N**, the number of test cases. The next
**N** lines will contain **N** values of **X**.

### Constraints

0 ≤ **X** ≤ 2147483647  
1 ≤ **N** ≤ 100

### Output

For each value of **X**, you should output the number of ways to write **X**
as the sum of two squares.



Sample input:
5
10
25
3
0
1


Sample output:
Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 1
Case #5: 1
Problem: slot_machine_hacker (2011 round1b)

You recently befriended a guy who writes software for slot machines. After
hanging out with him a bit, you notice that he has a penchant for showing off
his knowledge of how the slot machines work. Eventually you get him to
describe for you in precise detail the algorithm used on a particular brand of
machine. The algorithm is as follows:

    int getRandomNumber() {
      secret = (secret * 5402147 + 54321) % 10000001;
      return secret % 1000;
    }

This function returns an integer number in [0, 999]; each digit represents one
of ten symbols that appear on a wheel during a particular machine state.
**secret** is initially set to some nonnegative value unknown to you.

By observing the operation of a machine long enough, you can determine value
of **secret** and thus predict future outcomes. Knowing future outcomes you
would be able to bet in a smart way and win lots of money.

##  Input

The first line of the input contains positive number **T**, the number of test
cases. This is followed by **T** test cases. Each test case consists of a
positive integer **N**, the number of observations you make. Next **N** tokens
are integers from 0 to 999 describing your observations.

##  Output

For each test case, output the next 10 values that would be displayed by the
machine separated by whitespace.  
If the sequence you observed cannot be produced by the machine your friend
described to you, print "Wrong machine" instead.  
If you cannot uniquely determine the next 10 values, print "Not enough
observations" instead.

##  Constraints

**T** = 20  
1 ≤ **N** ≤ 100  
Tokens in the input are no more than 3 characters long and contain only digits
0-9.



Sample input:
5
1 968 
3 767 308 284 
5 78 880 53 698 235 
7 23 786 292 615 259 635 540 
9 862 452 303 558 767 105 911 846 462 


Sample output:
Case #1: Not enough observations
Case #2: 577 428 402 291 252 544 735 545 771 34
Case #3: 762 18 98 703 456 676 621 291 488 332
Case #4: 38 802 434 531 725 594 86 921 607 35
Case #5: Wrong machine
Problem: chess_2 (2011 round1b)

After decades of shadowy demonstrations and delays from the game’s maker,
Chess 2 has finally been released. You waited in line all night to be one of
the first to purchase an example of the hot sequel to the classic original,
and now you are finally getting a chance to open up your new investment and
take a look inside. What you find is slightly puzzling; in addition to the
traditional pieces, the game has been expanded to contain a number of pieces
that are not actually original.  
  
The best-known piece that has been added to the game is the nightrider. The
nightrider can make any number of knight moves in a single direction, i.e.,
its offset from its initial position will be 2***m** in one dimension and
**m** in the other for some nonzero integer **m**. Like other "sliding"
pieces, if one of the knight moves would cause it to take another piece it is
not able to traverse beyond that point  
  
The archbishop is also part of Chess 2. The archbishop can simply make any
move that a knight or bishop could legally make.  
  
The strangest new piece is the kraken. The kraken can move to any square on
the board, regardless of the position of any other pieces, including its own
current position.  
  
You don't feel like reading the manual to learn about how the new pieces fit
into the standard chess opening positions, so instead you place some of the
pieces randomly on the board. The game you’ve decided to play is simply to
count how many pieces on the board are currently being threatened. A piece is
threatened if another piece is able to move into its cell and take it (note
that if the kraken moves into its own cell it does not take itself).  
  

## Input

Your input file will consist of a single integer **N** followed by **N** test
cases. Each case will consist of, all separated by whitespace, an integer
**P** followed by the identities and positions of **P** Chess 2 pieces. Pieces
are described by a single character **C** to denote their type (see
specification below) followed by two integers **R** and **F**, the 1-based
rank and file, respectively, of the piece.  
  
You've decided to ignore the colors of the pieces in this game. The color of
the pieces will not be reflected in the input and so cannot affect your
output.  
  
To make room for the new pieces, the Chess 2 board is a 16 by 16 grid. No
specified pieces will fall outside the board, and no two pieces will occupy
the same position.  
The types of pieces will be specified as follows, and no entries not present
in this table will appear on the board:

Piece

Abbreviation

King

K

Queen

Q

Rook

R

Bishop

B

Knight

N

Nightrider

S

Archbishop

A

Kraken

E

  
  

## Output

Output a single integer, the number of threatened pieces on the board, for
each test case separated by whitespace.  
  

## Constraints

**N** = 20  
3 ≤ **P** ≤ 64  
1 ≤ **R, F** ≤ 16  
**C** will be one of {K, Q, R, B, N, S, A, E} 



Sample input:
5
4
Q 1 1
B 3 1
B 5 1
B 1 4

3
S 1 1
K 2 3
S 3 5

4
N 1 1
B 3 3
Q 5 5
N 4 1

5
R 2 2
N 1 2
N 2 1
N 16 2
N 2 16

6
Q 1 1
Q 2 3
Q 3 5
Q 4 2
Q 5 4
E 1 5



Sample output:
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 4
Case #5: 6
Problem: scotts_new_trick (2011 round2)

Little Scott recently learned how to perform arithmetic operations modulo some
prime number **P**. As a training set he picked two sequences **a** of length
**N** and **b** of length **M**, generated in the following way:

a1=A1  
a2=A2  
ai=(ai-2 * A3 + ai-1*A4 + A5) mod P, for i=3...**N**  
b1=B1  
b2=B2  
bj=(bj-2 * B3 + bj-1 * B4 + B5) mod P, for j=3...**M**  

Now he wants to find the number of pairs (i, j), where 1 ≤ i ≤ **N** and 1 ≤ j
≤ **M**, such that (ai * bj) mod **P** < **L**, for given number **L**. He
asked you to do the same to help him check his answers.

## Input

The first line of input file consists of a single number **T**, the number of
test cases. Each test consists of three lines. The first line of a test case
contains two integers: prime number **P** and positive integer **L**. The
second line consists of six non-negative integers **N**, **A1**, **A2**,
**A3**, **A4**, **A5**. Likewise, the third line contains six non-negative
integers **M**, **B1**, **B2**, **B3**, **B4**, **B5**.

## Output

Output **T** lines, with the answer to each test case on a single line.

## Constraints

**T** = 20  
2 ≤ **P** < 250,000  
**P** is prime   
1 ≤ **L** ≤ **P**  
2 ≤ **N**, **M** ≤ 10,000,000  
0 ≤ **A1**, **A2**, **A3**, **A4**, **A5**, **B1**, **B2**, **B3**, **B4**,
**B5** < **P**  



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


Sample output:
Case #1: 6
Case #2: 10
Case #3: 15
Case #4: 3
Case #5: 9
Problem: bonus_assignments (2011 round2)

You are in charge of a group of **N** workers, and you want to pay a one-time
bonus to each of them. The bonus for each worker is an integer number of
dollars. According to state law the bonus of the worker who gets the least
should be no less than **A**, but no more than **B**. To motivate your staff,
the bonus of the worker who gets the most should be no less than **C** and no
more than **D**.

Workers tend to spend their entire bonuses on HackerCola. Each of them buys
bottles of HackerCola until he runs out of money, i.e., until amount of money
left is less than the price of one bottle. Workers are very individualistic
and each of them uses his own money only, so they never pool to buy
HackerCola. Unfortunately you don't remember the price of one bottle of
HackerCola, but you are pretty sure that it is an integer number of dollars
greater than 1.

Since you care about the working class you want to assign bonuses to workers
in such a way that there would be at least one worker who would have some
money left after buying as much HackerCola as possible regardless of the price
of the bottle. Calculate the number of possible bonus assignments that fit
this constraint. Two bonus assignments are different if at least one worker
gets different bonus in each assignment. Since the answer can be large,
calculate it modulo 1,000,000,007.

## Input

The first line of the input contains one integer **T**, the number of test
cases. Each of the next **T** lines consists of 5 integers separated by
spaces: **N**, **A**, **B**, **C** and **D**.

## Output

For each of the test cases print a line containing number of possible bonus
assignments modulo 1,000,000,007.

## Constraints

**T** = 20  
1 ≤ **N** ≤ 106  
1 ≤ **A** ≤ **B** ≤ 106  
1 ≤ **C** ≤ **D** ≤ 106



Sample input:
5
2 1 2 4 5
2 2 4 3 5
1 5 10 5 10
5 5 7 2 3
5 2 7 5 12


Sample output:
Case #1: 6
Case #2: 10
Case #3: 0
Case #4: 0
Case #5: 149190
Problem: studious_student_ii (2011 round2)

You've decided to make up another string manipulation game instead of paying
attention in class. Starting with a string composed entirely of 'a' and 'b'
characters, you will iteratively apply the following operation:

For a string **s** of length **len**, choose indices **i** and **j**, where
**i** < **j** < **len**. Choose a character **c** that occurs in the substring
which begins at zero-based index **i** of string **s** and extends to the
index **j** (inclusive). Replace all characters in **s** with zero-based index
in [**i**, **j**] with a single instance of **c** to generate **s'**. Set
**s** to be **s'**.

As an example of sequence of operations consider the string 'abba'. Some of
the possible transformations are shown below. The substring being replaced is
enclosed in square brackets.

  1. [abb]a → [aa] → a
  2. a[bba] → [aa] → a
  3. ab[ba] → [abb] → a
  4. a[bb]a → aba

The goal of your game is simple: calculate how many different sequences of
operations you can perform. As this number can be very large, you decide to
calculate it modulo 1,000,000,007. Two sequences of operations are considered
different if they differ in length, or if they differ in at least one
position. Note that the order of operations is a factor. The empty sequence of
operations should be counted as well. Operations can be considered triples of
(**i**, **j**, **c**) as described above, and these are the only values used
when computing whether two operations are the same.

## Input

The first line of the input file contains a single number **N**, the number of
test cases. Each test case is written on a separate line, and contains a
string consisting of letters 'a' and 'b'.

## Output

Output N lines, with the answer to each test case on a single line.

## Constraints

**N** = 20  
1 ≤ **len** ≤ 60  
**s** only contains the lowercase characters 'a' and 'b'. 



Sample input:
5
ab
aba
aabb
ababa
bbbbb


Sample output:
Case #1: 3
Case #2: 13
Case #3: 57
Case #4: 642
Case #5: 120
Problem: wine_tasting (2011 round1a)

A group of Facebook employees just had a very successful product launch. To
celebrate, they have decided to go wine tasting. At the vineyard, they decide
to play a game. One person is given some glasses of wine, each containing a
different wine. Every glass of wine is labelled to indicate the kind of wine
the glass contains. After tasting each of the wines, the labelled glasses are
removed and the same person is given glasses containing the same wines, but
unlabelled. The person then needs to determine which of the unlabelled glasses
contains which wine. Sadly, nobody in the group can tell wines apart, so they
just guess randomly. They will always guess a different type of wine for each
glass. If they get enough right, they win the game. You must find the number
of ways that the person can win, modulo 1051962371.  
  

### Input

The first line of the input is the number of test cases, **N**. The next **N**
lines each contain a test case, which consists of two integers, **G** and
**C**, separated by a single space. **G** is the total number of glasses of
wine and **C** is the minimum number that the person must correctly identify
to win.  
  

### Constraints

  * **N** = 20
  * 1 ≤ **G** ≤ 100
  * 1 ≤ **C** ≤ **G**
  

### Output

For each test case, output a line containing a single integer, the number of
ways that the person can win the game modulo 1051962371.



Sample input:
5
1 1
4 2
5 5
13 10
14 1


Sample output:
Case #1: 1
Case #2: 7
Case #3: 1
Case #4: 651
Case #5: 405146859
Problem: turn_on_the_lights (2011 round1a)

A simple game consists of a grid of **R**x**C** buttons. Each button will be
either lighted, or unlighted. Whenever you push a button, the state of that
button, and its (up to) four neighbors will toggle -- lighted buttons will
become unlighted and unlighted buttons will become lighted. Note that the
neighbors do not 'wrap' and thus a corner button has only two neighbors, while
an edge buttons has three.  
  
In this problem you will be given an initial configuration of the buttons.
Your task is to push the right buttons so that, when you are done, all of the
lights are turned on. If there are multiple ways to do this, you should
determine the minimum number of buttons pushes that it can be done in.

### Input

You will first read an integer **N** the number of test cases. For each test
case, you will read two integers **R** and **C**. This will be followed by
**R** whitespace-separated tokens, each containing **C** characters. A 'X'
indicates a lighted button, while a '.' indicates an unlighted button.

### Constraints

  * **N** = 20
  * 1 ≤ **R**,**C** ≤ 18

### Output

For each test case you should output the minimum number of button presses
required to turn on all the lights. If there is no way to do this, you should
output -1.



Sample input:
5
5 6
XXXXXX
XXX.X.
XXXXXX
X.XXXX
XXXXX.
1 13
..XXXXXXX.X..
11 6
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
.X.XXX
XXXX.X
XXXXXX
XXX.XX
10 13
..XX...X.X.X.
XX..X..X.....
.X...........
X........X...
.....XX..X.X.
.X..XX.......
.X.....X.X...
.X....X......
......XX...X.
..X....X.....
9 3
...
...
...
...
...
..X
...
...
...


Sample output:
Case #1: 14
Case #2: 7
Case #3: 27
Case #4: 65
Case #5: 11
Problem: diversity_number (2011 round1a)

Let's call a sequence of integers a1, a2, ..., aN _almost monotonic_ if first
K elements are non-decreasing sequence and last N-K+1 elements are non-
increasing sequence: a1≤a2≤...≤aK and aK≥aK+1≥...≥aN.

The _diversity number_ of a sequence a1, a2, ..., aN is the number of possible
sequences b1, b2,..., bN for which 0≤bi<ai and all of the numbers b1, b2,...,
bN are different. The diversity number of an empty sequence is 1.

You need to find the sum of the diversity numbers of all almost monotonic
subsequences of a sequence. Since this number can be very large, find it
modulo 1,000,000,007. A subsequence is a sequence that can be obtained from
another sequence by deleting some elements without changing the order of the
remaining elements. Two sequences are considered different if their lengths
differ or there is at least one position at which they differ.

## Input

The first line of the input file consists of a single number **T**, the number
of test cases. Each test case consists of a number **M**, the number of
elements in a sequence, followed by **M** numbers **n**, elements of some
sequence (note that this sequence is not necessarily _almost monotonic_). All
tokens are whitespace-separated

## Constraints

**T** = 20  
1 ≤ **M**, **n** ≤ 100

## Output

Output T lines, with the answer to each test case on a single line.



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


Sample output:
Case #1: 2
Case #2: 5
Case #3: 15
Case #4: 17
Case #5: 80
Problem: safest_place (2011 finals)

While en route to the 295th annual Galactic Dance Party on Risa, you find
yourself unceremoniously yanked out of hyperspace and, according to your
sensors, surrounded by **N** space bombs. Apparently caught in a trap laid out
by some dastardly and unknown enemy, and unable to return to hyperspace, you
must find the safest place in the vicinity to weather the detonation of all
the space bombs. Your unseen opponent has constructed a cube-shaped space
anomaly that you are unable to leave, so your options are limited to points
within that cube.

Before the bombs explode (all simultaneously), you have just enough time to
travel to any integer point in the cube [0, 0, 0]-[1000, 1000, 1000], both
inclusive. You must find the point with the maximum distance to the nearest
bomb, which your captain's intuition tells you will be the safest point.

## Input

The first line of the input file consists of a single number **T**, the number
of test cases. Each test consists of single number **N**, the number of bombs,
followed by **3*N** integers describing the positions of the bombs.

## Output

Output **T** integers, one per test case each on its own line, representing
the square of distance to the nearest bomb from the safest point in the cube.

## Constraints

**T** = 50  
1 ≤ **N** ≤ 200  
All bombs coordinates will be in [0, 1000], both inclusive.



Sample input:
5
5
0 0 0
1000 1000 1000
1000 500 0
0 1000 500
500 0 1000
10
0 0 0
1000 1000 1000
1000 500 0
0 1000 500
500 0 1000
583 583 583
1000 0 500
500 1000 0
0 500 1000
625 0 0
15
0 0 0
1000 1000 1000
1000 500 0
0 1000 500
500 0 1000
583 583 583
1000 0 500
500 1000 0
0 500 1000
625 0 0
0 625 0
0 0 625
1000 1000 375
1000 375 1000
375 1000 1000
20
0 0 0
1000 1000 1000
1000 500 0
0 1000 500
500 0 1000
583 583 583
1000 0 500
500 1000 0
0 500 1000
625 0 0
0 625 0
0 0 625
1000 1000 375
1000 375 1000
375 1000 1000
491 491 84
491 84 491
84 491 491
1000 453 453
453 1000 453
25
0 0 0
1000 1000 1000
1000 500 0
0 1000 500
500 0 1000
583 583 583
1000 0 500
500 1000 0
0 500 1000
625 0 0
0 625 0
0 0 625
1000 1000 375
1000 375 1000
375 1000 1000
491 491 84
491 84 491
84 491 491
1000 453 453
453 1000 453
453 453 1000
891 891 0
891 0 891
0 891 891
1000 109 109


Sample output:
Case #1: 520667
Case #2: 390625
Case #3: 265929
Case #4: 207418
Case #5: 164387