ACM Programming Contest

ACM Programming Contest

DixieState 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:

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$

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 home-world!

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 all-you-can-eat 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 Faster-Than-Light hyper-drives 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_{n-1} y_{n-1} z_{n-1}

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 light-years. 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 0i<n 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 one-way 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 non-padded data, if you have 2 octets of the 24-bit buffer as padded-zeroes, 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:

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 1-7, 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: 0<N<P<1,000,000,000. After the first line, each line in the input file will produce a line in the output file with two numbers, the number of cycles to find P, and the value of P, separated by a single space.

input.txt

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.