|
OPEN06 SILVER Division |
Contest is over |
|
|
| |
ANALYSIS MODE
Submit solutions for your own enjoyment.
**********************************************************************
SILVER PROBLEMS
**********************************************************************
Three problems numbered 6 through 8
**********************************************************************
Problem 6: The County Fair [Brian Dean, 2006]
Every year, Farmer John loves to attend the county fair. The fair
has N booths (1 <= N <= 400), and each booth i is planning to give
away a fabulous prize at a particular time P(i) (0 <= P(i) <=
1,000,000,000) during the day. Farmer John has heard about this
and would like to collect as many fabulous prizes as possible to
share with the cows. He would like to show up at a maximum possible
number of booths at the exact times the prizes are going to be
awarded.
Farmer John investigated and has determined the time T(i,j) (always
in range 1..1,000,000) that it takes him to walk from booth i to
booth j. The county fair's unusual layout means that perhaps FJ
could travel from booth i to booth j by a faster route if he were
to visit intermediate booths along the way. Being a poor map reader,
Farmer John never considers taking such routes -- he will only walk
from booth i to booth j in the event that he can actually collect
a fabulous prize at booth j, and he never visits intermediate booths
along the way. Furthermore, T(i,j) might not have the same value
as T(j,i) owing to FJ's slow walking up hills.
Farmer John starts at booth #1 at time 0. Help him collect as many
fabulous prizes as possible.
PROBLEM NAME: counfr
INPUT FORMAT:
* Line 1: A single integer, N.
* Lines 2..1+N: Line i+1 contains a single integer, P(i).
* Lines 2+N..1+N+N^2: These N^2 lines each contain a single integer
T(i,j) for each pair (i,j) of booths. The first N of these
lines respectively contain T(1,1), T(1,2), ..., T(1,N). The
next N lines contain T(2,1), T(2,2), ..., T(2,N), and so on.
Each T(i,j) value is in the range 1...1,000,000 except for the
diagonals T(1,1), T(2,2), ..., T(N,N), which have the value
zero.
SAMPLE INPUT (file counfr.in):
4
13
9
19
3
0
10
20
3
4
0
11
2
1
15
0
12
5
5
13
0
INPUT DETAILS:
There are 4 booths. Booth #1 is giving away a prize at time 13, booth #2
at time 9, booth #3 at time 19, and booth #4 at time 3.
OUTPUT FORMAT:
* Line 1: A single integer, containing the maximum number of prizes
Farmer John can acquire.
SAMPLE OUTPUT (file counfr.out):
3
OUTPUT DETAILS:
Farmer John first walks to booth #4 and arrives at time 3, just in
time to receive the fabulous prize there. He them walks to booth
#2 (always walking directly, never using intermediate booths!) and
arrives at time 8, so after waiting 1 unit of time he receives the
fabulous prize there. Finally, he walks back to booth #1, arrives
at time 13, and collects his third fabulous prize.
**********************************************************************
Problem 7: County Fair Events [Russ Cox, 2006]
Farmer John has returned to the County Fair so he can attend the
special events (concerts, rodeos, cooking shows, etc.). He wants
to attend as many of the N (1 <= N <= 10,000) special events as he
possibly can.
He's rented a bicycle so he can speed from one event to the next
in absolutely no time at all (0 time units to go from one event to
the next!).
Given a list of the events that FJ might wish to attend, with their
start times (1 <= T <= 100,000) and their durations (1 <= L <=
100,000), determine the maximum number of events that FJ can attend.
FJ never leaves an event early.
PROBLEM NAME: events
INPUT FORMAT:
* Line 1: A single integer, N.
* Lines 2..N+1: Each line contains two space-separated integers, T and
L, that describe an event that FJ might attend.
SAMPLE INPUT (file events.in):
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
INPUT DETAILS:
Graphic picture of the schedule:
11111111112
12345678901234567890
--------------------
111111 2222223333344
55555555 777777 666
OUTPUT FORMAT:
* Line 1: A single integer that is the maximum number of events FJ can
attend.
SAMPLE OUTPUT (file events.out):
4
OUTPUT DETAILS:
FJ can do no better than to attend events 1, 2, 3, and 4.
**********************************************************************
Problem 8: The Climbing Wall [Rob Kolstad, 2006]
One of the most popular attractions at the county fair is the
climbing wall. Bessie wants to plan her trip up the wall in advance
and needs your help.
The wall is 30,000 millimeters wide and H (1001 <= H <= 30,000)
millimeters high and has F (1 <= F <= 10,000) hoof-holds at unique
X,Y coordinates expressed in millimeters. 0,0 is at the ground level
on the left side of the wall. Hoof-holds are separated by at least
300 millimeters since no cow can maneuver them if they are spaced
too close! Bessie knows there is at least one way up.
Bessie, through techniques only she knows, uses successive single
hoof-holds to climb the wall. She can only move from one hoof-hold
to another if they are no more than one meter apart. She can, of
course, move up, down, right, left or some combination of these in
each move. Similarly, once she gets to a hoof-hold that is at least
H-1000 millimeters above the ground, she can nimbly climb from there
onto the platform atop the wall. Bessie can start at any X location
that has a Y location <= 1000 millimeters.
Given the height of the wall and the locations of the hoof-holds,
determine the smallest number of hoof-holds Bessie should use to
reach the top.
PROBLEM NAME: wall
INPUT FORMAT:
* Line 1: Two space-separated integers, H and F.
* Lines 2..F+1: Each line contains two space-separated integers
(respectively X and Y) that describe a hoof-hold. X is the
distance from the left edge of the climbing wall; Y is the
distance from the ground.
SAMPLE INPUT (file wall.in):
3000 5
600 800
1600 1800
100 1300
300 2100
1600 2300
INPUT DETAILS:
The wall is three meters high with 5 hoof-holds.
OUTPUT FORMAT:
* Line 1: A single integer that is the smallest number of hoof-holds
Bessie must use to reach the top of the climbing wall.
SAMPLE OUTPUT (file wall.out):
3
OUTPUT DETAILS:
Bessie can start on the ground, move to the hoof-hold at (600,800), move
from there to (100,1300), move from there to (300,2100), and from that high
height can hop onto the platform. This trip requires three hoof-holds.
There is no shorter path that Bessie can take.
**********************************************************************