hackercupai/hackercup huggingface dataset:
Problem: unfriending (2012 round3)

It's time to clean up your friends list after friending too many people on
Facebook over the winter. The set of your friends' user ids is **F** =
{**x0**, **x1**, ..., **xn-1**}. Each friend from **F** is on zero or more
friend lists that you use to organize your friends. There are **M** friend
lists, **c0**, **c1**, ..., **cm-1**. You can unfriend (remove from **F**)
some of your friends, but because you want to stay in touch with people, you
can only unfriend one person from each friend list. You may also choose not to
unfriend anyone from friend list. Any friend that isn't on a friend list
cannot be unfriended.

Your goal is to find the maximum possible distance between the two friends
whose user ids are the closest after you are done unfriending people. The
distance between user id **x** and user id **y** is defined as
abs(**x**-**y**).

### Input

The first line contains a positive integer **T**, the number of test cases.
**T** test cases follow.

The first line of each test case contains the number of friends **N**, and
number of friend lists **M**, separated by a space. The second line contains
**x0** and integer parameters **a**, **b**, and **p**, separated by spaces.
You must use these to generate the remaining numbers **x1**, …, **xn-1**
according to this formula:

> **xi** = (**xi-1** * **a** \+ **b**) mod **p**

The next M lines of each test case define the friend lists for that test case.
Each line consists of the following integers, separated by spaces: **size**,
**y0**, **a**, **b**. The **size** is the number of friends in the friend
list. **y0** is the index in F of the first friend in the list. You must
generate the remaining friends in the friend list **y1**, …, **yn-1**
according to the following formula:

> **yi** = (**yi-1** * **a** \+ **b**) mod **n**

If a friend list contains more than one of a given index, consider it to only
contain that index once.

## Constraints

1 ≤ **T** ≤ 20  
2 ≤ **n** ≤ 50 000  
0 ≤ **m** ≤ 1 500  
0 ≤ sum of sizes of all friend lists ≤ 1 000 000  
**Numbers used in generators:**  
0 < **a**, **p** < 230  
0 ≤ **b** < 230

### Output

For each of the test cases numbered in order from **1** to **T**, output "Case
#", followed by the case number, followed by ": ", followed by the maximum
possible distance between the two closest user ids that you are still friends
with for that case.



Sample input:
5
9 2
48071530 715583197 479567108 1050406
2 6 743132951 85415827
2 3 376850600 968665455

11 3
787260730 352556659 382266931 1057730
2 9 734333632 693274928
4 2 109921566 4305285
2 6 677574083 984173544

10 3
395307869 893188066 853669149 1056195
4 7 225271526 816658669
4 0 131869161 339696459
4 7 709635520 662395613

12 3
796525811 590453825 261103276 1050505
3 9 594759110 714784928
3 5 431449006 621243801
3 10 638845242 279357772

12 2
609821186 802201942 33450613 1048819
4 3 988115593 116841583
4 0 327812052 590896542


Sample output:
Case #1: 7392
Case #2: 5130
Case #3: 15318
Case #4: 63175
Case #5: 5814
Problem: possible_medians (2012 finals)

For this problem, a _possible median_ is defined as: The median value of a set
containing an odd number of values. -or- One of all the integers between, but
not including, the two median values of a set containing an even number of
values.  
**Examples:** 3 is the only possible median of the set (1, 5, 3, 2, 4). 2, 3 and 4 are all of the possible median values for the set (5, 1). There are **no** possible median values for the set (1, 2, 3, 4), since there are no integers between 2 and 3. 

You are given an array **A** of **N** unique nonnegative integers, all of
which are < **N** (i.e. a permutation of the numbers 0...**N-1**), where 3 ≤
**N** ≤ 200,000. You are also given a length **L** (1 ≤ **L** ≤ **N**).
Additionally, you are given **Q** (1 ≤ **Q** ≤ 200,000) queries, each
containing a number **x** (0 ≤ **x** < N) and two indices **i** and **j** (0 ≤
**i** < **j** ≤ **N**).

Each query returns TRUE if and only if there exists at least one subrange, of
at least **L** elements, of the range **A[i]**...**A[j-1]** (where the array
indices start at 0), with **x** as a possible median. In other words, the
answer is TRUE precisely when there exist **a**, **b** with **i** ≤ **a** <
**b** < **j** with **b** \- **a** ≥ **L** \- 1 and with **A[a]**...**A[b]**
having **x** as a possible median.

You wish to determine the number of queries which will return TRUE.

### Input

The first line contains a positive integer **T** (1 ≤ **T** ≤ 20), the number
of test cases. **T** test cases follow.

The first line of each test case consists of a single integer, **N**. The next
line consists of **N** space-separated integers, the **A[i]**. The line after
that contains two space-separate d integers, **L** and **Q**.

Each of the remaining **Q** lines in the test case contains three space-
separated integers, **x**, **i** and **j**.

These inputs are all integers, and will be input in decimal form, with no
leading zeros, and no decimal points.

### Output

For each of the test cases numbered in order from 1 to T, output "Case #",
followed by the case number, followed by ": ", followed by a single integer,
the number of passing queries.

These outputs are all integers, and must be output in decimal form, with no
leading zeros, and no decimal points.



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


Sample output:
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 1
Case #5: 1
Problem: maximal_multiplicative_order (2012 finals)

Let's start with some notations and definitions. Let **m** be the fixed
positive integer.

  1. Let **a** be an integer that coprime to **m**, that is, **gcd(a, m) = 1**. The minimal positive integer **k** such that **m** divides **ak − 1** is called the _multiplicative order of **a** modulo **m**_ and denoted as **ordm(a)**. For example, ** ord7(2) = 3** since **23 − 1 = 7** is divisible by **7** but **21 − 1** and **22 − 1** are not. It can be proven that **ordm(a)** exists for every **a** that coprime to **m**. 
  2. Denote by **L(m)** the maximal possible multiplicative order of some number modulo **m**. That is, **L(m) = max{ordm(a) : 1 ≤ a ≤ m, gcd(a, m)=1}**. For example, 

**L(5) = max{ ord5(1), ord5(2), ord5(3), ord5(4)} = max{1, 4, 4, 2} = 4**

and

**L(6) = max{ord6(1), ord6(5)} = max{1, 2} = 2.**

  3. Denote by **N(m)** the number of positive integers **a ≤ m** such that ** ordm(a) = L(m)**. For example, **N(5) = 2**, **N(6) = 1**, **N(8) = 3** (numbers that have maximal multiplicative order modulo **8** are **3, 5** and **7**). 

Now your task is to find for the given positive integers **L** and **R** such
that **L ≤ R** the product

**N(L) ∙ N(L+1) ∙ ... ∙ N(R)**

modulo **109 \+ 7**.

### 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 two space
separated positive integers **L** and **R**.

### Output

For each of the test cases numbered in order from **1** to **T**, output "Case
#i: " followed by the value of required product modulo **109 \+ 7**.

### Constraints

**1 ≤ T ≤ 20  
1 ≤ L ≤ R ≤ 1012  
R − L ≤ 500000**  



Sample input:
5
5 8
1 10
1 100
1234 1234
1000000007 1000000007


Sample output:
Case #1: 12
Case #2: 48
Case #3: 451289786
Case #4: 240
Case #5: 500000002
Problem: checkpoint (2012 round1)

You are racing on a 2D lattice grid starting from the origin (0,0) towards a
goal (M,N) where M and N are positive integers such that **0< M ≤ N**. There
is a checkpoint that's neither on the origin nor on the goal with coordinates
(m,n) such that **0 ≤ m ≤ M** and **0 ≤ n ≤ N**. You must clear the checkpoint
before you reach the goal. The shortest path takes **T = M + N** steps.

At each point, you can move to the four immediate neighbors at a fixed speed,
but since you don't want to lose the race, you are only going to take either a
step to the right or to the top.

Even though there are many ways to reach the goal while clearing the
checkpoint, the race is completely pointless since it is relatively easy to
figure out the shortest route. To make the race more interesting, we change
the rules. ** Instead of racing to the same goal **(M,N)**, the racers get to
pick a goal **(x,y)** and place the checkpoint to their liking so that there
are exactly **S** distinct shortest paths. **

For example, given **S = 4**, consider the following two goal and checkpoint
configurations

* **Placing the checkpoint at (1, 3) and the goal at (2,3). ** There are 4 ways to get from the origin to the checkpoint depending on when you move to the right. Once you are at the checkpoint, there is only one way to reach the goal with minimal number of steps. This gives a total of 4 distinct shortest paths, and takes **T = 2 + 3 = 5** steps. However, you can do better. 
* **Placing the checkpoint at (1, 1) and the goal at (2,2). ** There are two ways to get from the origin to the checkpoint depending on whether you move to the right first or later. Similarly, there are two ways to get to the goal, which gives a total of 4 distinct shortest paths. This time, you only need **T = 2 + 2 = 4** steps. 

As a Hacker Cup racer, you want to figure out how to place the checkpoint and
the goal so that you cannot possibly lose. **Given S, find the smallest
possible T, over all possible checkpoint and goal configurations, such that
there are exactly S distinct shortest paths clearing the checkpoint.**

### Input

As input for the race you will receive a text file containing an integer
**R**, the number of races you will participate in. This will be followed by
**R** lines, each describing a race by a single number **S**.  
  

### Output

Your submission should contain the smallest possible length of the shortest
path, **T** for each corresponding race, one per line and in order.  
  

### Constraints

5 ≤ **R** ≤ 20  
1 ≤ **S** ≤ 10,000,000  



Sample input:
5
4
5
12
14
1


Sample output:
Case #1: 4
Case #2: 6
Case #3: 6
Case #4: 9
Case #5: 2
Problem: recover_the_sequence (2012 round1)

Merge sort is one of the classic sorting algorithms. It divides the input
array into two halves, recursively sorts each half, then merges the two sorted
halves.

In this problem merge sort is used to sort an array of integers in ascending
order. The exact behavior is given by the following pseudo-code:

    function merge_sort(arr):
        n = arr.length()
        if n <= 1:
            return arr
        // arr is indexed 0 through n-1, inclusive
        mid = floor(n/2)
        first_half = merge_sort(arr[0..mid-1])
        second_half = merge_sort(arr[mid..n-1])
        return merge(first_half, second_half)
    function merge(arr1, arr2):
        result = []
        while arr1.length() > 0 and arr2.length() > 0:
            if arr1[0] < arr2[0]:
                print '1' // for debugging
                result.append(arr1[0])
                arr1.remove_first()
            else:
                print '2' // for debugging
                result.append(arr2[0])
                arr2.remove_first()
        result.append(arr1)
        result.append(arr2)
        return result

A very important permutation of the integers 1 through **N** was lost to a
hard drive failure. Luckily, that sequence had been sorted by the above
algorithm and the debug sequence of 1s and 2s was recorded on a different
disk. You will be given the length **N** of the original sequence, and the
debug sequence. Recover the original sequence of integers.

### 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 the length of the original sequence, **N**. The second line
contains a string of 1s and 2s, the debug sequence produced by merge sort
while sorting the original sequence. Lines are separated using Unix-style
("\n") line endings.

### Output

To avoid having to upload the entire original sequence, output an integer
checksum of the original sequence, calculated by the following algorithm:

    function checksum(arr):
        result = 1
        for i=0 to arr.length()-1:
            result = (31 * result + arr[i]) mod 1000003
        return result

### Constraints

5 ≤ **T** ≤ 20  
2 ≤ N ≤ 10,000

### Examples

In the first example, N is 2 and the debug sequence is `1`. The original
sequence was 1 2 or 2 1. The debug sequence tells us that the first number was
smaller than the second so we know the sequence was 1 2. The checksum is 994.

In the second example, N is 2 and the debug sequence is `2`. This time the
original sequence is 2 1.

In the third example, N is 4 and the debug sequence is `12212`. The original
sequence is 2 4 3 1.



Sample input:
5
2
1
2
2
4
12212
5
1122211
10
121221212111122121212


Sample output:
Case #1: 994
Case #2: 1024
Case #3: 987041
Case #4: 570316
Case #5: 940812
Problem: squished_status (2012 round1)

Some engineers got tired of dealing with all the different ways of encoding
status messages, so they decided to invent their own. In their new scheme, an
encoded status message consists of a sequence of integers representing the
characters in the message, separated by spaces. Each integer is between 1 and
**M**, inclusive. The integers do not have leading zeroes. Unfortunately they
decided to compress the encoded status messages by removing all the spaces!

Your task is to figure out how many different encoded status messages a given
compressed status message could have originally been. Because this number can
be very large, you should return the answer modulo 4207849484 (0xfaceb00c in
hex).

For example, if the compressed status message is "12" it might have originally
been "1 2", or it might have originally been "12". The compressed status
messages are between 1 and 1000 characters long, inclusive. Due to database
corruption, a compressed status may contain sequences of digits that could not
result from removing the spaces in an encoded status message.

### Input

The input begins with a single integer, **N**, the number of compressed status
messages you must analyze. This will be followed by **N** compressed status
messages, each consisting of an integer **M**, the highest character code for
that database, then the compressed status message, which will be a string of
digits each in the range '0' to '9', inclusive. All tokens in the input will
be separated by some whitespace.

### Output

For each of the test cases numbered in order from 1 to **N**, output "Case
#**i**: " followed by a single integer containing the number of different
encoded status messages that could be represented by the corresponding
compressed sequence modulo 4207849484. If none are possible, output a 0.

### Constraints

5 ≤ **N** ≤ 25  
2 ≤ **M** ≤ 255  
1 ≤ length of encoded status ≤ 1000



Sample input:
5
12
12
255
219
30
1234321
2
101
70 8675309


Sample output:
Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 0
Case #5: 2
Problem: square_detector (2014 quals)

You want to write an image detection system that is able to recognize
different geometric shapes. In the first version of the system you settled
with just being able to detect filled squares on a grid.

You are given a grid of **N**×**N** square cells. Each cell is either white or
black. Your task is to detect whether all the black cells form a square shape.

### Input

The first line of the input consists of a single number **T**, the number of
test cases.

Each test case starts with a line containing a single integer **N**. Each of
the subsequent **N** lines contain **N** characters. Each character is either
"." symbolizing a white cell, or "#" symbolizing a black cell. Every test case
contains at least one black cell.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by YES or NO depending on whether or not all the black cells form a
completely filled square with edges parallel to the grid of cells.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 20

### Example

Test cases 1 and 5 represent valid squares. Case 2 has an extra cell that is
outside of the square. Case 3 shows a square not filled inside. And case 4 is
a rectangle but not a square.



Sample input:
5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####


Sample output:
Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES
Problem: tennison (2014 quals)

You may be familiar with the works of Alfred, Lord Tennyson, the famous
English poet. In this problem we will concern ourselves with Tennison, the
less famous English tennis player. As you know, tennis is not so much a game
of skill as a game of luck and weather patterns. The goal of tennis is to win
**K** sets before the other player. However, the chance of winning a set is
largely dependent on whether or not there is weather.

Tennison plays best when it's sunny, but sometimes, of course, it rains.
Tennison wins a set with probability **ps** when it's sunny, and with
probability **pr** when it's raining. The chance that there will be sun for
the first set is **pi**. Luckily for Tennison, whenever he wins a set, the
probability that there will be sun increases by **pu** with probability
**pw**. Unfortunately, when Tennison loses a set, the probability of sun
decreases by **pd** with probability **pl**. What is the chance that Tennison
will be successful in his match?

Rain and sun are the only weather conditions, so P(rain) = 1 - P(sun) at all
times. Also, probabilities always stay in the range [0, 1]. If P(sun) would
ever be less than 0, it is instead 0. If it would ever be greater than 1, it
is instead 1.

## Input

Input begins with an integer **T**, the number of tennis matches that Tennison
plays. For each match, there is a line containing an integer **K**, followed
by the probabilities **ps, pr, pi, pu, pw, pd, pl** in that order. All of
these values are given with exactly three places after the decimal point.

## Output

For each match, output "Case #i: " followed by the probability that Tennison
wins the match, rounded to 6 decimal places (quotes for clarity only). It is
guaranteed that the output is unaffected by deviations as large as 10-8.

## Constraints

  * 1 ≤ **T** ≤ 100
  * 1 ≤ **K** ≤ 100
  * 0 ≤ **ps, pr, pi, pu, pw, pd, pl** ≤ 1
  * **ps** > **pr**



Sample input:
5
1 0.800 0.100 0.500 0.500 0.500 0.500 0.500
2 0.600 0.200 0.500 0.100 1.000 0.100 1.000
1 1.000 0.000 1.000 1.000 1.000 1.000 1.000
25 0.984 0.222 0.993 0.336 0.207 0.084 0.478
58 0.472 0.182 0.418 0.097 0.569 0.816 0.711


Sample output:
Case #1: 0.450000
Case #2: 0.352000
Case #3: 1.000000
Case #4: 0.999956
Case #5: 0.000000
Problem: holdem_numbers (2014 round2)

In the game of Hold'em Numbers, 4 players play with a deck of **N** cards,
where each card has a distinct number from the range [1..**N**] on it. Each
player is dealt two cards and the player who has the highest sum of the two
numbers wins. If multiple players have the highest sum, the one of them who
holds the highest card wins. All 8 cards are dealt simultaneously so it's
impossible for two players to have the same card.

After seeing your two cards you can bet $1. If you win the hand you get $4
back but if another player wins you lose your dollar. You can also fold, in
which case you don't win nor lose any money. Your opponents play very
aggressively and they will always bet. After the winner is determined all
cards are reshuffled to play another hand for the total of **H** games. It's
possible you get dealt the same hand more than once.

You want to maximize your winnings and only bet if your expected winnings are
strictly greater than zero. To help yourself you decided to write a program
that for the given deck size and hands you were dealt returns whether you
should bet or fold.

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.  
Each test case starts with a line containing two integers **N** and **H**  
The subsequent **H** lines each contain two integers, **C1** and **C2**, the
cards you were dealt.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by a string of **H** characters. Each character being either "B" if
you should bet, or "F" if should fold. The order of characters corresponds to
the order of hands given in the input.

### Constraints

1 ≤ **T** ≤ 20  
8 ≤ **N** ≤ 100  
1 ≤ **H** ≤ 10000  
1 ≤ **C1**, **C2** ≤ **N**  
**C1** ≠ **C2**

### Examples

In the first three examples we are playing a single hand with a deck of eight
cards. The first case is a clear winner so you should bet. The second case
gives no chance to win and you should fold. Finally the third case gives you
40% chance of winning. This is good enough to make the bet profitable.



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


Sample output:
Case #1: B
Case #2: F
Case #3: B
Case #4: BB
Case #5: FBF
Problem: ski_resort_planning (2014 round2)

Charlotte is a very successful Olympic skier. All the sponsor deals she landed
during her career has made her very rich, so she has decided to retire from
skiing. Charlotte has just bought an entire mountain, and is planning to build
a ski resort there. The mountain has **N** interesting points, numbered 0, 1,
..., **N**-1. Point 0 is the top of the mountain. Point **i** is further down
the mountain than point **j** if **i** > **j**.

For each point **a** > 0, she has decided on a different point **b**, which
has the following property: All paths from the top of the mountain to point
**a** have to go through point **b**, and there is no point **c**, such that
**b** < **c** < **a** and all paths from the top of the mountain to point
**a** go through point **c**. A path can never go up the mountain.

You have been given the task to plan where the slopes go. You can add slopes
directly between any two different interesting points. How many ways can you
lay out the slopes for her resort, while satisfying the conditions above?

Two ways of laying out the slopes, **X** and **Y**, are different if there
exists two interesting points **a** and **b**, such that the slope between
**a** and **b** exists in **X** or **Y**, but not in the other.

You can assume that the skiers will be able to get to a lift from any point,
so you don't have to worry about getting them all the way down for every path.
You have to be able to reach all interesting points from the top.

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.  
Each test case starts with a line containing the integer **N**.  
The next line of each test case contains **N**-1 integers, **A1**, **A2**,
..., **AN-1**, where **Ai** is the lowest interesting point that all paths to
point **i** has to pass through.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the number of ways you can lay out the slopes given the
constraints in the input, modulo 1,000,000,007

### Constraints

1 ≤ ** T ** ≤ 20  
2 ≤ **N** ≤ 5000  
**Ai** < **i** for each of **A1**, **A2**, ..., **AN-1**  

### Examples

The first example has to have the following slopes:

    0 -> 1
    0 -> 2
    1 -> 3

In addition, we can choose whether or not to add the slope

    1 -> 2

The total will be 2; one for adding the slope and one for not adding it.



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


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