|
| Contest: OPEN11 GOLD Division |
|
|
|
|
ANALYSIS MODE
Submit solutions for your own enjoyment.
**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Four problems numbered 11 through 14
**********************************************************************
Problem 11: The Bovine Fire Drill [Lewin Gan, 2011]
The N (3 <= N <= 250) cows (conveniently labeled cow_1..cow_N) sat
in a perfect circle around the camp fire in chairs numbered
chair_1..chair_N as Farmer John told them stories of the old days
(cow_i sits in chair_i, of course). At the conclusion of one story,
FJ suggested they perform a Bovine Fire Drill.
In a Bovine Fire Drill, one cow at a time walks around the circle
from her chair to a potentially new chair while the other cows chant
"Fire, fire, fire." When it is cow_i's turn to move, she rises and
moves clockwise to the i'th chair encountered in that direction (so
if it was cow_3's turn, she would rise from chair_3 and move to
chair_6 if N >= 6).
When cow_i arrives at her new chair, she taps any cow sitting there
on the shoulder; that cow rises to make room for cow_i, who sits
down. This process continues until a cow lands in an empty chair
or until a cow is asked to move for a second time. In either of
those cases, the game ends. Cow 1 always starts, so it is her chair
that will be the empty one.
Only rarely do all the cows get to participate, as the game termination
conditions arise naturally and frequently from the properties of
whole numbers. The final cow to move (whether she ends the game by
sitting in cow_1's chair or by tapping the shoulder of a cow who
has already moved) receives a special treat of extra tender grass.
Help FJ plan in advance to learn which cow will get the tender
grass.
For example, consider five cows sitting around the blazing campfire:
2 - 3
( )
1 - 5 - 4
First, cow 1 walks one space and taps cow 2, who rises. (The *
denotes the empty chair.)
2
1 - 3
( )
* - 5 - 4
Cow 2 walks two spaces and taps cow 4, who begins her journey:
1 - 3
( )
* - 5 - 2
4
Cow 4 will walk four spaces and tap cow 3:
3
1 - 4
( )
* - 5 - 2
Finally, cow 3 will walk three spaces to chair_1, which is empty and thus
terminates
the drill.
1 - 4
( )
3 - 5 - 2
Cow 3 receives tender spring grass as the other cows clap and cheer.
PROBLEM NAME: bfire
INPUT FORMAT:
* Line 1: A single integer: N
SAMPLE INPUT (file bfire.in):
5
OUTPUT FORMAT:
* Line 1: The number of the cow who ends the drill
SAMPLE OUTPUT (file bfire.out):
3
**********************************************************************
Problem 12: Skewed Sorting [Lewin Gan, 2011]
Farmer John has 2^N (1 <= N <= 10) cows, each conveniently labeled
with paint on her flank with a number in the range 1..2^N. They are
standing in a line in some random order. The first cow in line is
cow_1; the second cow in line is cow_2; and so on (1 <= cow_i <=
2^N). Of course, cow_1 is unlikely to carry the painted label 1.
He performs the following algorithm to put them in order.
1. If there is more than one cow, then partition the cows into
two equal-sized sub-groups. Sort the first sub-group using
this algorithm and then sort the second sub-group, also using
this algorithm.
2. Consider the current set of cows to be sorted as an equal-length
pair of (potentially huge) base 2^N numbers. If the second
number is smaller than the first one, then swap all the
elements of the second one with those elements of the first
one.
The cows would like to know how much distance they cover while
moving around during this 'sorting' procedure.
Given the initial configuration of the cows, process the list
according to the algorithm above and then print out:
* the sum of the total distances traveled by all cows and
* the final configuration of the cows after this 'sorting'
procedure.
By way of example, consider this line of 2^3=8 cows:
8 5 2 3 4 7 1 6
First, Farmer John will sort each half of the line separately:
8 5 2 3 | 4 7 1 6
Since each half still has more than one cow, Farmer John will sort
those halves separately; starting with the 'first' half:
8 5 | 2 3
Partitioning again, FJ makes
8 | 5 and 2 | 3
each of which can be sorted by second rule, ultimately yielding:
5 | 8 and 2 | 3 (<--unchanged)
The distance traveled by each cow during the first subgroup's sort
is 1, so total_distance_moved becomes 2. The second half is already
sorted, so the total_distance_moved stays at 2. The new configuration
of this sub-group is:
5 8 | 2 3
For step 2 of the algorithm on the subgroup above, we compare the
two sides lexicographically (5 8 vs. 2 3). Since the 2 comes before
5, we swap the two elements of the first half with the corresponding
elements of the second half, yielding:
2 3 5 8
Each of the four cows moved two spaces in this swap, contributing
a total of 8 moves, so total_distance_moved becomes 10.
Consider the other half of the cows; we divide the list of four
into two sub-groups:
4 7 | 1 6
Each pair (4, 7) and (1, 6) is already sorted.
Comparing (4 7) to (1 6), since 1 comes before 4, we must swap the
two sub-groups:
1 6 4 7
which contributes a total of 8 more moves, bringing total_distanced_move
to 18.
After the operations above, the list looks like this (and it's time
for step 2 to be performed on the two groups of 4):
2 3 5 8 | 1 6 4 7
Since 1 comes before 2, we must swap the halves, this yielding this
configuration:
1 6 4 7 2 3 5 8
Since each of 8 cows moved four units, this contributes a total of
32 more moves, making total_distance_moved become 50
Therefore, the answer is 50 and 1 6 4 7 2 3 5 8.
PROBLEM NAME: ssort
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..2^N + 1: Line i+1 contains a single integer: cow_i
SAMPLE INPUT (file ssort.in):
3
8
5
2
3
4
7
1
6
OUTPUT FORMAT:
* Line 1: One integer, the total distance traveled by all the cows
* Lines 2..2^N + 1: Line i+1 will contain one integer: the ith cow in
the final configuration
SAMPLE OUTPUT (file ssort.out):
50
1
6
4
7
2
3
5
8
**********************************************************************
Problem 13: 3D Space Exploration [Andre Kessler, 2010]
Farmer John's cows have finally blasted off from earth and are now
floating around space in their Moocraft. The cows want to reach
their fiery kin on Io, a moon of Jupiter, but to do so they first
must navigate the dangerous asteroid belt.
Bessie is piloting the craft and must guide it through this treacherous
N x N x N (1 <= N <= 100) sector of space. All asteroids in this
sector comprise some number of 1 x 1 x 1 blocks of space-rock
connected along their faces (two blocks sharing only a vertex or
only an edge count as two distinct asteroids).
Please help Bessie by counting the number of distinct asteroids in
the field.
Consider a 3 x 3 x 3 space where the first slice of space looks
like this, with 'M' indicating the starting location of the Moocraft
(1,1,1) and 'D' is the destination at (3,3,3). In these maps, these
markers serve mostly as map orientation rather than providing useful
information to solve the problem.
In these diagrams and also in the input file, the *'s represent
asteroid chunks and each '.' represents a vast void of empty space.
Close slice Middle slice Far Slice Assembled with overlaps
+---+ +---+ +---+ +---+ Far
|M..| |..*| |...| |...|
|.*.| |.*.| |.*.| +---+.|
|...| |*..| |..D| |..*|D|
+---+ +---+ +---+ +---+.|-+
|M..|.|
|.*.|-+
|...|
Close +---+
Visual inspection shows three asteroids, including a long one through
the middle of the map. Here's a map with the asteroid pieces labelled:
+---+ Far
/|...|
/ |.1.|
/ |...|
/ +---+
+---+ /
/|..3| /
/ |.1.| /
/ |2..|/
/ +---+
+---+ /
|...| /
|.1.| /
|...|/
Close +---+
PROBLEM NAME: space3d
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..N^2+1: Line i-1 contains line 1 + ((k+1)%N) of slice int (
(i+N-1)/N ): N characters
SAMPLE INPUT (file space3d.in):
3
...
.*.
...
..*
.*.
*..
...
.*.
...
OUTPUT FORMAT:
* Line 1: A single integer indicating the number of asteroids in the
field
SAMPLE OUTPUT (file space3d.out):
3
**********************************************************************
Problem 14: String Function Encoding [Lewin Gan, 2011]
Bessie discovered a new function that the entire herd can apply to
its character strings.
Given both a number N (1 <= N <= 15) and a string S, with length
strictly greater than N, define f(N, S) as a new string composed
of the concatenation of the substring from character N (zero based
-- first character is number 0) through the end of S and the string
S itself.
For example, with N = 2, and S = "COW", f(N, S) = "W" + "COW" =
"WCOW". Also, f(3, "USACO") = "CO" + "USACO" = "COUSACO".
Bessie is enthralled with this function and wants to iterate it
several times. For example, if she iterates the function once for
"COW" and N = 2, she will get "WCOW". If she applies the function
with N = 2 again to that string, she will get "OWWCOW", and if she
applies it one more time with N = 2, she will get "WCOWOWWCOW".
Help Bessie encode a total of Z (1 <= Z <= 100) strings, str_1,
str_2, and so on. Each str_i has length in the range 2..100 and
contains only upper case letters. Each string is presented with its
own N_i (0 <= N_i < length(str_i), and iteration count C_i (1 <= C_i
<= 12).
PROBLEM NAME: stringe
INPUT FORMAT:
* Line 1: A single integer: Z
* Lines 2..Z+1: Line i+1 contains two space-separated integers, a
space, and string to be encoded: N_i, C_i, and str_i
SAMPLE INPUT (file stringe.in):
2
2 3 COW
3 2 USACO
OUTPUT FORMAT:
* Lines 1..Q: Line j contains the iterated, encoded version of str_j
SAMPLE OUTPUT (file stringe.out):
WCOWOWWCOW
SACOCOUSACO
OUTPUT DETAILS:
The arrow denotes an iteration of the function
COW -> WCOW -> OWWCOW -> WCOWOWWCOW
USACO -> COUSACO -> SACOCOUSACO
**********************************************************************