ACM Programming Contest
Dixie State College
Spring, 2009
(Do NOT turn this page until time.gov says it is 10:00 am Mountain Standard Time!)
Table Of Contents:
Vowels (High School Only)
Histogram (High School Only)
Incoming
Power Grid
Base 64
Sticks Game
Magic Numbers
Palindromes
Roach
Top 3
Check Protect
Luhn
Naked Sets
Vowels (High School Only)
Write a program that reads a very large word from input.txt, and writes to output.txt how many vowels are in that word. Vowels include a, e, i, o, and u, but never y. The vowels may be lowercase or uppercase. The length of the word will not be more than 100 characters, and will only contain capital and lowercase letters.
Consider the following example. Remember that the ‘$’ symbol indicates the placement of a line feed, and should not be part of the actual input or output.
input.txt:
ComputerScience$
output.txt:
6$
Histogram (High School Only)
Write a program that reads a sequence of up to 1000 integers from input.txt, and writes to output.txt a histogram of how frequently each of the numbers from 1 to 9 showed up. The first line of input.txt indicates how many numbers follow, and will not be bigger than 1000. Each subsequent line contains one number between 1 and 9. Note that the number on the first line is only to indicate the count of numbers to follow, and should not be part of the histogram calculation.
Consider the following example, and make sure your output file exactly matches the format of the sample output.txt file below, character for character. That is, each line of output should have the number being counted, followed by 1 colon, followed by one space, followed by how many times that number showed up, followed by 1 line feed. Remember that the ‘$’ symbol indicates the placement of a line feed, and should not be part of the actual input or output.
input.txt:
13$
7$
2$
4$
8$
1$
2$
7$
8$
9$
1$
3$
4$
8$
output.txt:
1: 2$
2: 2$
3: 1$
4: 2$
5: 0$
6: 0$
7: 2$
8: 3$
9: 1$
Incoming!
Alas! An enemy ship is on its way to your homeworld!
You have received information detailing a massive enemy warship which has discovered the location to your planet. The aliens piloting it see your race as nothing but cattle to be fed upon and your world is an allyoucaneat buffet of 6 billion morsels. Luckily, your people have been informed of the threat and can respond.
It is known that the enemy ship's FasterThanLight hyperdrives need to be shut off every few hours for recharging. Luckily, your ships do not have to deal with that weakness. Thus, you can fly straight from your planet to any point in space at your maximum velocity. You spies have received the speed of their ship, and the coordinates of its planned recharging points in the vast space between its home galaxy and your own. You must find a suitable time to ambush the enemy ship.
Given the following input:
v1 t v2 n
x_0 y_0 z_0
x_1 y_1 z_1
.
.
.
x_{n1} y_{n1} z_{n1}
where v1 is the speed of the enemy ship in light years per hour, t is the time the enemy ship requires to recharge in hours, v2 is the speed of your ship in light years per hour and n is the number of stopping points of the enemy ship. x_a,y_a,z_a form a coordinate in 3d space where 0,0,0 is your home world and your launch point. The first set of coordinates is the enemy launch point. Coordinates are in lightyears. You may assume they did not need to charge at their launch point. The final point will always be your home world.
Return the first index i in the list at which you can arrive before the enemy ship to ambush them and your flight time to that location, rounded to the nearest hour. Your output should be a number 0n followed by the number of hours your ship will have to travel rounded to the nearest hour. In the sample problem below, your ship can arrive at location 2048,2048,2048 before their ship.
All input numbers will be positive integers less than 2^16.
n will be less than 1024
input.txt:
16 1 16 5$
4096 4096 4096$
3072 3072 3072$
2048 2048 2048$
1024 1024 1024$
0 0 0$
output.txt:
2 222$
Power Grid
You are working on an engineering team aboard an unbelievably old spacecraft. The craft, designed to literally be a city in space has been through tens of thousands of years of battles, neglect and use.
After you and your team came into possession of this city and began repairing it, you have a power maintenance conundrum to face. You do not have any of the power sources that the city was designed to use. Instead, you have much less powerful portable reactors. You can place these reactors at critical points on the power grid so that key systems are fed sufficient power.
The ancient power conduits add a level of complexity to the problem. Each has some level of power loss, through damage or simple laws of physics.
The situation is further complicated by the fact that you are cut off from your supply base and have limited reactors to power the city. Several suggestions have been made as to where to put the power reactors. You must write a program to quickly and efficiently determine the validity of a proposed solution.
The power grid is represented in your database as conduits between numbered junctions. Assume there are 10,000 junctions, indexed between 0 and 9999, though not all junction numbers are necessarily used. Any given junction is either a power source, a power consumer, or just a pass through. A junction cannot be a power source and a power consumer.
Conduits are oneway and there are no feedback loops. (no output feeds into itself through any means)
All key systems that must be powered (consumers) are at a numbered junction with no outputs.
All power sources are at numbered junctions that may have both input and output conduits. The total output of a power source junction is the sum of all power feeding into it, plus its own power.
Conduits can transmit any amount of power you are capable of generating.
Junctions transmit the same amount of power on every output. For instance, if a junction has 3 outputs, each will have 1/3 of the original amount transmitted on it.
Given the input:
n m k
n is the number of conduits, m is the number of junctions with reactors (sources) and k is the number of key system junctions (consumers).
The input is followed by n lines of:
x  y z
where x and y are each junction numbers (between 0 and 99999), and z is the power lost as a percentage of all power transmitted across the conduit. Flow is from x to y.
Followed by m lines of:
p g
where p is the junction number (between 0 and 99999) and g is the power output of the reactor at that node.
Followed by k lines of:
a b
Where a is the junction number (between 0 and 99999) and b is the amount of power the systems on that junction require.
Junctions numbers that are “pass through” (neither source nor consumer) are not included in either junction list, but may be included in the conduit list.
Determine if the solution is workable in that all power requirements are met. Print “VALID” for working solutions and “INVALID” otherwise.
Note that in the first sample case below, power starts and junction 0 with output of 1000. 90% of that makes it to junction 1, and 90% of what’s left makes it to junction 2. Thus, junction 2 ends up with 810 units of power, which is more than the 800 it needs.
In general, the solution is VALID if all consumer junctions get at least as much power as they need.
Note that since one input file can only test one configuration for validity, the judges will be using several input files to test your code.
input.txt:
2 1 1$
0  1 .100$
1  2 .100$
0 1000.0$
2 800.0$
output.txt:
VALID$
Base 64 Encoding
Implement base64 encoding on some text. Base 64 encoding has many different applications. One of these is the encoding of MIME attachments for email. For example, a picture that you attach to an email is first encoded as base64 before it is sent. For the program below you will encode some text using base64 encoding.
A sample of unencoded text: (Including the quotes, no CRLF at end of line).
"The more I C, the less I see."
The sample text encoded using base64 follows:
IlRoZSBtb3JlIEkgQywgdGhlIGxlc3MgSSBzZWUuIg==
How do you do it?
Read each byte of the input file one character at a time. Convert each character of the input file to 8 binary bits. Three of these bytes are joined together in a 24 bit buffer. The 24 bit buffer is then separated into 4 packs of 6 bits each. Packs of 6 bits (6 bits have a maximum of 64 different binary values) are converted into 4 numbers (24 = 6x4) which are then converted to their corresponding values in Base 64, using the base64 alphabet.
The alphabet for base 64, is as follows:
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" (not including the quotes).
If there are fewer than 3 bytes (24 bits) left to encode, the input data is right padded with zero bits. After you encode the nonpadded data, if you have 2 octets of the 24bit buffer as paddedzeroes, two '=' signs are appended to the output. If only one octet, one '=' sign is appended to the output. The '=' will signal the decoder that the zero bits that were added as a result of padding, should be excluded from the reconstructed data.
An example from above:
The quote '”' is 0010 0010 in ascii binary (decimal 34).
T = 0101 0100 (84 ascii)
h = 0110 1000(104 ascii)
So our binary stream looks like this at this point:
001000100101010001101000 (24 bits)
Break them into groups of 6 and figure out corresponding decimal value and corresponding value from alphabet above.
001000 = 8 = I
100101 = 37=l
010001 = 17 = R
101000 = 40 = o
There you have the corresponding base64 encoded value.
You need to write a program that will take a stream of bytes in input.txt and convert it to base64 encoding using the rules outlined above, writing the result to output.txt. You can use the sample above to check your work.
The following sample code may help you open the input file and read characters one at a time until the end of file:
ifstream fin;
fin.open(“input.txt”);
Char c;
while(fin.get(c))
{
// process each character.
}
Sticks Game
“Sticks” is a two player game where the players take turns removing one or more sticks from one of three piles. Initially, there are 3 sticks in the first pile, 4 in the second, and 5 in the third. The winner is the player who removes the last stick.
The board can be represented with 3 integers, indicating the number of sticks currently in each pile. For example, the initial board is represented with the integers:
3 4 5
Suppose player 1 chose to remove 2 sticks from the third pile. The board would then be:
3 4 3
The “best move” for player 2 would then be to remove all the sticks from the second pile:
3 0 3
Then player 2 can force a win by simply matching whatever player 1 does to the opposite pile. For example, if player 1 removes 2 sticks from pile 3:
3 0 1
Then player 2 responds by removing 2 from pile 1:
1 0 1
Then player 1 must remove a stick from a remaining pile:
0 0 1
And player 2 can win by removing the last stick:
0 0 0
There is a trick to this game. Player 2 got the board to a “winning position” with:
3 0 3
From a winning position, no matter what the other player does, there is a counter move to return to another winning position. In fact, from the initial board, if player 1 had chosen the best move, a winning position could have been achieved. But player 1 made an incorrect move, allowing player 2 to gain a winning position, and hold onto it until victory.
A game engine is needed that inputs any board configuration and determines the one and only “best move” to set up a winning position, if possible. Of course, if the opposing player has already got a winning position then there is no best move, because you are already in a “losing” position.
The first line of the input file contains the count of how many board configurations follow. After that are several board configurations, one on each line. For each board configuration, your code should determine the best move and the resulting winning configuration. Print to the output file the original board configuration, followed directly by a colon and space, followed by the winning board configuration if possible, or by the word “losing”.
Each board configuration will have 0 to 3 in the first pile, 0 to 4 in the second, and 0 to 5 in the third. Each board configuration will have at least one stick in at least one pile. You will not be given any board configurations with the same number of sticks in all 3 piles, as that would result in multiple “best moves.”
input.txt:
4$
3 4 3$
0 2 0$
1 2 4$
3 3 0$
output.txt:
3 4 3: 3 0 3$
0 2 0: 0 0 0$
1 2 4: 1 2 3$
3 3 0: losing$
Magic Numbers
A simple magic trick for guessing a volunteer's number uses some specially prepared cards with numbers on them. Each card has a set of numbers. The volunteer secretly chooses a number from a given range, then examines each of the cards in the set. The volunteer then hands the cards that contain the chosen number to the magician. The magician holds the cards to her head and pronounces the volunteer's secret number.
The trick uses binary arithmetic to aid the magician. There is one card for each bit in the binary representation of the numbers. The number of cards required is determined by the number of bits necessary to represent the largest number. Each card only contains numbers in the given range that have the card's particular bit set in their binary representation. The magician just adds up the value of the bits that are set in the volunteer's numbers as the cards are handed to her.
For example, if the numbers are in the range 17, there will be 3 cards, because the largest number, 7, requires the 1, 2 and 4 bits to all be set. The first card will contain the numbers that require the 1 bit to be set in their representation: 1, 3, 5, and 7. The second card will contain the numbers that require the 2 bit to be set in their representation: 2, 3, 6, and 7. The third card will contain the numbers that require the 4 bit to be set in their representation: 4, 5, 6, and 7.
Your program will be required to make cards for a specified range of numbers. It will need to calculate the number of cards needed, and the numbers to be displayed on each card.
The input file will contain one line. The line will contain two numbers, N and M. N is the lowest number in the range, and M is the largest number in the range. The numbers will obey the constraints
0 < N < M < 2,000,000,000 and M – N < 8192.
The output file will contain a line with the number of cards to produce, followed by a line for each card. Each card line will contain a list of the numbers that will appear on the card. The numbers will be ordered from smallest to largest, and separated by a single space. The last number on the line may be followed by a space, but the space is not required.
Examples:
input.txt
1 7$
output.txt
3$ 1 3 5 7$ 2 3 6 7$ 4 5 6 7$

input.txt
7 18$
output.txt
5$ 7 9 11 13 15 17$ 7 10 11 14 15 18$ 7 12 13 14 15$ 8 9 10 11 12 13 14 15$ 16 17 18$
 Numeric Palindromes
A numeric palindrome is a number that reads the same forwards or backwards. For example, 747, 1221, and 555 are all numeric palindromes. By following a simple process, most numbers can be converted into palindromes.
The process is to take the original number, reverse the digits and add the two resulting numbers. For example, if the original number is 49, the reversed digit number is 94. If we add 49 and 94, the result is 143. This is not a palindrome yet, so we repeat, by reversing 143 to get 341, and adding. 143 plus 341 gives us 484. Shazam! We have a palindrome.
Some numbers require only one cycle of reverse and add. Others require 10, 20, or even more cycles.
Your program will be required to find the palindromes for a set of numbers. For each number, it will need to calculate the number of cycles and the resulting numeric palindrome.
The input file will contain multiple lines. The first line will contain a single number. This is the number of problems in the file. Each subsequent line will contain a number, N. N is the starting number. The program will calculate the palindrome, P, and the number of cycles required to find P . The numbers N and P will obey the constraint: 0input.txt
4$ 1$ 49$ 69$ 86$
output.txt
0 1$ 2 484$ 4 4884$ 3 1111$
Roach Invasion
On the alien planet, Nightfall, human settlers have run into a pesky native life form that is very similar to the cockroaches of Earth. Every night, the roaches swarm the food stockpiles. The alien roaches have an internal communication system that allows them to synchronize their attack waves. They only attack in groups.
The humans are not without resources however. They have an advanced motion detection system that allows them to know how many roaches will attack at any given minute through the night. They have also discovered a plant, native to Nightfall, that produces a natural poison that kills the alien roaches with no side effects to humans. This plant can be prodded to release its antiroach chemical at will. However, the number of roaches affected by the poison depends on the number of minutes since the last release of poison. Only roaches that arrive at the minute of the prodding are affected by the poison. The longer they wait, up to some maximum, the more roaches are killed by the poison. At the start of a set of attacks, the plant starts at the beginning of its charge cycle.
The humans can stomp on the roaches not killed by the poison, provided the number is low enough. They need a computer program that will take the list of numbers of roaches arriving each minute, and the number of roaches that can be killed by the poisonous plant, given the wait time. Then it needs to tell them when to use the poisonous plant to minimize the number of roaches that need to be stepped on.
For example, if the motion detector indicates that there will be roaches arriving in waves of { 6, 10, 3, 5, 1, 32 } over the next 6 minutes, and the plant is able to kill { 1, 2, 4, 8, 16, 32 } roaches after 1, 2, 3, 4, 5, or 6 minutes respectively, then the program needs to tell the humans which minutes to prod the plant, such that the number of roaches not killed by the plant is minimized.
If the humans prod the plan every minute, then one roach will be killed each minute by the poison, leaving (5 + 9 + 2 + 4 + 0 + 31 = 51) roaches to be squished. However, waiting until the sixth minute to prod the plant will kill all 32 in the last wave, leaving the humans with (6 + 10 + 3 + 5 + 1 + 0 = 25) roaches to squish. Your program must find the BEST timings.
The input file will contain four lines. The first line will contain a single number indicating the number of waves of roaches. The second line will contain a list of space separated integers, corresponding to the number of roaches to arrive at each minute. The number of waves will be less than 60. Each wave will have at most 100 roaches. The third line will contain a single number indicating the maximum number of minutes that the plant will charge (which indicates the number of integers on the forth line). The fourth line will contain a list of space separated integers, corresponding to the number of roaches killed by the plant after waiting 1,2,3,4 etc. minutes. The first number corresponds to a one minute pause, the second is for two minutes, etc. Wait times larger than the last position in this list only kill the number listed last. There will be at most 15 numbers in this list. No number in this list will be larger than 100.
The output file should contain one line. The first number on the line will be the total number of roaches that must be squished by the humans in the optimal solution. The rest of the line will be the minutes at which the plant must be prodded to produce this result. Each value on the line should be space separated. The last value may have a trailing space, but it is not required.
input.txt
6$
6 10 3 5 1 32$ 6$ 1 2 4 8 16 32$
output.txt
25 6$
input.txt
6$
2 12 7 5 3 6$ 4$ 1 2 4 8$
output.txt
27 2 6$
input.txt
21$
36 14 53 29 4 29 64 33 34 55 45 65 19 54 44 1 63 56 1 41 29$ 6$ 1 2 3 5 8 13$
output.txt
727 3 9 15 21$
Top 3
In this problem you will read in a list of students and their test scores. There will be a maximum of 50 students in the class. The students and their scores will be in random order. You will then decide the top 3 scores in the list and output the results to the output.txt file.
The input file (input.txt) consists of lines of text. The first field is the student’s name. The second field is the student’s test score. The first and second fields are separated by a space. The input file is terminated by the end of the file.
The output file (output.txt) consists of lines of text. The first number is the rank. The second field is the name of the student. The third is the test score. All fields are separated by a space.
input.txt:
bob 23$
jill 78$
bill 100$
george 99$
mary 98$
tim 45$
output.txt:
1 bill 100$
2 george 99$
3 mary 98$
Check Protect
In this problem you will be working for a bank. When printing checks, the check amounts need to be formatted and padded with an * in order to avoid fraud. Here are the rules:
1. All check amounts need to have exactly 10 characters.
2. All amounts must be preceded with a $.
3. All numbers must be formatted with 2 decimals on the right of the decimal.
4. All numbers must have a comma separating the thousands from the hundred.
5. All numbers less than one dollar must have a zero to the left of the decimal.
6. All preceding spaces need to be padded with an *.
The input file (input.txt) consists of lines of text. Each line is a number. That number ranges from 0 to 99,999.99.
The output file (output.txt) consists of lines of text. Each line is a formatted number string.
The symbol $ denotes a cr/lf.
Example:
12.34 > ****$12.34
123.45 > ***$123.45
1234.56 > *$1,234.56
12345.67 > $12,345.67
.1 > *****$0.10
.01 > *****$0.01
1234.5 > *$1,234.50
input.txt:
12.34$
123.45$
1234.56$
12345.67$
.1$
.01$
1234.5$
output.txt:
****$12.34$
***$123.45$
*$1,234.56$
$12,345.67$
*****$0.10$
*****$0.01$
*$1,234.50$
Luhn
The Luhn algorithm is a simple checksum procedure that is used to help detect typos when entering credit card (and other identity) numbers. In a 16digit credit card number (note the algorithm does not require 16 digits), the first 15 digits are chosen by the bank, and the last digit is computed according to the algorithm. Credit card machines, web sites, and other places that accept credit card numbers recompute the last digit by examining the first 15, and check that it matches the last digit entered. If so, it is likely that the number was entered correctly. If not, the interface can immediately signal an error and require the number to be reentered. It does not prevent fraud, but it does help to detect typos quickly and easily.
Assuming that you have the check digit (all 16 digits in our example), the algorithm works as follows (taken from Wikipedia):

Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.

Sum the digits of the products together with the undoubled digits from the original number.

If the total ends in 0 (put another way, if the total modulo 10 is congruent to 0), then the number is valid according to the Luhn formula; else it is not valid.
As an example, if the account number is 49927398716, it will be validated as follows:

Double every second digit, from the rightmost: (1*2)=2, (8*2)=16, (3*2)=6, (2*2)=4, (9*2)=18.

Sum all digits (digits in parentheses are the products from Step 1): 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70.

Take the sum modulo 10: 70 mod 10 = 0; the account number is valid.
Your task is to compute the correct final digit for a series of account numbers (of varying length) so that the number is valid according to the Luhn formula.
The first line of the input file will be a positive integer, indicating how many account numbers you must complete. Each account number will be on a line by itself, and missing the file digit. You must compute that final digit, and write the complete account number to the output file, one number per line.
input.txt:
5$
4992739871$
123456789$
819281716264023$
33333333333333$
888888888888888$
output.txt:
49927398716$
1234567897$
8192817162640237$
333333333333337$
8888888888888888$
Naked Sets
The game of Sudoku is played on a 9x9 grid where some spaces have a single digit (1 through 9) and others are blank. The player's task is to fill in the blank entries such that the same digit is not repeated in any single row, column, or 3x3 family (9 of which exist in the larger board).
One common strategy in solving Sudoku puzzles is to find socalled naked sets. The player first pencils in which digits could go in each blank position, then starts eliminating candidates that would create conflicts. For example, a row may already contain a 5, so the player would remove 5 from the penciledin candidates for every other space on that row.
A naked set occurs when the pencil marks for any n positions in one group (either a single row, a single column, or a single family) consist entirely of subsets of the same group of n digits. When this occurs, those n digits must be distributed through those n positions, so they can be removed from the pencil marks for the other positions in that group.
For example, if three positions in a column have pencil marks for (1, 4), (4, 7), and (1, 7) respectively, then those three positions in the column must ultimately be filled in with 1, 4, and 7 (in some order). Since they must be “used up” in those three positions, they cannot occur anywhere else in the row.
Note that a position whose final digit is known is a special case of this rule where n is one.
Your task is to read a series of pencil markings from the 9 positions of a single group (they could be taken from a single row, a single column, or a single 3x3 family), and to eliminate any pencil markings that can be removed by considering naked sets. No other marks should be removed.
The input file will consist of exactly 9 lines. Each has the penciled in digits for a single position in a group. You must remove any pencil marks you can using naked sets, and write the result to the output file. The digits for each position must be in increasing numerical order.
input.txt
2$
239$
39$
4$
1289$
6$
7$
1389$
5$
output.txt
2$
39$
39$
4$
18$
6$
7$
18$
5$
Share with your friends: 