As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
link to let me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
e-mail with your comments about this program (or anything else).
Another ACM Programming Contest problem. Here it is
just the way the contestants saw it:
Why did the chicken cross the road? Well, that is not our concern. We only seek
to make sure that it gets across safely.
The chicken will cross several roads (anything from Farm-to-Market roads to interstate
highways including access roads). For each road to cross, the chicken looks
to see how many lanes there are to cross and what traffic there is on each lane.
The chicken then starts waiting for traffic to clear so it can cross safely. In order to
maintain the timing between steps and his head-bobbing, the chicken will only start
walking on 1 second intervals. However, this chicken is particularly impatient and
will start walking whether it is safe or not after waiting only 60 seconds and it
may be time to break out the barbeque sauce.
When the chicken does cross the road, it will start walking on a path perpendicular
to the lanes (all lanes are parallel) at a constant rate of 10 feet/second and will not
stop until reaching the other side. All lanes are 15 feet wide and there is no room
between the lanes. Each vehicle description includes a width in feet of the vehicle
(0<W<=15 feet), the length of the vehicle (0<L<=40 feet), a constant speed of the
vehicle in feet/second (0<S<=100 feet/second), and the time (in seconds) which
the vehicle will cross the line which the chicken will attempt to walk along.
Second zero is the first opportunity for the chicken to start across the road. Vehicles
always drive down the exact center of the lane they occupy (no drunk drivers here!).
Information for each crossing will be formatted in the input file as follows.
The first line for each crossing will contain the number of lanes (1<=L<=20) to be crossed
(direction does not matter here). The second line contains the number of vehicles
(0<=N<=100) involved in the crossing. Each of the subsequent N lines contains the
description of the vehicles in no particular order. The first value of the line
is an integer which identifies the lane number (1 to L) the vehicle occupies
(lane 1 is closest to the chicken). The second through fifth values are floating
point numbers which identify the width, length and speed of the vehicle and the
time (in seconds) that the vehicle will cross the line the chicken will walk
along. You must read to the end-of-file.
You may assume that there are no lane changes; collisions between vehicles are
irrelevant; and sufficient safety margin has been included in the dimensions of the
vehicle to treat the chicken as a single point. It is time to get the barbeque
sauce if at any time any part of the vehicle and the single point of the chicken intersect.
For each road to cross, you must output the crossing number (start counting at
one) and an integer representing the earliest second (0 to 60) the chicken should start
to cross such that it can cross safely. If the chicken cannot cross safely, you
must print the message "Bar-B-Q time!" instead of the crossing start time. Your output
should be formatted similar to that in the examples below.
2 5.0 6.3 12.0 47.7
1 14.5 39.6 66.0 29.3
2 14.8 40.0 9.0 4.8
1 11.1 40.0 100.0 24.3
1 9.0 14.2 83.6 2.1
1 9.0 15.0 88.0 1.1
2 12.6 29.9 80.67 19.25
1 3.0 6.0 40.0 10.6
4 15.0 40.0 0.1 4.4
2 15.0 40.0 0.1 4.4
Crossing 1 should start at 8.
Crossing 2 Bar-B-Q time!
Crossing 3 should start at 0.
Background & Techniques
This problem is from the 1993 Southeastern Regional ACM
Programming Contest. I decided to solve this as a console
application mainly because I had never written one before and secondarily
because that's the way all ACM Programming Contest programs must be
written. The easiest way to create a console program is to click on the Delphi
menu option File/New/Console Application. Console apps have no form
and no corresponding unit, only the .dpr member is generated. Main
program code lies between Begin and End. statements. Readln
and Writeln functions can be used to read and write lines to the
console. A Readln function with no parameters is
commonly used at the end of a program to force it to pause while the user reads
the output screen until the user presses the Enter
For this problem, the total number of lanes information
seems redundant. Here's how I approached the
problem. A TTruck class was created to contain lane
number, length, width, speed and time of arrival (toa)
fields for each truck. An additional time of departure (tod)
field was calculated based on time of arrival plus time for the truck to pass,
based on its length and speed. tod=toa +
To find a valid start time we'll just try all possible
start times from 0 through 60 seconds. For each start time, for each truck,
we'll check whether the chicken and the truck try to occupy the same space
at the same time. If, for a particular start time, we check all trucks and find
no conflicts, that time is the solution. If they do conflict, we'll
try the next start time. If all times are tried without finding a clear path,
display the "Bar-B-Q" message. To check for conflicts,
compute time of chicken arrival (toca) and time of chicken departure (tocd)
for each truck. Since the chicken travels at a constant speed, and the
truck travels down the center of its lane, distance to the near and far
sides of the truck divided by the chickens speed will give us the desired
times. The equations are: toca:=starttime +
tocd:=toca+truckwidth / chickenspeed; If the chicken
leaves the truck spaces before the truck arrives (tocd<toa) or the
chicken arrives at he truck space after the truck has departed (toca>tod),
then he is safe. If there's a conflict (i.e. both of the above test are
false), we'll stop checking this time and try the next. If we check all
the trucks for a particular time without finding a conflict, that is the
Running/Exploring the Program
Suggestions for Further Explorations
A visual animated version that showed the trucks
moving and the chicken crossing would be cool and and not very difficult