A Contest Between Friends
Spring Programming Competition
February 23, 2008 /
A Contest Between Friends
- Are You My Friend?(friend1)
- A Sign of the Times?(sign)
- Auto Selection(auto)
- Bigger Better Bowling(bowling)
- ClocksGoing Cuckoo(clocks)
- Dice Going Clockwise(dice)
- Desired Drug Dosing(drug)
- Divisible Dot Product(product)
- ISBN Conversion(isbn)
- Who is My Friend?(friend2)
The name in parenthesis following each problem is the name you must use as your program’s name. You must add the appropriate extension depending upon your choice of programming language (.c .cpp .java .py).
Are You My Friend?
February is the month of love and friendship. Numbers can be friends too. It is said that when Pythagoras was asked "What is a friend?", he replied that a friend is one "who is the other Isuch as are 220 and 284."
One definition of friendly numbers says that two numbers are called friendly if each is equal to the sum of the proper divisors of the other. Recall that proper divisors are all the divisors excluding the number itself. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110. The proper divisors of 284 are 1, 2, 4, 71, and 142.
If we represent a pair by (m, n) and the sum of the proper divisors of m and n by σ (m) and σ (n) respectively, then for (220, 284) we get
σ (m) = σ (220) = 1+2+4+5+10+11+20+22+44+55+110 = 284 = n
σ (n) = σ (284) = 1+2+4+71+142 = 220 = m
It can be seen that each partner in a friendly pair has the power to generate the other, thus symbolizing mutual compatibility, harmonious friendship, and perfect love. Your task is to determine if a pair of numbers are friends.
Input
The input to the problem will begin with a positive integer c, which is the number of cases. Each case will consist of two positive integers, nand m,n < 1,000,000 and m1,000,000.
Output
For each case, print out n and m and a message indicating whether or not they are friendly using the format in the sample output.
Sample input
3
220 284
42 24
284 423
Output corresponding to sample input
220 and 284 are friendly
42 and 24 are not friendly
284 and 423 are not friendly
A Sign of the Times?
All US national parks have signs along their roads stating the elevation of the road. EvergladesNational Park is no exception, although it is a bit lower than most of the others. So it has a sign about halfway between the welcome station and Flamingo with the information “RockReefPass: Elevation 3 feet”. This sign is uncharacteristically large, starting exactly 4 feet off the ground and being exactly 6 feet in total height including the post. Note: the “Elevation 3 feet” refers to ground level. Since this is at an elevation of 3 feet, the bottom of the post is 3 feet above sea level.
It has been claimed that the oceans are currently rising at the rate of 1.5 millimeters (mm) per year. If this is so, in what year will the sign have water touching the bottom of its post (i.e. ground level)? be completely underwater? What if the oceans rise at a slightly higher rate each year?
The conversion from millimeters to inches is:1 millimeter = 0.0393700787 inches.
Input
The input will contain one or more data sets. Each data set will be one line, with two real values, initial, the initial rise in sea level in mm per year and change, the percentage increase per year, with initial > 0.0. The file will end with a line containing initial = 0.0 which you should not process.
Output
Your program must output the case number (starting at 1) and the years in which the water touches the bottom of the signpost (that is, completely covers the ground) and covers the entire sign, formatted as shown in the sample output. You should assume that the water is at sea level in 2008 and increases by the percentage given by initial in 2009, then increases over the 2009 value by the percentage given by change in 2010, and so forth until the level is over the sign. The water level at the sign is only checked once per year, so even if the water rises above the sign in a given year, it will not be reported until the sign is checked the next year. You may assume that the water will always cover the sign at some point in time.
Sample Input
5 0.05
3 0.02
0.0 0.0
Output corresponding to sample input
Case 1: reaches post in 2056, covers sign in 2077
Case 2: reaches post in 2107, covers sign in 2158
Auto Selection
My car radio has a SELECT button that scans the local airwaves and determines the six strongest FM stations. It then sets the six buttons on the radio to those stations in order of ascending frequency. If there are fewer than six stations on a scan, the remaining buttons are set to display the letter A. Once the stations are set, the radio is set to the station that has the strongest signal. Sometimes the radio can find no stations. In that case, all buttons are set to display the letter A and the first button is the one that is selected—that is, the first button is set as though that station had the strongest signal.
Whenever a tie needs to be broken between two or more stations with the same signal strength, the one with the lowest frequency will be selected. So, if there are two stations with the same highest signal strength, the one with the lower frequency will be preset.
Write a program that determines what the button settings are for a given set of scan data.
Input
The input consists of one or more sets of scan data. Each set starts with an integer n, 0 n < 30, the number of stations that my radio scans. There are then n lines, each containing two positive floating point numbers:
<frequency> <signal strength>
No frequency will appear more than once in a set of scan data.
End of input is indicated by end of file (EOF).
Output
For each scan data, output the data set number starting at 1 (i.e. ‘Set number 1’). On the following six lines display the frequencies that will be set on the six buttons on the radio, in order from left to right. The selected frequency is followed by *. If fewer than six stations are available, an A is displayed. One blank line appears after the output for each data set.
Sample input
3
91.1 14.2
92.3 0.7
90.4 12.2
8
91.1 14.2
92.3 0.7
90.4 12.2
93.1 14.2
103.3 0.2
88.4 13.2
101.1 0.5
99.5 10.4
Output corresponding to sample input
Set number 1
90.4
91.1*
92.3
A
A
A
Set number 2
88.4
90.4
91.1*
92.3
93.1
99.5
Bigger Better Bowling
Mr. Miller, the owner of a prosperous bowling alley, wants to expand to more bowling-type games. Mr. Miller thinks he can make more money with a lane that has a variable number of pins. Traditional lanes have 10 pins on four rows (as shown on the right), 1 on the closest row, 2 on the second row, 3 on the third row and 4 on the fourth row.
To accomplish this, Mr. Miller decided to reduce the size of the pins so that more than 4 pins would fit across the last row. The new lane will have a menu that allows bowlers to choose how many rows of pins they would like to play with and how many pins should fit across the back row. To do this Mr. Miller needs a program that can take the input from the bowler and return the total number of pins needed so that the pin dispenser can place the correct number of pins at the end of the lane.
Sometimes a bowler will select a number of rows so that a full row will fit across the lane, as in the example on the left (six rows and six across the back row). Other times a bowler may want more rows than pins across the back row, as shown in the example on the right (six rows and five across the back row).
Input
The input will consist of a list of integers, two per line, rows and pins, 0 < rows < 100,000, 0pins100,000. rows is the number of rows the bowler wants and pins is the maximum number of pins that will fit across the lane.
Input will be terminated with a line containing only 0 0, which should not be processed.
Output
For each line of the input (except the terminating case, 0 0), your program should output how many total pins will be needed in the following format (case-number starts at 1).
case-number: X pins are needed for rows rows.
Sample input
4 6
6 6
6 5
0 0
Output corresponding to sample input
1: 10 pins are needed for 4 rows.
2: 21 pins are needed for 6 rows.
3: 20 pins are needed for 6 rows.
Clocks Going Cuckoo
Unfortunately, the power goes out in my home frequently, often when I’m out. When I get back, the clocks in my home are in disarray – but I can figure out some things about the power outage from them.
I have several clocks, which behave differently when the power goes out. In particular:
- My Watch is, of course, completely unaffected.
- My Alarm clock is electronic. When the power comes back on, it resets to midnight, and keeps time from there.
- My Stove clock is motorized with hands – when the power goes out, it stops at that time, and picks up from that time when the power comes back on.
For example, if the power goes out at 8:30am, and it comes back on at 9:30am, and I get home at noon, then:
- My Watch reads 12:00pm
- My Alarm clock reads 2:30am
- My Stove clock reads 11:00am
The Problem
Given the times on these three clocks, determine the time that the power outage started, the time that it ended, and the length of the outage in minutes. You may assume that there was exactly one power outage, that it lasted at least 1 minute and no more than 24 hours, and that the clocks will be consistent. Note that my Stove clock, despite having hands, is still a 24-hour clock, not a 12-hour clock.
Input
The first line of input will have a single integer n, indicating the number of cases to follow. On each of the next n lines, there will be three times separated by a single space:
Watch Alarm Stove
Each time will be in this format:
hh:mm[am|pm]
Where:
- hh is the hours, 1 <= hh <= 12. Hours less than 10 will NOT have a leading zero.
- mm is the minutes, 00 <= mm <= 59. Minutes less than 10 WILL have a leading zero.
- [am|pm] is either the string “am” or the string “pm”, always in lower case.
There will be no spaces in a time.
Output
For each case, print a single line:
Day number day: start end duration
where day is the number of the case in the input set, start is the start time of the power outage, end is the end time, and duration is the duration of the outage. The times start and end should be printed in exactly the format described in the inputsection. The duration should be an integer representing the number of minutes that the power was out. There should be no blank lines in the output.
Sample Input
2
12:00pm 2:30am 11:00am
5:00pm 4:00am 3:00pm
Output corresponding to sample input
Day number 1: 8:30am 9:30am 60
Day number 2: 11:00am 1:00pm 120
Dice Going Clockwise
Regulation Dice are cubes, with each of the numbers 1 through 6 on exactly one face. Additionally, to be Regulation, the numbers on opposite faces of the die must total 7. So, the 1 must be opposite the 6, the 2 must be opposite the 5, and the 3 must be opposite the 4.
With these constraints, on any Regulation die, it is guaranteed that the 1 face, the 2 face and the 3 face must all meet at some vertex. If, looking at that vertex, the numbers 1, 2, 3 go Clockwise around the vertex, the die is called a Clockwise die. Otherwise, it is called a Counterclockwise die.
The Problem
Given the faces of a die, determine if it is Clockwise, Counterclockwise or Not Regulation.
Input
Each line of input will have six integers, in this order:
Front Back Left Right Top Bottom
The integers are guaranteed to be in the range 1 through 6, except for the last line, which will be all 0’s, will mark the end of input, and should not be processed.
Output
For each case, print a single line containing the die number (starting at 1) and one of the following:
ClockwiseorCounterclockwiseorNot Regulation
There should be no blank lines or extraneous spaces in the output.
Sample Input
1 6 4 3 2 5
1 6 5 2 3 4
1 2 3 4 5 6
1 1 1 1 1 1
0 0 0 0 0 0
Output corresponding to sample input
Die 1: Clockwise
Die 2: Counterclockwise
Die 3: Not Regulation
Die 4: Not Regulation
Desired Drug Dosing
For years, drugs have been prescribed with dosages like 400 milligrams (mg) every 4 hours. But why every 4 hours? Perhaps it would be better for patients to have the drug every 217 minutes, but asking sick patients to worry about timing like that is too difficult.
Fortunately, we live in a computer age and can use programs to determine when drugs should be administered. All substances have a biological half-life, the amount of time it takes the body to remove half of the substance from the body. This assumes that the drug is removed at an exponential rate, so after 1 half-life, only ½ of the drug would be left, after 2 half lives, only ¼ of the drug would be left, and, in general, for i, any non-negative value (possibly rational!), after i half-lives, only of the drug would remain in the patient's body. (In fact, the real rate at which drugs are removed is much more complicated, but we will only consider the biological half-life for this problem.)
Consider a drug with a half-life of 40 minutes. If an initial dosage of 400 mg was given, after 40 minutes, the body would remove half of the drug, so only 200 mg would be left. After 60 minutes, there would be (or approximately 0.35356) of the initial dosage or approximately 141.42 mg. After 4 hours, there would be of the initial dosage, or 6.25 mg left. If the person took another 400 mg 4 hours after the first, there would then be 406.25 mg in the patient's system.
Given the times and levels of previous drug administrations, a drug's biological half-life, and the desired minimum level, your program should determine the earliest time at which the patient has a remaining dosage that is less than or equal to the minimum desired dosage.
Input
Input to your program will be one or more data sets.
Each data set will begin with two lines of drug information. The first will have the name of the drug, a string of 1 or more characters. The second will have two positive integers. The first is the size (in mg) of one dose and the second is the biological half-life, in minutes.
After the drug information, there will be one or more patient sets. Each patient set will begin with 2 lines, the first with the patient name, a string of 1 or more characters, and the second with two positive integers, the desired minimum level (in mg) for the patient, and the second the number of previous doses, n. There will then be n lines describing the previous doses in the form:
day:hour:minute doses
where day, hour, minute, and doses are all integers, with 0 ≤ day < 100, 0 ≤ hour < 24, 0 ≤ minute < 60, and 0 < doses. These lines will be in chronological order.
The last patient set will be followed by the line containing just "LAST PATIENT". The last data set will be followed by the line containing just "LAST DRUG".
Output
For each data set, print a single line with the name of the drug and then one line of output from each patient set. For each patient’s data set, print the patient's name and the earliest time after the last dose at which the patient will be below the minimum level. Minutes and hours should always be printed with 2 digits. Use the format in the sample output below.
Sample input
Problem Example
400 40
Patient 1
10 1
0:10:20 1
Patient 2
50 5
0:10:00 1
0:10:40 2
0:11:20 1
0:12:00 1
0:12:40 2
LAST PATIENT
Easy Drug
100 60
Needs high level
100 2
0:01:00 1
0:02:00 1
LAST PATIENT
LAST DRUG
Output corresponding to sample input
Problem Example
Patient 1 0:13:53
Patient 2 0:15:45
Easy Drug
Needs high level 0:02:36
Divisible Dot Product
The dot product of two vectors is found by multiplying their elements component wise and summing all the results. So, if v and w each have n elements, then
v · w = v1w1 + v2w2 + v3w3 + … + vnwn
Consider the vectors v = (2, 1, 3) and w = (6, 2, 4). The dot product is 26 (since 26=2*6+1*2+3*4).
A permutation of a vector is a rearrangement of its elements. Mathematically, v’ is a permutation of v if and only if
v’ = vp1, vp2, vp3, … , vpn,
where 1pin, and pipj whenever ij.
Notice that permutations will usually change the dot product. Although v · w in the previous example is not divisible by 7, the dot product of the permutation w' = (4, 2, 6) and v is 28, which is divisible by 7.
Given two integers n and m and two vectors v and w, each with n elements, find the lexicographically least permutation of w, call it w’, such that v · w’ is divisible by m. A vector x is lexicographically less than a vector y if there is an index i such that xi yi and xj = yj for all ji.
Input
The input will consist of one or more test cases. The first line of each test case will contain two integers n and m, where 1n 15 and 1m 200. The next two lines will each consist of n positive integers less than 10,000 separated by single spaces, representing the elements of v and w, respectively.