# Google Code Jam Archive — Code Jam to I/O for Women 2014 problems

## Overview

This was our first Code Jam to I/O for Women contest. Saturnalia was a simple warm-up problem, Zathras entailed implementing a simulation, and Seating Chart was a more complex exercise in combinatorics. MirandaYang took first place with a perfect score in only 46 minutes! Eight other contestants achieved perfect scores.

## A. Saturnalia

### Problem

It is the eve of Saturnalia in the Roman Empire, and Caterina is preparing the stables for the next day's chariot race. Part of her job is to write instructions and notes, print them on her printer (she's ahead of her time), and put them on the stable walls. That's simple, but because Saturnalia is an important festival, she wants to make them beautiful. Caterina needs a computer program that reads a message and outputs it back, decorated with a box. The program needs to be able to handle many messages at once. Can you help her?

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains a text message.

### Output

For each test case, output four lines. The first one should contain "Case #x:", where x is the test case number (starting from 1). The next 3 lines should contain the original message surrounded by a box of '+', '-', and '|' characters, with a space character added on each side of the message. See examples below for the exact formatting requirements. Pay special attention to the spaces.

### Limits

#### Small dataset (Test set 1 - Visible)

1 ≤ T ≤ 100.
Time limit: 20 seconds.
Memory limit: 1 GB.
Each input line will contain between 1 and 70 characters.
Each character will either be an English letter, a space, or one of the following punctuation characters: ,?!'. (comma, question mark, exclamation point, apostrophe, or period).

### Sample

 Input ```5 Merry Saturnalia, Giovanni! Equus, you're the best! Caballus, you try really hard! w ``` Output ```Case #1: +-----------------------------+ | Merry Saturnalia, Giovanni! | +-----------------------------+ Case #2: +-------------------------+ | Equus, you're the best! | +-------------------------+ Case #3: +--------------------------------+ | Caballus, you try really hard! | +--------------------------------+ Case #4: +-----+ | | +-----+ Case #5: +---+ | w | +---+ ```

Note that the input for Case #4 is a line with 3 space characters on it, so the output is a box with five space characters inside.

## B. Zathras

### Problem

It is year 2025 on planet Zathras -- a world populated exclusively by semi-sentient robots called Zathrinians. There are two kinds of Zathrinians: acrobots and bouncoids. Once a year, the Great Mind makes its Great Decision for that year, and chooses how the Zathrinians will reproduce and be decommissioned. When it's making the Great Decision, it takes into account two Eternal Parameters: α and β. These parameters, being Eternal, do not change from year to year.

Reproduction: If there are A acrobots and B bouncoids when the Great Mind makes the Great Decision, the Great Mind will create K = min(A, B) reproductive pairs by pairing together an acrobot and a bouncoid. Any remaining robots will be unpaired. The next day, 2% of those K couples (rounded down) will produce one baby Zathrinian each.

Out of all the baby Zathrinians produced, α% (rounded down) are acrobots, and β% (rounded down) are bouncoids. The remaining baby Zathrinians are split evenly between acrobots and bouncoids; if there's an odd number, the extra baby becomes a bouncoid.

Decommissioning: When the Great Mind makes its Great Decision, 1% of acrobots (rounded down) and 1% of bouncoids (rounded down) are marked for decommissioning. Two days later, they will all be disassembled. Note that the 1% figure is calculated on the day of the Great Decision, before the new Zathrinians are born.

After the Great Decision has been made (day 1), the reproduction has occurred (day 2), and the unlucky Zathrinians have been disassembled (day 3), the entire world continues to function in harmony until next year's Great Decision takes place at the time scheduled in the Eternal Specification.

### Example

If we start with a population of 12345 acrobots and 12890 bouncoids, 123 acrobots and 128 bouncoids will be marked for decommissioning. The number of couples will be min(12345, 12890), which is 12345. This means that 246 offspring will be created that year. Let's say that α=10 and β=13, so more bouncoids than Zathrinians are created each year. This means that 24 offspring will be acrobots (10% of 246, rounded down); 31 will be bouncoids (13% of 246, rounded down); and the remaining 191 will be split between 95 more acrobots and 96 more bouncoids.

Overall, we started with 12345 acrobots and 12890 bouncoids. One day later, there will be 12464 acrobots and 13017 bouncoids. The next day, there will be 12341 acrobots and 12889 bouncoids. 99 years later, there will be 11993 acrobots and 12676 bouncoids. After a total of 5049 years, we will be down to only 3099 acrobots and 3199 bouncoids -- a huge drop in total population size. After that, the populations will remain the same forever.

Given the values of A, B, α, β, and Y, can you compute the acrobot and bouncoid population sizes at the end of Y years?

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains 5 integers: A, B, α, β, and Y.

### Output

For each test case, output one line containing "Case #x: AY BY", where x is the test case number (starting from 1) and (AY, BY) are the populations of acrobots and bouncoids after Y years, respectively.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
0 ≤ α.
0 ≤ β.
α + β ≤ 100.

0 ≤ A ≤ 20000.
0 ≤ B ≤ 20000.
0 ≤ Y ≤ 100.

0 ≤ A ≤ 106.
0 ≤ B ≤ 106.
0 ≤ Y ≤ 1015.

### Sample

 Input Output ```4 12345 12890 10 13 0 12345 12890 10 13 1 12345 12890 10 13 100 12345 12890 10 13 5049 ``` ```Case #1: 12345 12890 Case #2: 12341 12889 Case #3: 11993 12676 Case #4: 3099 3199 ```

## C. Seating Chart

### Problem

Some people believe that the easiest way to ruin a conference is to do a bad job of planning the seating arrangements. The conference's chairperson, Saanvi, is planning seating for the dinner after the keynote address, with N people, and she wants to manually review all possible seating arrangements in order to pick the absolutely best one. To figure out whether that's feasible, she's planning to write a program to compute the number of possible seating arrangements.

There are K round tables at the dinner, numbered 1 through K. It is important to have exactly the same number of people sitting at each table. If that is impossible (N is not divisible by K), then the table with the most people must have at most one more person sitting at it than the table with the fewest people.

Each of the N people will be assigned a unique number between 0 and N - 1. What matters is who is sitting next to whom, and not exactly where they're sitting. In other words, two arrangements, A and B, are considered different if there exists a pair of numbers, α and β, such that persons α and β are sitting next to each other at the same table in arrangement A, but they are not sitting next to each other in arrangement B.

For example, if N is 5, and K is 2, we must have 3 people seated at one of the tables, and 2 people seated at the other table. Here is the list of all 10 of the possible arrangements:

```[[0, 1, 2], [3, 4]]
[[0, 1, 3], [2, 4]]
[[0, 1, 4], [2, 3]]
[[0, 2, 3], [1, 4]]
[[0, 2, 4], [1, 3]]
[[0, 3, 4], [1, 2]]
[[1, 2, 3], [0, 4]]
[[1, 2, 4], [0, 3]]
[[1, 3, 4], [0, 2]]
[[2, 3, 4], [0, 1]]
```
All other arrangements are similar to one of the arrangements above and are not counted as different. In particular, all of the following arrangements are considered to be the same:
```[[0, 1, 2], [3, 4]]
[[2, 0, 1], [3, 4]]
[[1, 2, 0], [4, 3]]
[[0, 2, 1], [3, 4]]
[[3, 4], [0, 2, 1]]
```
This is because the following pairs of people (and no other pairs) are sitting next to each other in each of these 5 arrangements:
```0 and 1
0 and 2
1 and 2
3 and 4
```

Another example is N = 5 and K = 3, which requires having two tables with two people each, and one table with a single person sitting at it. There are 15 possible arrangements in this case:

```[[0, 1], [2, 3], [4]]
[[0, 1], [2, 4], [3]]
[[0, 1], [3, 4], [2]]
[[0, 2], [1, 3], [4]]
[[0, 2], [1, 4], [3]]
[[0, 2], [3, 4], [1]]
[[0, 3], [1, 2], [4]]
[[0, 3], [1, 4], [2]]
[[0, 3], [2, 4], [1]]
[[0, 4], [1, 2], [3]]
[[0, 4], [1, 3], [2]]
[[0, 4], [2, 3], [1]]
[[1, 2], [3, 4], [0]]
[[1, 3], [2, 4], [0]]
[[1, 4], [2, 3], [0]]
```

In this final example, N = 5 and K = 1, which means that we only have a single table, seating all 5 guests. Here, the answer is 12:

```[[0, 1, 2, 3, 4]]
[[0, 1, 2, 4, 3]]
[[0, 1, 3, 2, 4]]
[[0, 1, 3, 4, 2]]
[[0, 1, 4, 2, 3]]
[[0, 1, 4, 3, 2]]
[[0, 2, 1, 3, 4]]
[[0, 2, 1, 4, 3]]
[[0, 2, 3, 1, 4]]
[[0, 2, 4, 1, 3]]
[[0, 3, 1, 2, 4]]
[[0, 3, 2, 1, 4]]
```

### Input

The first line of the input gives the number of test cases, T. T lines, each one containing two integers, N and K.

### Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of different possible seating arrangements.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ KN.

1 ≤ T ≤ 36.
1 ≤ N ≤ 8.

1 ≤ T ≤ 210.
1 ≤ N ≤ 20.

### Sample

 Input Output ```5 5 2 5 3 5 4 5 1 1 1 ``` ```Case #1: 10 Case #2: 15 Case #3: 10 Case #4: 12 Case #5: 1 ```

## Saturnalia: Analysis

The first problem in the first instance of this new Code Jam contest has a very straightforward solution:

• Determine the length of the given string; call it L.
• Output a line consisting of one `+` character, L+2 `-` characters, and one more `+` character.
• Output a line consisting of one `|` character, then one space, then the given string, then another space, then one more `|` character.
• Output another line identical to the first line described above.

It is important to avoid reading the input in a way that strips space characters, since those are considered part of the given string. Sample Case #4 calls attention to this issue.

## Zathras: Analysis

### Small dataset

The Small dataset is an exercise in understanding the rules of the described system, and then turning them into code. There are some issues to watch out for:

• If we use floating-point numbers, we must avoid precision issues and ensure that we round down appropriately whenever the rules require it. It is safer to reframe the calculations to use only integers; in most languages, integer division already has the round-down property that the rules require.
• When determining the types of babies, we must see how many guaranteed babies of each type we get before we can know the size of the pool of remaining babies to divvy up. Suppose we have α = 40 and β = 20, and 4950 of each type of Zathrinian. Then we must create 99 babies; floor(99 * 0.4) = 39 of them must be acrobots, floor(99 * 0.2) = 19 of them must be bouncoids, and then the remaining 99 - 39 - 19 = 41 of them must be 20 acrobots and 21 bouncoids, for a total of 59 acrobots and 40 bouncoids. If we had instead tried to directly calculate the number of remaining babies as 100 - 40 - 20 = 40% of 99, we would have gotten 39 or 40 (depending on how we rounded), not 41.

Since Y ≤ 100 in the Small dataset, simulation is fast enough. Note that it is possible for Y to equal 0!

### Large dataset

In the Large dataset, Y can be as large as 1015; there is not enough time in the submission window to simulate that many steps. (Most contestants who attempted but did not pass this dataset got the "Time expired" verdict.) We need another insight.

The example in the problem statement provides a hint: the numbers of acrobots and bouncoids reach stable values that do not change from year to year. If we ever find that those numbers are the same two years in a row, we know they will be the same forever (since the rules do not change), and so we can stop the simulation. But how can we convince ourselves that this will necessarily happen fast enough, or at all? If there is a cycle of length greater than 1 — that is, if we see the same pair of acrobot and bouncoid population values more than once, but not back-to-back — then this strategy will fail. It turns out to be difficult to prove that there are no such cycles, or even to set bounds on how long the simulation can go on.

At this point, one option is to just assume that the simulation always reaches a stable point, and this assumption turns out to be correct. Another option is to implement a more cautious simulation that includes a cycle detection algorithm that uses constant memory; if we detect a cycle, we can then figure out where in the cycle the simulation would end, without actually running the remainder (but, again, this turns out not to happen). Since there are just over 1012 possible ordered pairs of acrobot and bouncoid population values, the simulation cannot possibly take more steps than that, and it is possible to convince yourself that much tighter upper bounds exist. Under the given rules, the percentage of acrobots approaches α + (100 - α - β) / 2, and the percentage of bouncoids approaches β + (100 - α - β) / 2, and these approaches are at more or less exponential speed, although they may oscillate around their final values for a while (and it is even possible for the total population size to increase, up to a point). The behavior of the exponential approach is "smooth" — small changes to a set of initial values do not change the behavior much — so you can make yourself more confident overall by experimenting with various values. In practice, each simulation takes at most several tens of thousands of steps.

## Seating Chart: Analysis

Before assigning any particular people to particular tables, we can figure out how many people must sit at each table: M = N mod K of the tables will be "more full" and will have ceil(N / K) people each, and the other L tables will be "less full" and will have floor(N / K) people each.

### Small dataset

In the Small dataset, there are at most 8 people, and at most 8 tables. These numbers are small enough that we can try a brute force strategy; here is one example. Number the people from 1 to N, and generate each of the N! permutations of the list [1, ..., N]. Then, for each permutation, proceed left to right through the permutation, filling up the first table in clockwise order with the appropriate number of people, then the second table, and so on. Turn each of these assignments into a sorted list of pairs of people who are sitting next to each other, with the numbers in each pair themselves sorted in ascending order. Maintain a set of all such lists found, discarding any duplicates, and then return the size of that set.

### Large dataset

In the Large dataset, N can be as large as 20, so we need to use combinatorics. As in the Small dataset, the tricky part is to avoid counting the same arrangement more than once.

First, let's consider how we assign people to tables. If we have P people who are not yet assigned, and the table requires Q people, there are (P choose Q) ways of selecting those people.

Then, how many ways are there to put those Q people around the table? First, let's dispense with some small cases: for 1 or 2 people, there is only one way. Otherwise, without loss of generality, let's put the first person in our chosen set at the "top" of the table. Then, for each of the (Q-1)! possible orders of the remaining people, we can try putting them clockwise around the table, starting from the spot that is directly clockwise from our "top" person. Notice that for any one of these orders, using the reverse of that order creates an equivalent arrangement, so there are really only (Q-1)! / 2 possibilities.

So, we can start by saying there is 1 possible arrangement, and then, for each table, multiply that number by (P choose Q) and (Q-1)! / 2, to reflect populating that table. The value of P will diminish as we seat more and more people, and the value of Q will depend on whether we are looking at one of our "more full" or "less full" tables. It does not matter what order we process the tables in.

However, after we have done this, we still need to correct for some overcounting. For any particular arrangement, we have a huge number of duplicates. Specifically, we could have enumerated the M "more full" tables in the arrangement in any one of M! possible orders, and the L "less full" tables in any one of L! possible orders. Dividing our total by M! and L! eliminates this redundancy and yields the correct answer.

First
MirandaYang 3:37
acktshoo 4:59
cherry_su 5:25
KirarinSnow 5:50
Mog.Joyce 6:01

## Statistics — B. Zathras

### Test set 1: 112 correct solutions (77.8% solve rate)

First
CodingPenguin 22:18
MirandaYang 23:24
chicapi 24:13
Sarah810 25:37
nikkib 25:59

### Test set 2: 19 correct solutions (13.2% solve rate)

First
MirandaYang 23:24
Skulla 31:05
KirarinSnow 32:19
Razieh 36:59
wet.raccoon 39:19

## Statistics — C. Seating Chart

### Test set 1: 23 correct solutions (16.0% solve rate)

First
Witty khaki giraffe 42:09
MirandaYang 45:56
KirarinSnow 69:58
pangjun92 73:39
lennie2nd 85:12

### Test set 2: 18 correct solutions (12.5% solve rate)

First
Witty khaki giraffe 42:09
MirandaYang 45:56
KirarinSnow 69:58
yifanwu 86:56
tearswillz 95:08