ACM_2004_Problems.txt
Published in DevCode 2001. Original code and wording are preserved.
ACM Programming Competition - 2004 Regional Problems
======================================================
PROBLEM 1: Flow Layout
======================================================
A flow layout manager takes rectangular objects and places them
in a rectangular window from left to right. If there isn't enough
room in one row for an object, it is placed completely below all
the objects in the first row at the left edge, where the order
continues from left to right again. Given a set of rectangular
dimensions and a maximum window width, you are to write a program
that computes the dimensions of the final window after all the
rectangles have been placed in it.
INPUT
-----
The input consists of one or more sets of data, followed by a
final line containing only the value 0. Each data set starts with
a line containing an integer N (1 <= N <= 100), which is the
maximum width of the resulting window. This is followed by at
least one and at most 15 lines, each containing the dimensions of
one rectangle, width first, then height. The end of the list of
rectangles is signaled by the pair -1 -1, which is not counted as
the dimensions of an actual rectangle. Each rectangle is between
1 and 100 units wide (inclusive) and between 1 and 100 units high
(inclusive).
OUTPUT
------
For each input set print the width of the resulting window,
followed by a space, then the lowercase letter "x", followed by
a space, then the height of the resulting window.
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
35 30 x 25
10 5 23 x 18
20 12 15 x 47
8 13
-1 -1
25
10 5
20 13
3 12
-1 -1
15
5 17
5 17
5 17
7 9
7 20
2 10
-1 -1
0
======================================================
PROBLEM 2: Ink Blots
======================================================
[img: p2-0001.png]
Figure 1: 1 White Region
[img: p2-0002.png]
Figure 2: 3 White Regions
[img: p2-0003.png]
Figure 3: 4 White Regions
Drops of dark ink can fall on a white piece of paper creating a
number of round ink blots. The blots can create multiple distinct
white regions. In Figure 1, there is just one white region. In
Figure 2 there is the outer white region plus a small white region
bounded by the left four blots and an even smaller white region
bounded by the right three blots. In Figure 3, there are four
white regions: one on the very outside, one inside the outer ring
of blots and outside the four blots in the middle, and two tiny
ones each formed between three of the four inner blots.
Two points are in the same white region if a path can be drawn
between them that only passes through white points. Your problem
is to count the number of white regions given the centers and
radii of the blots.
MATH FORMULAS
-------------
If circles C1 (center P1, radius r1) and C2 (center P2, radius r2)
intersect in exactly two distinct points, let:
d = distance between centers of C1 and C2
a = (r1^2 - r2^2 + d^2) / (2*d)
h = sqrt(r1^2 - a^2)
The intersection points on C1 are at angles:
atan2(Py2 - Py1, Px2 - Px1) +/- acos(a / r1)
radians counterclockwise from the ray extending right from C1.
(atan2 and acos available in C, C++, and Java math libraries.)
INPUT
-----
One to 15 data sets, followed by a final line containing only 0.
Each data set starts with a single positive integer N (N <= 100),
the number of blots. Then N groups of three positive integers
follow (separated by spaces or newlines): X coordinate, Y
coordinate, and radius of each blot. All values <= 10000. All
blots lie entirely on the paper; no blot touches any edge. No two
circles are identical. Any two distinct circles either intersect
at exactly two distinct points or not at all. If two circles
intersect, they overlap by at least one unit. Three or more
circles never intersect at the same point. Any two intersection
points on the same circle are separated by at least 10^-5 radians.
OUTPUT
------
One line per data set containing only the number of white regions
(never more than 200).
WARNING: Brute force raster methods will be too slow and use
too much memory.
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
4 1
45 45 40 3
65 55 35 4
45 45 10
20 95 10
5
30 30 20 30 60 20
60 30 20 60 60 20
90 45 15
16
200 120 65 300 100 55 400 120 65 480 200 65
500 300 55 480 400 65 400 480 65 300 500 55
200 480 65 120 400 65 100 300 55 120 200 65
300 245 60 300 355 60 385 300 51 215 300 51
0
======================================================
PROBLEM 3: Permutation Code
======================================================
As the owner of a computer forensics company, you have just been
given the following note by a new client:
"I, Albert Charles Montgomery, have just discovered the most
amazing cypher for encrypting messages. Let me tell you about it.
To begin, you will need to decide on a set of symbols, call it S,
perhaps with the letters RATE. The size of this set must be a
power of 2 and the order of the symbols in S is important. You
must note that R is at position 0, A at 1, T at 2, and E at 3.
You will also need one permutation P of all those symbols, say
TEAR. Finally you will need an integer, call it x. Together,
these make up the key.
Given a key, you are now ready to convert a plaintext message M
of length n into a cyphertext string C, also of length n. The
encrypting algorithm computes C as follows:
1. Calculate d = floor(sqrt(x)) % n
2. Set C[d] to be the symbol in S whose position is the same as
the position of M[d] in P.
3. For each j != d, set C[j] to be the symbol in S whose position
is obtained by XOR-ing the position of M[j] in P with the
position of M[(j+1) % n] in S.
(bitwise XOR is '^' in C, C++, and Java)
EXAMPLE: S=RATE, P=TEAR, x=102, M=TEETER, n=6
d = floor(sqrt(102)) % 6 = 10 % 6 = 4... wait: 116 % 6 = 2, so d=2
0 1 2 3 4 5
S = R A T E
P = T E A R
M = T E E T E R
C[0]: M[0]=T at P[0], M[1]=E at S[3]. C[0] = S[0^3] = S[3] = E
C[1]: M[1]=E at P[1], M[2]=E at S[3]. C[1] = S[1^3] = S[2] = T
C[2]: d=2. M[2]=E at P[1]. C[2] = S[1] = A
C[3]: M[3]=T at P[0], M[4]=E at S[3]. C[3] = S[0^3] = S[3] = E
C[4]: M[4]=E at P[1], M[5]=R at S[0]. C[4] = S[1^0] = S[1] = A
C[5]: M[5]=R at P[3], M[0]=T at S[2]. C[5] = S[3^2] = S[1] = A
Result: C = ETAEAA"
INPUT
-----
One or more {key, encrypted message} pairs. The key is on 3 lines:
Line 1: integer x (x >= 1)
Line 2: string S (length is a power of 2: 2, 4, 8, 16, or 32)
Line 3: string P (a permutation of S)
Followed by: the encrypted message C (1 to 60 characters).
S, P, and C will not contain whitespace but may contain printable
non-alphanumeric characters. Input ends with a line containing 0.
OUTPUT
------
For each input set print the decrypted string on a single line.
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
102 TEETER
RATE HELLO_WORLD
TEAR THE_CAT_IN_THE_HAT
ETAEAA
32
ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,;
;ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,
MOMCUKZ,ZPD
1956
ACEHINT_
ACTN_IHE
CIANCTNAAIECIA_TAI
0
======================================================
PROBLEM 4: Primary X-Subfactor Series
======================================================
Let N be any positive integer. A FACTOR of N is any number that
divides evenly into N without a remainder. A SUBSEQUENCE of N is
a number without a leading zero that can be obtained from N by
discarding one or more of its digits (digits cannot be rearranged
or repeated beyond their count in N, and at least one digit must
be discarded).
A SUBFACTOR of N is an integer greater than 1 that is both a
factor and a subsequence of N.
Example: 2004 has subfactors 2, 4, and 200.
Example: Some numbers have no subfactor (e.g. 7).
An X-SUBFACTOR SERIES of N is a decreasing series of integers
N = a1 > a2 > a3 > ... > ak
in which:
(1) a1 = N
(2) ak = 0 or ak has no subfactor
(3) For all i, a(i+1) is obtained from ai by discarding the
digits of a subfactor of ai, then discarding any leading zeros
(4) ak has no subfactor
The PRIMARY x-subfactor series has maximal length. If two or more
series share maximal length, the one with the smallest second
number is primary; then smallest third, and so on. Every positive
integer has a unique primary x-subfactor series.
2004 has two distinct x-subfactor series:
2004 -> 4 -> (end) [subfactor 200 removed, then 4]
2004 -> 200 -> 0 -> (end) [subfactor 4 removed, then 200...]
2004 -> 200 -> 0 <-- PRIMARY (longest, smallest a2)
INPUT
-----
At most 1000 positive integers, each less than one billion,
without leading zeros, one per line. Followed by a line
containing only "0" to signal end of input.
OUTPUT
------
For each positive integer, output its primary x-subfactor series
on a single line, space-separated.
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
123456789 123456789 12345678 1245678 124568 12456 1245 124 12 1
7 7
2004 2004 200 0
6341 6341
8013824 8013824 13824 1324 132 12 1
0
======================================================
PROBLEM 5: Speed Limit
======================================================
Bill and Ted are taking a road trip. But the odometer in their
car is broken, so they don't know how many miles they have driven.
Fortunately, Bill has a working stopwatch, so they can record
their speed and the total elapsed time. Their record keeping
strategy is a little odd, so they need help computing the total
distance driven.
Example log:
Speed (mph) Total elapsed time (hrs)
20 2
30 6
10 7
This means: 2 hrs at 20 mph, then 4 hrs at 30 mph, then 1 hr
at 10 mph. Note that elapsed time is always since the BEGINNING
of the trip, not since the previous entry.
Distance = (2)(20) + (4)(30) + (1)(10) = 40 + 120 + 10 = 170 miles
INPUT
-----
One or more data sets (at most 10). Each set starts with a line
containing an integer N (N >= 1), followed by N pairs of values
(one pair per line):
s_i = speed in miles per hour
t_i = total elapsed time in hours
Both s_i and t_i are integers, 1 <= s_i <= 90, 1 <= t_i <= 12.
The values for t_i are always in strictly increasing order.
A value of -1 for N signals end of input.
OUTPUT
------
For each input set, print the distance driven, followed by a
space, followed by the word "miles".
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
3 170 miles
20 2 180 miles
30 6 90 miles
10 7
2
60 1
30 5
4
15 1
25 2
30 3
10 5
-1
======================================================
PROBLEM 6: Symmetric Order
======================================================
In your job at Albatross Circus Management (yes, it's run by a
bunch of clowns), you have just finished writing a program whose
output is a list of names in nondescending order by length. However,
your boss wants the output to appear more symmetric, with shorter
strings at the top and bottom and longer strings in the middle.
His rule: each pair of names belongs on opposite ends of the list,
and the first name in the pair is always in the top part.
Example (7 names): Bo, Pat, Jean, Kevin, Claude, William, Marybeth
Pairs: (Bo, Pat), (Jean, Kevin), (Claude, William), [Marybeth]
Top half: Bo, Jean, Claude <- first of each pair
Middle: Marybeth <- odd one out (goes in middle)
Bottom half: William, Kevin, Pat <- second of each pair, reversed
Result: Bo / Jean / Claude / Marybeth / William / Kevin / Pat
INPUT
-----
One or more sets of strings, followed by a final line containing
only 0. Each set starts with a line containing an integer N
(the number of strings), followed by N strings, one per line,
sorted in nondescending order by length. No strings contain
spaces. 1 <= N <= 20. Each string is at most 20 characters long.
OUTPUT
------
For each input set print "SET k" on a line (k starts at 1),
followed by the rearranged output set.
SAMPLE INPUT SAMPLE OUTPUT
------------ -------------
7 SET 1
Bo Bo
Pat Jean
Jean Claude
Kevin Marybeth
Claude William
William Kevin
Marybeth Pat
6 SET 2
Jim Jim
Ben Zoe
Zoe Frederick
Joey Annabelle
Frederick Joey
Annabelle Ben
5 SET 3
John John
Bill Fran
Fran Cece
Stan Stan
Cece Bill
0
======================================================
PROBLEM 7: Triangles (Cutting Paper)
======================================================
[img: p7-0001.png]
Figure 1
[img: p7-0002.png]
Figure 2
[img: p7-0003.png]
Figure 3
[img: p7-0004.png]
Figure 4 (Disallowed Pattern)
A computer science professor was watching his young daughter use
scissors to cut large triangular pieces of paper (green on one
side, white on the other, always white side up). Starting with
one large white triangle, she always makes exactly THREE straight
cuts, each separating one piece into two, ending up with exactly
FOUR smaller white triangles.
Figures 1 and 2 show the only ways to produce four triangles
without a cut going all the way from one vertex to the opposite
side (including any rotations). Figure 4 is disallowed: after
cutting off the rightmost triangle, no remaining cut can separate
the remaining piece into two pieces.
The professor's question: given the angles of a large triangle
and four smaller ones, could the small triangles have been
obtained from the large one using this procedure?
He noted that only shapes matter -- if shapes are compatible,
there will always be some appropriate sizes.
INPUT
-----
1 to 30 datasets, followed by a line containing only "0 0 180".
Each dataset contains 15 positive integers (< 180) separated by
single blanks on one line. Each group of three integers are the
vertex angles of one triangle, listed in CLOCKWISE order. The
first group is the large triangle; the last four are the small
ones. Triangles are never flipped (green side stays down).
OUTPUT
------
One line per dataset: "yes" if the four small triangles could
have been produced from the large one, "no" otherwise.
SAMPLE INPUT OUT
---------------------------------------------------- ---
60 70 50 30 100 50 75 70 35 75 60 45 45 65 70 yes
40 75 65 60 40 80 20 120 40 45 85 50 25 55 100 yes
60 60 60 30 60 90 30 60 90 90 60 30 90 60 30 yes
30 60 90 30 120 30 30 120 30 30 120 30 30 120 30 no
60 70 50 30 100 50 75 70 35 75 60 45 70 65 45 no
0 0 180