ACM Programming Contest
Western Preliminary
@
SUNY
Contest Questions
Problem 1:COUNTING THE DAYS.
The marquee for a movie theater has a sign containing
light bulbs
arranged in a particular way on
an M x N rectangle (M light-bulbs
high by N light-bulbs wide, but
only the top, middle and bottom
rows contain N light bulbs.)
Assume M is always an odd number.
For example, a 5x3 grid of bulbs would appear as shown,
with
an asterisk (*) representing a
bulb.
*--*--*
| |
| |
* *
| |
| |
*--*--*
| |
| |
* *
| |
| |
*--*--*
The lights are going to be used to count down the days
until the
release of the new Stewart Cheifet movie. As such they are meant
to mimic a 7-segment display,
whose segments are labeled as shown.
a
---
| |
f| |b
| g |
---
| |
e| |c
| d |
---
The segments are lit to represent the digits 0-9 thusly:
_ _
_ _
_ _ _
_
| | |
_| _| |_| |_ |_
| |_| |_|
|_| |
|_ _| | _| |_|
| |_| |
An important assumption is - whenever a segment is to be
lit,
all bulbs including the
end-points are on. Thus, to light
segment 'a', all horizontal
lights in the top row would be on.
To light segment 'b', the right end-points of 'a' and 'g'
would
be on. The other segments behave
similarly.
Problem:
Given M, N, and a string of digits to display, calculate
the total "state
switches" (a bulb switching from on to off
or from off to on) required to
display the entire string.
Assume that initially all bulbs are off.
For example, with the 5x3 grid, the string
"123" would require
15 state switches:
- 5 to light up the 1
- 8 for the 2 (7 turn-ons
and 1 turn-off)
- 2 for the 3 (1 turn-on and 1 turn-off from
those currently lit )
While the string "321" would require 21
switches:
- 11 for the 3
- 2 for the 2
- 8 for the 1
Input will be three lines containing M, N, and the string
of digits, respectively.
Output should be the number of state switches.
Problem 2:PACKING PRIMES.
Some newbie cryptographers are trying to transform secret
information
contained in ASCII text messages
into a seemingly innocuous list of
numbers. Their method is to treat the secret, encoded
in ASCII, as a
sequence of integers (0-127).
They convert each integer in the sequence
to its prime factorization. (The
numbers 0 and 1 represent themselves.)
Since there are only 32 unique numbers - 0, 1, and 30 prime
factors
required to represent this
integer sequence, each part of a character
can be stored in 5 bits. They then plan to pack this sequence of
numbers,
each between 0 and 30 inclusive,
into 16 bit entities, using 5 bits per
integer. The high order bit will always be zero. A
string of five 0's,
not counting any high order bit,
will separate the factorization for
each character.
For example, the string 'Bob' is '66 111 98' in ASCII
encoding.
The prime factors form the sequence
'(2 3 11) (3 37) (2 7 7)'.
So the desired packing would be
[ 3 | 4 | 7] [ 0 | 4 | 14] [ 0 | 3 | 6] [6 | 0 | 0]
Note that 2 is the third number in the encoding scheme -
0 is
first, 1 is second, 2 is third, 3 is fourth, 5 is fifth,
7 is
sixth, 11 is seventh, etc., for
the rest of the prime numbers.
In binary this would look like:
[0 00011 | 00100
| 00111 ]
[0 00000 | 00100
| 01110 ]
[0 00000 | 00011
| 00110 ]
[0 00110 | 00000
| 00000 ]
The numbers would then be printed as 16-bit integers, so
the
desired output would be:
3207
142
102
6144
You don't have to use any particular packing scheme. Your
output
just has to replicate what would
appear if the three 5-bit entities
were packed into one 16-bit
integer as specified.
Input will be an ascii
text file. Output should be the numbers
derived therefrom,
one per line. Note that you DO encode any
ASCII new-line characters in the input
as part of the numbers.
Your output will add newline
characters after each number.
Problem 3: Chainsaw Massacre
As every year the Canadian Lumberjack Society has just
held its annual woodcutting competition and the national forests between
The organizing committee has asked you to find the largest
yet free rectangle which could serve as the dance floor. The area in which you
should search is also rectangular and the dance floor must be entirely located
in that area. Its sides should be parallel to the borders of the area. It is
allowed that the dance floor is located at the borders of the area and also
that trees grow on the borders of the dance floor. What is the maximum size of
the dance floor?
The Input
The first line of the input specifies the number of
scenarios. For each scenario, the first line provides the length l and width w
of the area in meters ( , both integers). Each of the
following lines describes either a single tree, or a line of trees according to
one of the following formats:
1 x y, where the ``one'' characterizes a single tree, and
x and y provide its coordinates in meters with respect to the upper left
corner.
k x y dx dy,
where k>1 provides the number of trees in a line with coordinates
.
0 denotes the end of the scenario.
The coordinates x, y, dx, and dy are given as integers. It is
guaranteed that all the trees are situated in the area, i.e. have coordinates in . There will be at most 1000 trees.
The Output
For each scenario print a line containing the maximum
size of the dance floor measured in square meters.
Sample Input
2
2 3
0
10 10
2 1 1 8 0
2 1 9 8 0
0
Sample Output
6
80
Problem 4:
Tourist Guide
Because of his disabilities, Bruno has a lot of fines to
pay and he doesn't want to have even more to pay, even though he promised you
to be your tourist guide. What he would like to know, however, is where are all
the cameras that help the police to fine the bad drivers, so he can drive more
carefully when passing by them.
Those cameras are strategically distributed over the
city, in locations that a driver must pass through in order to go from one zone
of the city to another. In order words, if there are two city locations A and B
such that to go from one to another (A to B or B to A) a driver must pass
through a location C, then C will have a camera.
For instance, suppose that we have 6 locations (A, B, C,
D, E and F) and that we have 7 routes (all of them bidirectonal)
B-C, A-B, C-A, D-C, D-E, E-F and F-C. There's a camera on C because to go from
A to E, for instance, you must pass through C. In this configuration, there's
only one camera (on C).
Your task is to help Bruno (as he wants to be a musician
and he doesn't want to get even close to computers) and write a program which
will tell him where are all the cameras, given the map of the city, so he can
be your tourist guide and avoid further fines.
Input
The input will consist of an arbitrary number of city
maps. Each city map will begin with an integer N (2 < N <= 100) which
stands for the total locations of the city. Then will follow N different place
names, one per line. Each place name will have at least one and at most 30
characters (all of them will be lowercase latin
letters). Then will follow a non-negative integer R which stands for the total
routes of the city. Then will follow R lines with the routes. Each route will
be represented by the name of both places that the route connects (remember
that the routes are bidirectional). Location names in route description will
always be valid and there will be no route from one place to itself. You must
read until N = 0, and this input should not be processed.
Output
For each city map you must print the line:
City map #d: c camera(s) found
Where d stands for the city map number
(starting from 1) and c stands for the total number of cameras. Then
should follow c lines with the location names where
are each camera (in alphabetic order). You should print a blank line between
output sets.
Sample Input
6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema
copacabana
copacabana
sugarloaf
ipanema
sugarloaf
maracana
lapa
sugarloaf maracana
corcovado
sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
sambodromo
4
guanabarabay
sambodromo
downtown sambodromo
sambodromo
botanicgarden
0
Sample Output
City map #1: 1 camera(s) found
sugarloaf
City map #2: 1 camera(s) found
sambodromo
Problem 5:Shoemaker's Problem
Shoemaker has N jobs (orders from customers) which he
must make. Shoemaker can work on only one job in each day. For each ith job, it is known the integer Ti (1<=Ti<=1000),
the time in days it takes the shoemaker to finish the job. For each day of
delay before starting to work for the ith job,
shoemaker must pay a fine of Si (1<=Si<=10000) cents. Your task is to help the shoemaker,
writing a program to find the sequence of jobs with minimal total fine.
Input
The input begins with a single positive integer on a line
by itself indicating the number of the cases following, each of them as
described below. This line is followed by a blank line, and there is also a
blank line between two consecutive inputs.
First line of input contains an integer N
(1<=N<=1000). The next N lines each contain two numbers: the time and
fine of each task in order.
Output
For each test case, the output must follow the
description below. The outputs of two consecutive cases will be separated by a
blank line.
You programm should print the
sequence of jobs with minimal fine. Each job should be represented by its
number in input. All integers should be placed on only one output line and
separated by one space. If multiple solutions are possible, print the first
lexicographically.
Sample Input
1
4
3 4
1 1000
2 2
5 5
Sample Output
2 1 3 4
Problem 6:Stack 'em
Up
A standard playing card deck contains 52 cards, 13 values
in each of four suits. The values are named 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack,
Queen, King, Ace. The suits are named Clubs, Diamonds,
Hearts, Spades. A particular card in the deck can be
uniquely identified by its value and suit, typically denoted <value> of
<suit>. For example, "9 of Hearts" or
"King of Spades". Traditionally a new deck is ordered first
alphabetically by suit, then by value in the order given above.
The
You have been retained by the security manager to track
this dealer. You are given a list of all the shuffles performed by the dealer,
along with visual cues that allow you to determine which shuffle she uses at
any particular time. Your job is to predict the order of the cards after a
sequence of shuffles.
Input
The input begins with a single positive integer on a line
by itself indicating the number of the cases following, each of them as
described below. This line is followed by a blank line, and there is also a
blank line between two consecutive inputs.
Input consists of an integer n <= 100, the number of
shuffles that the dealer knows. 52n integers follow. Each consecutive 52
integers will comprise all the integers from 1 to 52 in some order. Within each
set of 52 integers, i in position j means that the shuffle moves the ith
card in the deck to position j.
Several lines follow; each containing an integer k
between 1 and n indicating that you have observed the dealer applying the kth shuffle given in the input.
Output
For each test case, the output must follow the
description below. The outputs of two consecutive cases will be separated by a
blank line.
Assume the dealer starts with a new deck ordered as
described above. After all the shuffles had been performed, give the names of
the cards in the deck, in the new order.
Sample Input
1
2
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 52 51
52 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 1
1
2
Output for Sample Input
King of Spades
2 of Clubs
4 of Clubs
5 of Clubs
6 of Clubs
7 of Clubs
8 of Clubs
9 of Clubs
10 of Clubs
Jack of Clubs
Queen of Clubs
King of Clubs
Ace of Clubs
2 of Diamonds
3 of Diamonds
4 of Diamonds
5 of Diamonds
6 of Diamonds
7 of Diamonds
8 of Diamonds
9 of Diamonds
10 of Diamonds
Jack of Diamonds
Queen of Diamonds
King of Diamonds
Ace of Diamonds
2 of Hearts
3 of Hearts
4 of Hearts
5 of Hearts
6 of Hearts
7 of Hearts
8 of Hearts
9 of Hearts
10 of Hearts
Jack of Hearts
Queen of Hearts
King of Hearts
Ace of Hearts
2 of Spades
3 of Spades
4 of Spades
5 of Spades
6 of Spades
7 of Spades
8 of Spades
9 of Spades
10 of Spades
Jack of Spades
Queen of Spades
Ace of Spades
3 of Clubs