hackercupai/hackercup huggingface dataset:
Problem: cake_cutting (2013 round2)

"Happy birthday to you... Happy birthday to you... Happy birthday to
Grovyle... Happy birthday to you..."

Today is Grovyle's birthday and he is going to invite his friends to his
birthday party. To have an awesome party, each of the attendants should get
one piece of cake. Your job is to help Grovyle invite as many friends as you
can.

However, Grovyle's parents are very mean, and make him use the following rules
when cutting his cake:

* There is only ONE cylindrical cake. 
* Grovyle cuts the cake **N** times, each cut being perpendicular to the surface of the cake. 
* The **i**-th cut is a broken line with **a**[**i**] vertices. 
* The knife is only allowed to intersect the edge of the cylindrical cake at the start and end of the cut. 

What is the maximum number of pieces Grovyle could get?

### Input

The first line contains an integer **T**, **T** ≤ 50, indicating the number of
test cases. Each test case begins with an integer **N**, 1 ≤ **N** ≤ 100,
followed by **N** integers **a**[**i**], 0 ≤ **a**[**i**] < 400, which
indicate the number of vertices in the **i**-th cut.

### Output

For each test case, output "Case #i: " followed by the maximum number of
pieces of cake Grovyle can cut.



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


Sample output:
Case #1: 7
Case #2: 7
Case #3: 10
Case #4: 14
Case #5: 63
Problem: permutations (2013 round2)

In this problem you need to count number of possible permutations **p** of the
first **N** integers, given **N-1** constraints of the form **pi < pj.**

## Input

The first line contains an integer **T**, **T** ≤ 20, followed by **T** test
cases. Each test case begins with an integer **N**, **N** ≤ 1,000, which is
the number of integers in the permutation. The next **N - 1** lines each
contain a single constraint in the following format: "**i** **sign** **j**",
where 0 ≤ **i**, **j** ≤ **N - 1** and **sign** is either "**<**" or "**>**",
which denotes whether the **i**-th element of the permutation should be less
than or greater than the **j**-th element.

It is guaranteed that it is not possible to partition indices into two
disjoint sets A and B such that there is no constraint involving elements from
both A and B.

## Output

For each test case, output one single line with the number of permutations
that satisfy all the constraints, following the output format shown in the
example. The answer may be very large, so you should give the result modulo
**1,000,000,007**.



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


Sample output:
Case #1: 1
Case #2: 1
Case #3: 4
Case #4: 6
Case #5: 1
Problem: roboelection (2013 round2)

In the not so distant future the world is populated by robots and ruled by an
evil robot emperor. Every robot in the world can be identified by a unique
numeric ID, and the list of all the existing robot IDs is easily accessible to
everyone. One day the emperor decided to call for a general election to
preserve an illusion of democracy. He set it up in the following way:

  * \- Every robot can cast at most one vote per round of voting and the votes are anonymous.
  * \- The only option on the ballot is the vote for reelection of the emperor.
  * \- If at least **P** percent of the population cast votes for the emperor he becomes reelected for the next millennium.
  * \- Otherwise the emperor declares the vote void, disassembles **K** robots with the lowest ID numbers (who he finds to be the most rebellious), and then if there are any functional robots left he restarts the whole process.

All the robots are perfectly logical but also rather lazy and prone to
procrastination. That's why after figuring out the plan of the emperor, they
will abstain from voting unless they have to vote to survive the election
(including this round and all later rounds). If they will die whether or not
they vote, they will vote in the hope that the emperor will spare them. (He
won't, because he's evil!).

## Problem

Given **N** \- the initial population size, **K** \- the number of robots
disassembled after an unsuccessful vote and **P** \- the required percentage
of votes.

Compute the number of times the vote will take place.

## Input

The first line contains the number of test cases **T**, where ** 1 ≤ T ≤ 100
**

Each case is a single line with three space-separated integers **N** **K**
**P**

0 < **K** ≤ **N** ≤ 1,000,000,000,000  
0 < **P** ≤ 100

## Output

For test case **i**, numbered from **1** to **T**, output "Case #i: ",
followed by a single integer, the number of times the emperor will have to
call a vote before getting reelected.

## Example

In the first case we have three robots. Two of them are facing disassembly, so
they will vote for the emperor. The third robot will survive even if he
abstains in the first round, so he doesn't vote. But two out of three is not
enough to reach the 75% minimum, so the election proceeds to a second round.
The election ends when the single remaining robot casts a vote for the
emperor.

In the second case again two robots are in immediate danger, but the next two
robots are forced to vote as well, otherwise they would end up in the same
situation as in the first example case. Now with the 4 out of 5 casting the
vote the election successfully ends.



Sample input:
5
3 2 75
5 2 75
75 8 20
30 15 10
1234 7 44


Sample output:
Case #1: 2
Case #2: 1
Case #3: 2
Case #4: 1
Case #5: 60
Problem: name_the_baby (2013 round3)

Jack is blessed with a baby and he and his wife want to name their child. Jack
is a mathematician and his wife is very superstitious. She wants the baby's
name to contain at least one of her ancestors names as a substring. They have
decided that the baby's name should be exactly **L** characters long, and will
only consist of lowercase characters. Jack's wife gives Jack a list of **N**
strings, the names of her ancestors. Jack finds all the name possible names
for his baby and lists them in alphabetical order. He asks you to choose the
**K**th (1-based) name in the list as the name for his child.

## Input

The first line contains **T**, the number of test cases. Each test case begins
with the value of **L** followed by a single integer **K**. The next line
contains a single integer **N** followed by **N** lines, each containing the
name of one of the wife's ancestors.

## Output

For every test case output the name for the child. If no such name exists
print "unnamed baby :(".

## Constraints

1 ≤ **T** ≤ 20  
1 ≤ **L** ≤ 100  
1 ≤ **N** ≤ 100  
1 ≤ length of each string in the list ≤ 100  
1 ≤ **K** ≤ 1018  



Sample input:
5
5 10
2
like
poke
5 100
1
hack
3 5
3
ab
bc
ca
7 100000
4
abcd
bcde
cdef
defg
10 1000000000
5
facebook
hacker
cup
round
three


Sample output:
Case #1: epoke
Case #2: unnamed baby :(
Case #3: abd
Case #4: dzdefgn
Case #5: ajpxcccuph
Problem: digits_war (2013 round3)

There has been a war between the digits in the kingdom of numbers and it is
King Infinity's job to restore balance. In search of peace he came up with a
new number system which only allows those numbers to exist in which:

1\. None of the consecutive digits are at war against each other.

2\. No two digits that have only one digit in between them are at war.

For example, if 4 is at war with 5, then 45, 405, and 574 are all forbidden.

A digit can be at war with itself. You are given a 10 x 10 binary matrix **M**
(0 index based), where **M**[i][j] denotes whether there is a war between
digit i and digit j. If **M**[i][j] = 1 then they are at war and **M**[i][j] =
0 means they are not. **M**[i][j] will always be equal to **M**[j][i].

Your task is to find the count of positive numbers that can exist in this
number system with number of digits ≤ **K**. No number in the number system
can have leading zeroes.

## Limits

1 ≤ **K** ≤ 1018

## Input

Input consists of **T** test cases, with **T** ≤ 25. Each test case begins
with the value of **K** followed by a 10x10 binary matrix.

## Output

For every test case output the result modulo 109 +7



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


Sample output:
Case #1: 517
Case #2: 9
Case #3: 6510
Case #4: 60
Case #5: 187
Problem: minesweeping (2013 finals)

Do you know Minesweeper, the famous video game? The player is initially
presented with a grid of undifferentiated squares. Some randomly selected
squares, unknown to the player, are designated to contain mines. One square
can contain at most one mine.  
  
The game is played by revealing squares of the grid, typically by clicking
them. After that, a digit is revealed in the square, indicating the number of
adjacent squares (under 8-way connectivity, that is, if two squares share
either an edge or a corner, they are considered adjacent) that contain mines.
If this number is zero then the surrounding squares are automatically also
revealed. This process applies recursively and automatically every time a new
square with count zero is revealed.  
  
Now, given a Minesweeper situation, you need to check if it is possible that
such a situation can occur after **exactly** 1 click on the grid. Note that
the game is designed in such a way, that the first clicked square never
contains a mine.  
  

## Input:

The first line contains a single integer **T**, **T** ≤ 20.  
Then **T** test cases follow.  
The first line of each test case contains two integers **n**, **m** which
indicate the size of the grid (**1 ≤ n ≤ 16, 1 ≤ m ≤ 32**).  
**n** lines follow, each line contains **m** characters describing the situation of the grid.  
The meaning of the characters are as follows:  
x: the square is not revealed after the first click  
0 - 8: the number of mines that are adjacent to this square  
  

## Output:

Output a single line containing 'Yes' if the situation is valid after 1 click,
and 'No' otherwise (quotes for clarity).  



Sample input:
5
8 8
xxxxxxxx
1221124x
0000001x
1100011x
x10001xx
x10001xx
x11111xx
xxxxxxxx
8 8
xxxxxxxx
1221124x
0000001x
1100011x
x10001xx
x30001xx
x11111xx
xxxxxxxx
5 5
xxxxx
xxxxx
xx1xx
xxxxx
xxxxx
1 1
0
2 2
5x
xx


Sample output:
Case #1: Yes
Case #2: No
Case #3: Yes
Case #4: Yes
Case #5: No
Problem: archiver (2013 finals)

You are writing a new revolutionary archiver. The archive is essentially a
pair of non-decreasing sequences of integers of equal length **K**:
**0≤x1≤...≤xk** and **0≤y1≤...≤yk**.

The decompression algorithm proceeds as follows:

  1. Sequence **(0,0), (x1,y1), ... (xk,yk), (xk, 0), (0, 0)** defines a polygon **P**
  2. Starting from the point **(0,0)**, increase either **x** or **y** coordinate by 1 without moving outside of **P**. If both moves are available, you should increase y. After each step write **0** to output if incremented **x** or **1** otherwise.
  3. Repeat step 2 until you end up in point **(xk,yk)**.

Example: decompression of sequence **(3,4), (7,6), (7,8)** will produce string
**010101100100111**.

Your task is to write a compression rate calculator, that is given binary
string s find the smallest value of **K** for which there exists archive that
decompresses to s.

## Input

The first line contains a single integer **T**, **T** ≤ 20. **T** test cases
follow, where each test case consists of one binary string with length **≤
1,000,000**.

## Output

Output a single line containing the smallest possible **K**.



Sample input:
5
001
10011
0010101
1110
0110


Sample output:
Case #1: 1
Case #2: 3
Case #3: 1
Case #4: 2
Case #5: 2
Problem: teleports (2013 finals)

Your house has **2 ≤ N ≤ 500,000** distinct rooms. None of the rooms have
doors, but every room has a one way teleport which takes you to a different
room. The same teleport will always go to the same room. You want to make sure
that every room can be reached from every room, via a series of teleports. To
do this, you are allowed to change the destination of some (or all) of the
teleports.

What is the sum of the minimum number of teleports you have to change to
achieve this, over all possible different starting configurations? Two
starting configurations are different if for some room, the outgoing teleport
goes to different rooms in the two configurations.

## Input

The first line contains a single integer **T**, **T** ≤ 20. **T** test cases
follow, where each test case consists of one integer: **N**

## Output

Output one single line with the sum of the minimum number of teleports you
have to change over all possible different starting configurations. Since this
number might be very big, output it modulo **1,000,000,007**



Sample input:
5
2
3
5
10
20


Sample output:
Case #1: 0
Case #2: 6
Case #3: 1720
Case #4: 435035973
Case #5: 93930085
Problem: colored_trees (2013 finals)

You are given two integers **N** and **K**, 1 ≤ **N** ≤ 1000, 1 ≤ **K** ≤ 109.
Your task is to calculate how many distinct trees with **N** vertices there
are with each vertex colored with one of **K** colors. Multiple vertices can
have the same color, and not all colors need to be used. Two trees t1 and t2
are considered identical if there exists a bijective function f from vertices
of t1 to vertices of t2 such that each vertex x in t1 is colored the same as
f(x) in t2 and each pair of vertices x, y in t1 is connected by an edge if and
only if f(x) and f(y) are connected by an edge in t2. A bijective function is
a function that is both one-to-one and onto, meaning that f(x) = f(y) if and
only if x = y, and for every vertex y in t2, there exists x in t1, such that
f(x) = y.

## Input

The first line contains a single integer **T**, **T** ≤ 20. **T** test cases
follow, where each test case consists of two integers: **N** and **K**.

## Output

Output one single line with the number of colored trees. Since this number
might be very big, output it modulo **1,000,000,007**.

## Examples

![](https://fbcdn-dragon-a.akamaihd.net/cfs-ak-
ash3/676523/506/293813004081038_-/tmp-/IV3SsS)



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


Sample output:
Case #1: 1
Case #2: 55
Case #3: 2
Case #4: 6
Case #5: 96237
Problem: dead_pixels (2013 round1)

John's friend Peter purchases a new high resolution monitor with dimension
**W** * **H** where **W** is the number of pixels in each row (i.e. width) and
**H** is the number of pixels in each column (i.e. height).

However, there are **N** dead pixels on the monitor. The **i**-th dead pixel
is located at (**x**[**i**], **y**[**i**]). (0, 0) is the top-left pixel and
(**W** \- 1, **H** \- 1) is the bottom-right pixel. The locations of the dead
pixels could be generated by 6 given integers **X**, **Y**, **a**, **b**,
**c** and **d** by the following rules. If 2 pixels are at the same location,
they are considered the same. It is possible that there are less than **N**
**distinct** dead pixels.

* **x**[0] = **X**
* **y**[0] = **Y**
* **x**[**i**] = (**x**[**i** \- 1] * **a** \+ **y**[**i** \- 1] * **b** \+ 1) % **W** (for 0 < **i** < **N**)
* **y**[**i**] = (**x**[**i** \- 1] * **c** \+ **y**[**i** \- 1] * **d** \+ 1) % **H** (for 0 < **i** < **N**)

Peter connects his monitor to his computer and opens an image with dimension
**P** (width) * **Q** (height). How many unique positions can the image be
placed so that it can be displayed perfectly (i.e. all pixels of the picture
are shown on the monitor)? The image cannot be rotated.

### Input

The first line contains an integer **T**, which is the number of test cases.
Then **T** test cases follow. Each test case contains 11 integers **W**,
**H**, **P**, **Q**, **N**, **X**, **Y**, **a**, **b**, **c**, **d**.

### Output

For each of the test cases numbered in order from 1 to **T**, output "Case #",
followed by the case number (with 1 being the first test case), followed by ":
", followed by an integer which is the number of different possible positions
for the poster.

### Constraints

* 1 ≤ **T** ≤ 20
* 1 ≤ **W**, **H** ≤ 40 000
* 1 ≤ **P** ≤ **W**
* 1 ≤ **Q** ≤ **H**
* 1 ≤ **N** ≤ min(1 000 000, **W** * **H**)
* 1 ≤ **a**, **b**, **c**, **d** ≤ **100**
* 0 ≤ ** X ** < ** W **
* 0 ≤ ** Y ** < ** H **



Sample input:
5
4 4 2 2 1 0 2 1 2 3 4
4 4 1 1 3 1 1 2 2 2 2
6 10 3 2 2 0 0 5 4 3 2
16 18 5 1 5 10 8 21 27 29 87
14 15 12 4 4 3 5 84 74 53 68


Sample output:
Case #1: 7
Case #2: 15
Case #3: 32
Case #4: 197
Case #5: 16
Problem: card_game (2013 round1)

John is playing a game with his friends. The game's rules are as follows:
There is deck of **N** cards from which each person is dealt a hand of **K**
cards. Each card has an integer value representing its strength. A hand's
strength is determined by the value of the highest card in the hand. The
person with the strongest hand wins the round. Bets are placed before each
player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when
the strength of his hand is higher than the average hand strength. Hence John
wants to calculate the average strength of ALL possible sets of hands. John is
very good at division, but he needs your help in calculating the sum of the
strengths of all possible hands.

## Problem

You are given an array **a** with **N ≤ 10,000** different integer numbers and
a number, **K**, where **1 ≤ K ≤ N**. For all possible subsets of **a** of
size **K** find the sum of their maximal elements modulo **1,000,000,007**.

## Input

The first line contains the number of test cases **T**, where ** 1 ≤ T ≤ 25 **

Each case begins with a line containing integers **N** and **K**. The next
line contains **N** space-separated numbers **0 ≤ a [i] ≤ 2,000,000,000**,
which describe the array **a**.

## Output

For test case **i**, numbered from **1** to **T**, output "Case #i: ",
followed by a single integer, the sum of maximal elements for all subsets of
size **K** modulo 1,000,000,007.

## Example

For **a = [3, 6, 2, 8]** and **N = 4** and **K = 3**, the maximal numbers
among all triples are **6, 8, 8, 8** and the sum is **30**.



Sample input:
5
4 3
3 6 2 8 
5 2
10 20 30 40 50 
6 4
0 1 2 3 5 8 
2 2
1069 1122 
10 5
10386 10257 10432 10087 10381 10035 10167 10206 10347 10088 


Sample output:
Case #1: 30
Case #2: 400
Case #3: 103
Case #4: 1122
Case #5: 2621483
Problem: security (2013 round1)

You are designing a new encryption system that works in the following way:

For server-client communication you need a key **k**, composed of **m**
sections, each of length **l**, and the key consists only of lowercase
characters in the set {a, b, c, d, e, f}. The server has a key **k1** and the
client has a key **k2** where:

  * k1 = f(k). **f** is a function that receives a key and replace some random letters by ? indicating that those characters can be any lowercase letter of the set described before.
  * k2 = f(g(k)). **g** is a function that takes a key and produces a random permutation of its m sections. And **f** is the function defined above.

For example: let m = 3, l = 2

  * f('abacbc') = '?ba??c'
  * g('abacbc') = 'acbcab' (each section was moved one place to the left).

Your task is given **k1** and **k2**, find key **k**. If there are several
solutions, print the lexicographically smallest key. And if there is no
solution at all, print "IMPOSSIBLE" (without the quotes).

## Input description:

The first line has a single integer **T**, which corresponds to the number of
test cases. **T** test cases follows: the first line of the test case
corresponds to the integer **m**, the second line contains the string **k1**
and the third line contains the string **k2**.

## Constraints:

  * T ≤ 20
  * 0 < |k1| ≤ 100
  * 0 < m ≤ 50
  * |k2| = |k1|
  * It is guaranteed that m is always a divisor of |k1|
  * k1 and k2 consist of {a, b, c, d, e, f, ?}

## Output description:

For test case **i**, numbered from **1** to **T**, output "Case #i: ",
followed by the lexicographically smallest key or "IMPOSSIBLE".



Sample input:
5
2
abcd
c?ab
3
ab?c?c
ac?c??
3
ab?c?c
aabbdd
2
aa
bb
2
abcd
cdab


Sample output:
Case #1: abcd
Case #2: abacac
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: abcd
Problem: studious_student (2011 quals)

You've been given a list of words to study and memorize. Being a diligent
student of language and the arts, you've decided to not study them at all and
instead make up pointless games based on them. One game you've come up with is
to see how you can concatenate the words to generate the lexicographically
lowest possible string.  
  

### Input

As input for playing this game you will receive a text file containing an
integer **N**, the number of word sets you need to play your game against.
This will be followed by **N** word sets, each starting with an integer **M**,
the number of words in the set, followed by **M** words. All tokens in the
input will be separated by some whitespace and, aside from **N** and **M**,
will consist entirely of lowercase letters.  
  

### Output

Your submission should contain the lexicographically shortest strings for each
corresponding word set, one per line and in order.  
  

### Constraints

1 ≤ **N** ≤ 100  
1 ≤ **M** ≤ 9  
1 ≤ all word lengths ≤ 10  



Sample input:
5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi


Sample output:
Case #1: cupfacebookforhackerstudentsstudious
Case #2: duzklvrawqrc
Case #3: dyroiymybeaxeyubxzdr
Case #4: bwjibwjibwjijp
Case #5: dcyihopjijliuiuy