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
Download 81.63 Kb.
|
- Navigate this page:
- Numeric Palindromes
- Roach Invasion
- Check Protect
| 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$
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$
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 0 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$
2 222$
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
The input is followed by n lines of: x - y z
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
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$
VALID$
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
3 4 3
3 0 3
3 0 1
1 0 1
0 0 1
0 0 0
3 0 3
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$
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:
Numeric PalindromesA 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 4$ 1$ 49$ 69$ 86$ output.txt 0 1$ 2 484$ 4 4884$ 3 1111$ Roach InvasionOn 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 anti-roach 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 3In 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 ProtectIn 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$
****$12.34$ ***$123.45$ *$1,234.56$ $12,345.67$ *****$0.10$ *****$0.01$ *$1,234.50$
As an example, if the account number is 49927398716, it will be validated as follows:
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 so-called 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 penciled-in 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$
5$ Directory: downloads downloads -> Northern England’s set-jetting locations downloads -> Dynatest 3031 lwd light Weight Deflectometer downloads -> Forth coming competitive exams downloads -> Brush High School Morning Announcements Friday, September 05, 2014 all school downloads -> Year 9 The Arts — Music downloads -> Years 7 and 8 standard elaborations — Australian Curriculum: Music draft downloads -> Chris Young sets 2016 “I’m Comin’ Over” Tour headlining dates downloads -> Slavery and Abolition: the Plymouth Connection Introduction downloads -> Summer Assignment Download 81.63 Kb. Share with your friends:
|