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.
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?
The first line of the input gives the number of test cases, T. T lines follow. Each line contains a text message.
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.
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).
|
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.
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
Out of all the baby Zathrinians produced,
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.
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
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?
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.
For each test case, output one line containing
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.
|
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 |
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
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
[[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,
[[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]]
The first line of the input gives the number of test cases, T. T lines, each one containing two integers, N and K.
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.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ K ≤ N.
1 ≤ T ≤ 36.
1 ≤ N ≤ 8.
1 ≤ T ≤ 210.
1 ≤ N ≤ 20.
|
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 |
The first problem in the first instance of this new Code Jam contest has a very straightforward solution:
+ character, L+2
- characters, and one more + character.| character, then one space,
then the given string, then another space, then one more |
character.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.
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:
Since Y ≤ 100 in the Small dataset, simulation is fast enough. Note that it is possible for Y to equal 0!
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.
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.
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.
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.