hackercupai/hackercup huggingface dataset:
Problem: magic_pairs (2014 round2)

The princess of the kingdom of Hackadia has been kidnapped by an evil dragon.
As always the prince Z.A.Y. is going to try to rescue her. The evil dragon is
keeping the princess prisoner in his deepest dungeon, and the prince has to
solve a puzzle to get her out safely.

There are two straight boards in front of the dungeon, both divided into a
large number of sections. Each section contains a sparkling gemstone. Each
stone has a color. We will denote these colors with numbers.

Let's say these boards **Board1** and **Board2** contain **N** and **M**
sections respectively. Let's call a pair of integers **x**, **y** a magic pair
if they have the following properties:

  1. 0 ≤ **x** < **N**
  2. 0 ≤ **y** < **M**
  3. The set of different colors in **Board1**[0...**x**] equals the set of different colors in **Board2**[0...**y**]

The prince has asked you to find out how many magic pairs exist for the given
two boards, so he can free the princess and become the hero. He will take all
the glory from this, so you will have to make do with points in this
competition as payment for your help.

Since the numbers **N** and **M** might be very large, the colors of the
gemstones will be supplied through a pseudo random generator. This works as
follows:  
**Board1**[0] = **x1**  
**Board2**[0] = **x2**  
**Board1**[**i**] = (**a1** * **Board1**[(**i**-1) % **N**] + **b1** * **Board2**[(**i**-1) % **M**] + **c1**) % **r1**, for 0 < **i** < **N**  
**Board2**[**i**] = (**a2** * **Board1**[(**i**-1) % **N**] + **b2** * **Board2**[(**i**-1) % **M**] + **c2**) % **r2**, for 0 < **i** < **M**  

### 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 integers **N**, **M**  
The second line of each test case contains five integers **x1**, **a1**,
**b1**, **c1**, **r1**  
The third line of each test case contains five integers **x2**, **a2**,
**b2**, **c2**, **r2**  

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the number of magic pairs for the two boards.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N**, **M** ≤ 10^6  
0 ≤ **x1**, **x2**, **a1**, **a2**, **b1**, **b2**, **c1**, **c2** ≤ 10^9  
1 ≤ **r1**, **r2** ≤ 10^9  

### Examples

The first example produces the following boards:  
**Board1** = [0, 3, 2, 0, 4, 2, 1, 3]  
**Board2** = [0, 4, 2, 1, 4, 3]  
There are 3 magic pairs:  
pair(0, 0) ==> (0)  
pair(6, 5) ==> (0, 1, 2, 3, 4)  
pair(7, 5) ==> (0, 1, 2, 3, 4)  



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


Sample output:
Case #1: 3
Case #2: 3
Case #3: 6
Case #4: 10
Case #5: 1
Problem: restaurant_chains (2014 round3)

The kingdom of Hackadia has **N** cities that are connected by **M**
bidirectional roads. Cities are enumerated from **0** to **N - 1**. To attract
tourists, the government has decided to open up some restaurant chains
throughout the kingdom. Each restaurant chain will serve some subset of
cities, and will have exactly one restaurant in each city of the chosen
subset. Thus, each city will have some restaurant chains, and it is possible
to have all possible restaurant chains in some city or not to have any
restaurant chains in some city.

To ensure that tourists do not face a drastic change in the food scenario when
traveling from one city to another, the government has decided that the
following condition must be satisfied for each pair of cities (**u**, **v**) :

_ "the number of restaurant chains open in city **u** but not in city **v**"
plus "the number of restaurant chains open in city **v** but not in city
**u**" should always be equal to the shortest distance between city **u** and
city **v**. _

It is guaranteed that every two cities are connected by some sequence of
bidirectional roads, and the shortest distance between city **u** and city
**v** is the number of roads on the shortest path connecting **u** and **v**.

Your job is to help the government determine the minimal number of restaurant
chains, such that there exist some assignment of the restaurant chains among
the cities that satisfy the above condition. If such assignment is not
possible print **-1**.

### Input

The first line of the input will be the number of test cases **T**.  
Each of the test cases start with a line containing the numbers **N** and
**M**, representing the number of cities and the number of roads respectively.  
The next **M** lines of each testcase contain a pairs of integers,
representing the cities connected by a bidirectional road in Hackadia.  
Each testcase will be followed by an empty line.  

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the minimal number of restaurant chains or **-1**.

### Constraints

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

### Explanation

In the first example, we can have two restaurant chains (named X and Y) and
have chain X serve cities 1 and 2, and have chain Y serve cities 2 and 3.  
In the second example, it is not possible to have such restaurant chain
assignment.  



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

4 5
1 3
3 0
1 2
2 3
0 1

2 1
0 1

6 9
1 5
2 4
2 3
0 3
0 4
2 5
1 3
0 5
1 4

10 9
0 1
0 9
0 3
0 8
0 7
0 6
0 2
0 4
0 5



Sample output:
Case #1: 2
Case #2: -1
Case #3: 1
Case #4: -1
Case #5: 9
Problem: secret_santa (2014 round3)

There are **K** families living in Christmasville. During Christmas they have
this tradition, where each person secretly gets a gift for some other person.
The assignment of who gives gift to whom is generally done by a lottery, but
this time we are writing a program to do it.

The assignment should have the following properties:  
* Each person should give exactly one gift.   
* Each person should receive exactly one gift.   
* A person should not give a gift to someone within the same family.   

Find out how many possible assignments are there, that satisfy above
constraints. Two assignments are considered different, if there exists some
person, who gives gifts to different people in the two assignments. Since this
number may be very large, output this number modulo **1,000,000,007**

### 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 **K**, the number of
families.  
The next line of each test case contains **K** integers, **n1**, **n2**, ...,
**nK**, where **ni** is the number of people in the **i**th family.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the number of valid assignments, modulo 1,000,000,007

### Constraints

1 ≤ ** T ** ≤ 20  
2 ≤ ** K ** ≤ 100  
1 ≤ **ni** ≤ 4  
1 ≤ **n1** \+ **n2** \+ ... + **nK** ≤ 100  



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


Sample output:
Case #1: 1
Case #2: 2
Case #3: 4
Case #4: 80
Case #5: 97344
Problem: lunch_at_facebook (2014 finals)

What's the best thing about working at Facebook? It's hard to say, but the
free food doesn't hurt. Every day there are long lines for food, and sometimes
guests visit the campus, as hungry as everybody else. It pays to be a good
host, so sometimes we'll let guests cut ahead in the line. But obviously
nobody wants to miss out on delicious Facebook food.

Every day, **N** Facebook employees are lined up for lunch, and every day
**M** visitors come to the campus looking for food. Each person has an
appetite **Ai**, which is a positive integer. Curiously, no two people have
the same appetite.

If people with large appetites eat first, there's a concern that the food
might run out before the people at the back get to eat, so it's ideal to have
people with smaller appetites further ahead in the line. With this in mind,
we'd like to squeeze all of the guests into the lunch line as efficiently as
possible.

We define the _unsuitableness_ of a line as the number of pairs of people in
the line, **Pi** and **Pj**, such that **Pi** is ahead of **Pj** in the line,
and **Pi** has a larger appetite than **Pj**. Your task is to find a way to
get all the visitors into the lunch line such that the unsuitableness of the
resulting line is minimized. The employees that are standing in line won't
change order, but you can put guests in any place you want.

### Input

The first line contains an integer **T**, the number of test cases.  
Each test case has three lines:  
A line with **N** and **M**.  
A line with **N** integers, the appetites of the employees in order, beginning
with the first employee.  
A line with **M** integers, the appetites of the visitors.  

### Output

For each test case _i_, output "Case #i: " followed by the minimum possible
unsuitableness of the resulting line.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 105  
1 ≤ **M** ≤ 105  
1 ≤ **Ai** ≤ 109  

### Explanation of Sample

For the first test case the optimal lunch line has the following appetites in
order: 1, 2, 3, 4  
For the second test case the optimal lunch line is: 1, 2, 4, 7, 5, 3  



Sample input:
5
2 2
1 2
3 4
4 2
1 7 5 3
2 4
10 5
9 3 14 13 7 10 12 1 6 8
2 15 5 4 11
10 5
7 9 3 14 10 4 5 1 13 6
2 15 11 8 12
10 5
2 8 10 7 12 5 13 11 4 6
3 9 14 15 1


Sample output:
Case #1: 0
Case #2: 4
Case #3: 35
Case #4: 33
Case #5: 25
Problem: coins_game (2014 round1)

Alice and Bob like to play what they call the "Coins Game". In this game Bob
starts with **K** identical coins and **N** identical jars. A jar can fit any
number of coins and Bob has to distribute all the coins in whatever way he
wants.

After the coins are distributed Alice takes the jars and shuffles them at
random while Bob isn't looking. Alice will move jars around but will not move
any coins between the jars. The jars are opaque so after the shuffle Bob
doesn't see how many coins are in each.

Now Bob has **P** moves. In each move he points at one of the jars. If the jar
contains any coins Alice takes a single coin from it and hands it to Bob. If
the jar is empty Alice tells Bob. Bob remembers his initial distribution and
the moves he has made so far.

The goal of the game is to check whether Bob is able to acquire at least **C**
coins after his **P** moves. If he can do that he wins the game. After losing
the first few games Bob is determined to figure out what's the minimal number
of moves **P** that can guarantee his win. Your job is to help him, that is
find the minimal value **P** for which there exists an initial coins
distribution and moves strategy that makes Bob win no matter what order the
jars are in.

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.  
Each test case is a single line with three integers: **N** **K** **C**

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by an integer **P**, the minimal number of moves for which there
exists a winning strategy.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 1,000,000  
1 ≤ **C** ≤ **K** ≤ 1,000,000  

### Examples

In the first test case we start with three jars and six coins. Bob needs to
get four of them to win. A winning strategy is to put two coins in each jar.
Then he can point twice at one jar and twice at another one to always get four
coins.

In the second example he can put the five coins in a different jar each. In
the worst case he will point at an empty jar three times so he will need five
total moves to get two coins. There is no way to guarantee a win with fewer
than five moves.



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


Sample output:
Case #1: 4
Case #2: 5
Case #3: 5
Case #4: 1
Case #5: 9
Problem: preventing_alzheimers (2014 round1)

It is a truth universally acknowledged that a grandparent in possession of a
good fortune must furnish his or her grandchildren with cash on their
birthdays. Your usual approach is to give each of your **N** grandchildren a
number of dollars equal to their age, (That means 0 dollars for newborns; it's
important that they learn what a rough place the world is from the very
start).

One of your younger, and more precocious, grandchildren, Elly, has read online
that trying out new things is a good way to prevent Alzheimer's. So, out of
concern for your mental well-being (and in the hopes that she might receive
more money), she's posed a new distribution scheme. "If any two grandchildren
compare the size of their presents, they should find that both presents are
divisible by an integer **K**. They should also find that there is no larger
integer that divides the size of both presents," she states.

Well, that seems harmless enough, you think. Of course, each grandchild will
still have to receive at least as much money as they would have under the old
scheme, to avoid any family drama. As you're getting on in years, your
mathematical prowess isn't what it used to be. It would be easier to write a
program that computes the additional drain on your pocketbook.

Note that 0 is divisible by all other numbers.

### 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 with the integers **N** and **K**.  
The next line consists of the ages of your grandchildren as **N** integers
**A1**, **A2**, ..., **AN**.  

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the minimum extra amount of money you would have to spend compared
to giving everyone money equal to their age.

### Constraints

1 ≤ **T** ≤ 20  
2 ≤ **N** ≤ 20  
1 ≤ **K** ≤ 20  
0 ≤ **Ai** ≤ 50  

### Examples

In the first example, you would have to pay 2 to one of them and 3 to the
other. The total cost would be 5. Under the old constraints, both
grandchildren would get 2, for a total sum of 4. The answer is 5-4 = 1. You
can't pay 2 to both, because their gifts would be divisible by 2 as well as 1.

In the second example, a possible solution is to give them 3, 7, 5 and 16
dollars, for a total of 31. Under the old constraints, you would give them a
total of 28. The answer is 31-28 = 3.

In the third example, all gifts have to be divisible by 3. A possible solution
is 6, 21, 51. This is 6 more than the sum of their ages. Note that 6, 18, 51
are all divisible by 3, but 6 and 18 are both divisible by 6 as well, so that
solution is not valid.



Sample input:
5
2 1
2 2
4 1
2 7 5 14
3 3
5 18 49
3 1
1 2 3
4 2
0 0 1 2


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

Al is the proprietor of Al's Awesome and Amazing Amusement Arcade, called
AAAAAA by some, AAaAAA by others, AAAAA by others still, and alternately A5 or
A6 by math majors.

The problem with operating such a spectacular business is managing the line of
people waiting to get in. City by-laws prevent people from loitering on Al's
property, so anybody who wants to experience the wonders Al has in store has
to queue in the parking lot. Not wanting to turn people away, Al is interested
in cramming as many hapless souls into the parking lot as he can. However,
customers are a whiny bunch, and refuse to stand in any queue that makes too
many detours before getting to the entrance.

You can imagine that the parking lot is a grid, with the Arcade's entrance in
the upper-left corner. All queues must begin here. There may be cars in the
parking lot, denoted '#'. Customers refuse to queue on top of cars. All other
cells will contain '.'. Due to customer complaints, all queues must generally
extend only rightwards and downwards. However, Al's clientele is not entirely
unreasonable, so a queue may have a single contiguous section that runs
upwards, or a single contiguous section that runs leftwards, but not both.
Queues only extend in these four directions (i.e., not diagonally).

There is only room for one customer in each empty space. Each pair of
consecutive customers in the queue must stand in adjacent spaces, i.e. there
can't be any gaps in the queue.

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.  
Each test case begins with a line containing two integers, **N** and **M**,
the number of rows and columns in the lot's grid.  
The next **N** lines each contain a string with exactly **M** characters,
where the **i**th line correspond to the **i**th row in the grid.  

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the size of the largest queue starting in the top left corner that
Al can fit into his parking lot.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N**, **M** ≤ 500  
Each character in the grid will be either '.' or '#'.  
The character in the upper left corner will always be '.'  



Sample input:
5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.


Sample output:
Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10
Problem: labelmaker (2014 round1)

David is labelling boxes in a giant warehouse. He has a *lot* of boxes to
label, but unfortunately his labeling machine is broken, so only some of the
letters work. In order to be efficient, David labels the boxes by first using
every possible 1-letter label in alphabetical order, then using every possible
2-letter label in alphabetical order, then every 3-letter label, etc.

For example, suppose only the letters 'D', 'T', and 'Z' work. David would
label the first 15 boxes as follows: D, T, Z, DD, DT, DZ, TD, TT, TZ, ZD, ZT,
ZZ, DDD, DDT, DDZ. The first box is considered box #1, not box #0.

Given a set of working letters **L** on David's labelling machine and a number
**N** of boxes to label, return the label on the last box.

## Input

The first line of the input consists of a single integer **T**, the number of
test cases.  
Each test case consists of the string **L** and the integer **N**, separated
by a space.

## Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the label on the last box.

## Constraints

1 ≤ **T** ≤ 20  
1 ≤ length(**L**) ≤ 25  
**L** will be in alphabetical order, consist of only uppercase letters A-Z, and contain each letter at most once   
1 ≤ **N** ≤ 263-1  
The test cases will be designed so that no label is longer than 50 letters  



Sample input:
5
EHT 34
ABCEFKO 4296473
ACEHKMPRTU 4125383079316
CDEGHIKLOSUWY 8333092520403744490
ADEFHNOPSUVY 3365973428406169086


Sample output:
Case #1: THE
Case #2: FACEBOOK
Case #3: HACKERCUPTEAM
Case #4: WISHESYOUGOODLUCK
Case #5: ANDHOPESYOUHAVEFUN