hackercupai/hackercup huggingface dataset:
Problem: chess_showdown (2016 round3)

Two chess grandmasters, Andrew and Jacob, are having an epic chess showdown to
determine which of them is the uncontested best player in the world!

The showdown consists of **N** games. In each game, one player plays as White
and the other plays as Black. In the first game, Andrew plays as White. After
each game, the player who loses it chooses which color they'll play as in the
following game. However, the victor of the final game wins the entire
showdown, regardless of the results of the previous games!

In each game, each player may decide to attempt to win or attempt to lose:

  1. If both players play to win, then Andrew wins with probability **Ww** if he plays as White (and loses with probability 1 - **Ww**, as there are no draws at this high level of play). Similarly, he wins with probability **Wb** if he plays as Black. 
  2. If both players play to lose (achieved by tipping over their own king as quickly as possible), then Andrew loses with probability **Lw** if he plays as White, and loses with probability **Lb** if he plays as Black. 
  3. If exactly one player wants to win a game, then he's guaranteed to win it. 

Assuming both players play optimally in an attempt to win the showdown, what
is Andrew's probability of besting Jacob?

### Input

Input begins with an integer **T**, the number of showdowns between Andrew and
Jacob. For each showdown, there is first a line containing the integer **N**,
then a line containing the space-separated values **Ww** and **Wb**, then a
line containing the space-separated values **Lw** and **Lb**. These
probabilities are given with at most 9 decimal places.

### Output

For the **i**th showdown, print a line containing "Case #**i**: " followed by
the probability that Andrew wins the entire showdown. Your output should have
at most 10-6 absolute or relative error.

### Constraints

1 ≤ **T** ≤ 10,000  
1 ≤ **N** ≤ 1,000,000,000  
0 ≤ **Ww**, **Wb**, **Lw**, **Lb** ≤ 1  

### Explanation of Sample

In the first showdown, Andrew plays White and wins the only game with
probability 0.9. In the second showdown, Jacob will throw the first game to
force Andrew to play Black in the second game. Jacob can guarantee a loss in
the first game, and Andrew will win the second game with probability 0.8.



Sample input:
5
1
0.9 0.8
0.0 1.0
2
0.9 0.8
0.0 1.0
2
0.2 0.7
0.8 0.3
3
0.8 0.1
0.6 0.4
1000000000
0.5 0.5
0.12345 0.56789


Sample output:
Case #1: 0.900000000
Case #2: 0.800000000
Case #3: 0.600000000
Case #4: 0.464000000
Case #5: 0.500000000
Problem: boomerang_umbrella (2016 round3)

Uh oh, the weather forecast predicts that a rainstorm will soon break out over
the infinite, 1-dimensional number line you call home!

The forecast is remarkably precise. In fact, it's known that exactly **N**
raindrops will fall, with the **i**th drop striking the number line at
position **Xi** exactly **Ki** seconds after the start of the storm. No two
drops will strike the number line at exactly the same position and time.

You'd like to stop as many of the drops as possible, but you don't exactly
have an umbrella... so your boomerang will have to do. Your plan is as
follows:

  1. Stand at some (possibly non-integral) position A on the number line, and choose some other position B (A ≠ B). 
  2. At some point in time, throw your boomerang from A to B. This point in time can be arbitrarily long before or after the start of the storm (the storm won't start for a while, so you have time to prepare). The boomerang will travel along your chosen line segment at a constant speed of S units per second. 
  3. Make your boomerang spin in place at position B for some non-negative amount of time (which can be arbitrarily large). 
  4. Have your boomerang travel back along the line segment from B to A at the same speed, and catch it as soon as it gets back to position A. 

During the inclusive time interval from when you throw the boomerang to when
you catch it again, if the boomerang is ever at exactly the same position as a
raindrop at exactly the time that it strikes the number line, it will
intercept it... just like an umbrella! What's the maximum number of raindrops
you can intercept in this way with a single throw?

### Input

Input begins with an integer **T**, the number of rainstorms. For each
rainstorm, there is first a line containing the space-separated integers **N**
and **S**. Then, **N** lines follow, the **i**th of which contains the space-
separated integers **Xi** and **Ki**.

### Output

For the **i**th rainstorm, print a line containing "Case #**i**: " followed by
the maximum number of raindrops you can stop.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **N** ≤ 100,000  
1 ≤ **S** ≤ 1,000,000,000  
0 ≤ **Xi**, **Ki** ≤ 1,000,000,000  

### Explanation of Sample

In the first rainstorm, one solution is to stand at X = 99 and let your
boomerang spin at X = 100 until it intercepts all three raindrops that will
fall at that position. In the second rainstorm, one solution is to stand at X
= 50 and throw your boomerang towards X = 100 as soon as the first raindrop
hits it. If you recall your boomerang as soon as it reaches X = 100, it will
hit the second raindrop and be back just in time to hit the third.



Sample input:
5
4 20
100 43
100 21
100 541
101 21
3 10
50 10
100 15
50 20
3 10
50 10
100 15
50 19
7 1
1 1
4 4
3 5
4 6
6 7
6 8
3 11
3 3
33 3
34 1
333 3333333


Sample output:
Case #1: 3
Case #2: 3
Case #3: 2
Case #4: 5
Case #5: 3
Problem: public_transportation (2016 round3)

You live on a circular road, **L** metres in length. Any point on the road can
be referred to by a real number **x** (0 ≤ **x** < **L**), the distance along
the road clockwise from its Northmost point to that point (in metres).

Fortunately for you, this road is served by public transportation! There are
**N** bus stops at distinct, integral points along the road.

Unfortunately for you, due to budget cuts exactly **K** of these **N** stops
will soon be removed. The group of **K** removed stops will be chosen
uniformly at random from the set of all possible groups of **K** stops.

You'd like to calculate the expected distance you'll have to walk from a
random point along the road, chosen uniformly at random from the interval [0,
**L**), to the nearest of the remaining **N** \- **K** bus stops, in metres.

### Input

Input begins with an integer **T**, the number of roads. For each road, there
is first a line containing the space-separated integers **N**, **K**, and
**L**. Then follows a line containing a string of length **L**. This string
consists of only the characters '0' and '1'. There is a bus stop at position
**x** if and only if the (**x** \+ 1)th character of the string is '1'.
Exactly **N** of the characters will be '1'.

### Output

For the **i**th road, print a line containing "Case #**i**: " followed by the
expected distance you'll have to walk from a random point to the nearest bus
stop, in metres. You should output the exact answer modulo (109 \+ 7). That
is, if the exact answer is **a** / **b** (where **a** and **b** are integers),
you should output **a** * **b**-1 mod (109 \+ 7) (where **b**-1 is the modular
inverse of **b** mod (109 \+ 7)).

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N** ≤ 500,000  
0 ≤ **K** < **N**  
1 ≤ **L** ≤ 1,000,000  

### Explanation of Sample

In the first case, the single existing stop will remain untouched. If your
starting position is smaller than 1 or greater than 5, you'll walk clockwise
to it, for a distance of between 0m and 4m. Otherwise, you'll walk
counterclockwise to it, also for a distance of between 0m and 4m. As such,
your expected distance to walk will be 2m.

In the third case, one of the stops will be removed at random. Whichever one
is removed, your situation will be similar to that of the first case - the
distance you'll have to walk will be uniformly distributed between 0m and 4m,
for an expected distance of 2m.

In the fourth case, the exact answer is 3.15 or 63/20, which is 550000007 when
taken modulo (109 \+ 7).



Sample input:
5
1 0 8
01000000
2 0 8
00010001
2 1 8
00010001
3 1 15
000000111000000
5 2 33
100010000001100000000000100000000


Sample output:
Case #1: 2
Case #2: 1
Case #3: 2
Case #4: 550000007
Case #5: 695454554
Problem: laundro_matt (2016 round1)

Matt Laundro is about to engage in his favourite activity — doing laundry!
He's brought **L** indistinguishable loads of laundry to his local laundromat,
which has **N** washing machines and **M** dryers. The **i**th washing machine
takes **Wi** minutes to wash one load of laundry, and each dryer takes **D**
minutes to dry a load of laundry. At any point in time, each machine may only
be processing at most one load of laundry.

As one might expect, Matt wants to wash and then dry each of his **L** loads
of laundry. Each load of laundry will go through the following steps in order:

  1. A non-negative amount of time after Matt arrives at the laundromat, Matt places the load in an unoccupied washing machine **i**
  2. **Wi** minutes later, he removes the load from the washing machine, placing it in a temporary holding basket (which has unlimited space) 
  3. A non-negative amount of time later, he places the load in an unoccupied dryer 
  4. **D** minutes later, he removes the load from the dryer 

Matt can instantaneously add laundry to or remove laundry from a machine. Help
Matt minimize the amount of time (in minutes after he arrives at the
laundromat) after which he can be done drying all **L** loads of laundry!

### Input

Input begins with an integer **T**, the number of times Matt goes to the
laundromat. For each trip to the laundromat, there is first a line containing
the space-separated integers **L**, **N**, **M**, and **D** in that order.
After that is a line containing **N** space-separated integers, the **i**th of
which is **Wi**.

### Output

For the **i**th trip, print a line containing "Case #**i**: " followed by the
minimum time it will take Matt to finish his laundry.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **L** ≤ 1,000,000  
1 ≤ **N** ≤ 100,000  
1 ≤ **M** ≤ 1,000,000,000  
1 ≤ **D** ≤ 1,000,000,000  
1 ≤ **Wi** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, Matt has just one load of laundry. He washes it for 1200
minutes, and dries it for 34 minutes. In the second case, Matt uses the
1-minute washer for both loads of laundry. The second load finishes at the
2-minute mark, so it finishes drying at the 12-minute mark.



Sample input:
5
1 1 1 34
1200
2 3 2 10
100 10 1
3 3 3 3
1 2 3
4 2 2 7
5 8
999 1 999 6
3


Sample output:
Case #1: 1234
Case #2: 12
Case #3: 5
Case #4: 22
Case #5: 3003
Problem: coding_contest (2016 round1)

You've been put in charge of creating the problems for a certain high-profile
programming contest series.

The series will consist of one or more contests of exactly 4 problems each.
Every problem has a difficulty rating (an integer between 1 and 100,
inclusive), and the ratings of the 4 problems in each contest must be strictly
increasing, but with a difference of no more than 10 between consecutive
problems. In other words, if the problems in a contest have difficulties
**a**, **b**, **c**, and **d** (in order), then the inequalities **a** < **b**
< **c** < **d**, **b** \- **a** ≤ 10, **c** \- **b** ≤ 10, **d** \- **c** ≤ 10
must all hold.

You've been given an ordered list of **N** problems to use. Being an
experienced problemsetter, you may also write some new problems to insert at
any positions in the list, each with an integer difficulty between 1 and 100,
inclusive. The final list of problems must still include the original **N**
problems in their original order, though (with your new problems optionally
mixed in).

Once the problem list is finalized, the first 4 problems (in order) will form
a contest, the next 4 problems will form another contest, and so on. Note that
the number of problems in the list must be divisible by 4, and that each of
the contests formed must feature a valid ordered set of 4 problems. What's the
minimum number of additional problems you must write in order to create a set
of valid contests?

### Input

Input begins with an integer **T**, the number of contest series you need to
create. For each series, there is first a line containing the integer **N**,
then a line containing **N** space-separated integers, the **i**th of which is
**Di**, the difficulty rating of the **i**th existing problem.

### Output

For the **i**th series, print a line containing "Case #**i**: " followed by
the minimum number of additional problems you'll need to write.

### Constraints

1 ≤ **T** ≤ 50  
1 ≤ **N** ≤ 100,000  
1 ≤ **Di** ≤ 100  

### Explanation of Sample

In the first series, the four problems given are already a valid contest, so
no new problems need to be written. In the second series, the four existing
problems most certainly do not form a valid contest, due to the gap between
the third and fourth ones - one possible way to salvage the situation is to
add three new problems with difficulties 30, 29, and 30 after the third
problem, as well as a problem with difficulty 42 at the end, creating two
valid contests: [15, 20, 25, 30] and [29, 30, 40, 42].



Sample input:
5
4
10 15 25 30
4
15 20 25 40
3
3 3 3
8
60 90 61 62 63 91 92 93
11
5 14 30 32 39 46 47 47 30 58 47


Sample output:
Case #1: 0
Case #2: 4
Case #3: 9
Case #4: 4
Case #5: 9
Problem: yachtzee (2016 round1)

A rich, retired programmer has decided to invest his (possibly) massive
savings into constructing custom yachts for himself.

Initially, he has a real amount of dollars, chosen uniformly at random from
the range [**A**, **B**]. Constructing a yacht consists of **N** sequential
steps, with the **i**th step requiring **Ci** dollars.

The programmer blindly pays for the steps in order, until he's either
completed all of them, or can't afford the cost of the next step. If the
former occurs, he puts his completed yacht aside and restarts the process from
the first step with his remaining money - he wants as many yachts as possible!
Otherwise, in the latter case, he immediately stops his project entirely,
without spending any additional money on other steps.

What's the expected amount of money which the programmer will be left with
once he stops spending it on yachts? Your output should have at most 10-6
absolute or relative error.

### Input

Input begins with an integer **T**, the number of times the programmer embarks
on a yacht-creation spree. For each spree, there is first a line containing
the space-separated integers **N**, **A**, and **B** in that order, then a
line containing **N** space-separated integers, the **i**th of which is
**Ci**.

### Output

For the **i**th spree, print a line containing "Case #**i**: " followed by the
expected amount of money the programmer will have left.

### Constraints

1 ≤ **T** ≤ 50  
0 ≤ **A** < **B** ≤ 1,000,000,000  
1 ≤ **N** ≤ 100,000  
1 ≤ **Ci** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, the programmer starts with between 5 and 8 dollars. The
programmer's initial amount of money will fall into one of the ranges [5, 6),
or [6, 8), or [8, 8]. If it falls into the first range, the programmer will
end with [1, 2) dollars. If it falls into the second range, the programmer
will end with [0, 2) dollars. If the programmer starts with exactly 8 dollars,
he'll end with 0 dollars.



Sample input:
5
1 5 8
2
1 0 777777777
7
1 777777 7777777
777777777
2 9 20
8 2
5 40 140
4 9 1 12 7


Sample output:
Case #1: 1.166666667
Case #2: 3.500000000
Case #3: 4277777.000000000
Case #4: 3.227272727
Case #5: 4.400000000
Problem: sum_41_ch1 (2023 round1)

*This problem shares some similarities with B2, with key differences in bold.*

Given a positive integer \(P\), please find an array of at most \(100\) positive integers which have a sum of \(41\) and a product of \(P\), or output \(-1\) if no such array exists.

If multiple such arrays exist, **you may output any one of them**.

# Constraints
\(1 \leq T \leq 965\)
\(1 \leq P \leq 10^9\)

# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is one line containing a single integer \(P\).

# Output Format

For the \(i\)th test case, if there is no such array, print "`Case #i: -1`". Otherwise, print "`Case #i:` " followed by the integer \(N\), the size of your array, followed by the array itself as \(N\) more space-separated positive integers.

# Sample Explanation
In the first sample, we must find an array with product \(2023\), and sum \(41\). One possible answer is \([7, 17, 17]\).



Sample input:
7
2023
114
41
175
434
666
1872


Sample output:
Case #1: 3 7 17 17
Case #2: 2 3 38
Case #3: 1 41
Case #4: 3 1 5 35
Case #5: 4 1 2 7 31
Case #6: -1
Case #7: 5 1 2 6 6 26


Solution: Note that using a \(1\) in the output array will contribute to the sum without affecting the product. The problem reduces to finding any factorization \(P = f_1 * ... * f_k\) such that every \(f_i \ge 2\) and \(\sum f_i \le 41\). We can simply pad out the list with \(1\)s until we reach \(41\).

Let's consider the prime factorization of \(P = p_1^{k_1} * p_2^{k_2}  ... p_M^{k_M}\). We claim that if an answer exists, it can always be attained by taking the prime factorization and padding out the rest with \(1\)s.

To see why this is true, note that for any two integers \(a, b > 1\) it's always true that \(a*b \ge a+b\). Since composite factors can only be attained by merging prime factors, the overall sum can only stay the same or increase if we use composite factors. We might as well just use the prime factorization if it sums less than or equal to \(41\) (otherwise the answer does not exist), and then pad with \(1\)s.

The prime factorization can be generated in \(\mathcal{O}(\sqrt P)\), and padding up to \(41\) takes constant time, so the overall running time is \(\mathcal{O}(\sqrt P)\).


Code: #include <iostream>
#include <vector>
using namespace std;

void solve() {
  int P;
  cin >> P;
  int curr_sum = 0;
  vector<int> factors;
  for (int i = 2; i*i <= P; ) {
    if (P % i == 0) {
      factors.push_back(i);
      curr_sum += i;
      P /= i;
    } else {
      i++;
    }
  }
  if (P > 1) {
    curr_sum += P;
    factors.push_back(P);
  }
  if (curr_sum > 41) {
    cout << " -1";
    return;
  }
  while (curr_sum < 41) {
    factors.push_back(1);
    curr_sum++;
  }
  cout << " " << factors.size();
  for (int f : factors) {
    cout << " " << f;
  }
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ":";
    solve();
    cout << endl;
  }
  return 0;
}
Problem: balanced_smileys (2013 quals)

Your friend John uses a lot of emoticons when you talk to him on Messenger. In
addition to being a person who likes to express himself through emoticons, he
hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell
if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

  * \- An empty string ""
  * \- One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
  * \- An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'. 
  * \- A message with balanced parentheses followed by another message with balanced parentheses. 
  * \- A smiley face ":)" or a frowny face ":("

Write a program that determines if there is a way to interpret his message
while leaving the parentheses balanced.

## Input

The first line of the input contains a number **T **(1 ≤ **T** ≤ 50), the
number of test cases.  
The following **T** lines each contain a message of length **s** that you got
from John.

## Output

For each of the test cases numbered in order from 1 to **T**, output "Case #i:
" followed by a string stating whether or not it is possible that the message
had balanced parentheses. If it is, the string should be "YES", else it should
be "NO" (all quotes for clarity only)

## Constraints

  * 1 ≤ length of **s** ≤ 100



Sample input:
5
(:)
i am sick today (:()
)(
hacker cup: started :):)
:((


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

When John was a little kid he didn't have much to do. There was no internet,
no Facebook, and no programs to hack on. So he did the only thing he could...
he evaluated the beauty of strings in a quest to discover the most beautiful
string in the world.

Given a string **s**, little Johnny defined the beauty of the string as the
sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no
two letters have the same beauty. Johnny doesn't care about whether letters
are uppercase or lowercase, so that doesn't affect the beauty of a letter.
(Uppercase 'F' is exactly as beautiful as lowercase 'f', for example.)

You're a student writing a report on the youth of this famous hacker. You
found the string that Johnny considered most beautiful. What is the maximum
possible beauty of this string?

## Input

The input file consists of a single integer **m** followed by **m** lines.

## Output

Your output should consist of, for each test case, a line containing the
string "Case #**x**: **y**" where **x** is the case number (with 1 being the
first case in the input file, 2 being the second, etc.) and **y** is the
maximum beauty for that test case.

## Constraints

5 ≤ **m** ≤ 50**  
2 ≤ length of **s** ≤ 500  



Sample input:
5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves


Sample output:
Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646
Problem: find_the_min (2013 quals)

After sending smileys, John decided to play with arrays. Did you know that
hackers enjoy playing with arrays? John has a zero-based index array, **m**,
which contains **n** non-negative integers. However, only the first **k**
values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index **i**, where **k** ≤ **i** < **n,
m**[**i**] is the minimum non-negative integer which is *not* contained in the
previous ***k*** values of **m**.

For example, if **k** = 3, **n** = 4 and the known values of **m** are [2, 3,
0], he can figure out that **m**[3] = 1.

John is very busy making the world more open and connected, as such, he
doesn't have time to figure out the rest of the array. It is your task to help
him.

Given the first **k** values of **m**, calculate the **n**th value of this
array. (i.e. **m**[**n** \- 1]).

Because the values of **n** and **k** can be very large, we use a pseudo-
random number generator to calculate the first **k** values of **m**. Given
non-negative integers **a**, **b**, **c** and positive integer **r**, the
known values of **m** can be calculated as follows:

  * **m**[0] = **a**
  * **m**[**i**] = (**b** * **m**[**i** \- 1] + **c**) % **r**, 0 < **i** < **k**

### Input

The first line contains an integer **T** (**T** ≤ 20), the number of test
cases.  
This is followed by **T** test cases, consisting of 2 lines each.  
The first line of each test case contains 2 space separated integers, **n**,
**k** (1 ≤ **k** ≤ 105, **k** < **n** ≤109).  
The second line of each test case contains 4 space separated integers **a**,
**b**, **c**, **r** (0 ≤ **a**, **b**, **c** ≤ 109, 1 ≤ **r** ≤ 109).

### Output

For each test case, output a single line containing the case number and the
**n**th element of **m**.



Sample input:
5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46


Sample output:
Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12