Transcript
DKC3 2013 SHORT COMPUTING PROBLEMS
1. Linker
(15 pts)
A linker is a program that combines compiled object files of a program into an executable file, linking unresolved external name references (to subprograms or global variables) in one object file to their definitions in another. Most linkers have a facility for dealing with libraries—collections of object files— selecting a minimal set of object files out of a library so as to define all the outstanding unresolved names. The individual object files in the library may themselves reference unresolved names, so when the linker includes one object file from a library, it may have to include others as well. For this problem, you will write a program to determine what the minimal set is. Input The input to this program will consist of 10 test cases. A test case is consisted of a set of root names (strings separated by whitespace) for which definitions are to be found, followed by an isolated semicolon (i.e., a semicolon that is surrounded by whitespace), followed by a description of the contents of a library. This description consists of a sequence of object file directories, each having the form filename type1 name1 type2 name2· · · ; The filename and all the names are strings. Each type is either U, indicating that the following name is used in filename, but not defined, or D, indicating that the following name is defined in filename. Each object file directory ends with an isolated ‘;’. The input is in free format. You may assume file names are limited to 256 characters. You may assume that each required name is defined in exactly one library file. Each test case ends with a line consisting of only an asterisk “*”. Output The output consists of a list of the minimal set, S, of filenames from the library such that the root names and the type ‘U’ names from the files in S all have definitions (type ‘D’ names) among the files in S. List the result in the format shown in the example, in the order in which the file names appear in the description of the library. Separate the answer to each test case with a blank line. Input File: D:\DKC3\LinkerIn.txt Output File: D:\DKC3\LinkerOut.txt Examples: Input: print sin cos read ; files.o D close D open ; math.o D sin D cos U error ; diagnose.o D error ; format.o D printf D scanf ; input.o D read U close U error D seek ; output.o D print U error U close ; *
3
DKC 2013 Short Computing Problems
elog strequals read_order ; lol.o D teemo D garen U run_moba ; logging_lib.o D tlog D dlog D ilog D wlog D elog D flog U gettimestamp ; time_lib.o D gettimestamp ; string_lib.o D strequals D strcontains D strtrim U elog ; order_dao.o D create_order D read_order D update_order D delete_order ; * Output: files.o math.o diagnose.o input.o output.o logging_lib.o time_lib.o string_lib.o order_dao.o
2
3
DKC 2013 Short Computing Problems
2. Algebraic Expressions
(15 pts)
We can write simple algebraic expressions two dimensionally, like this: 2 x = x + (y - x )/2x n+1 n n n or we can write them in TeX format, like this: x_{n+1} = x_{n} + (y - x_{n}^{2})/2x_{n} In this problem, you are to convert the first form to the second. Input The input consists of up to three lines of text per test case, a superscript line (possibly empty), a main line, and an optional subscript line. Each superscript applies to the last character on the main line that is below and to its left. The lines contain only printing characters and blanks (no tabs). Each subscript applies to the last non-blank character on the main line that is above and to its left. You are to convert subscripts and superscripts to the notation illustrated above, with subscripts looking like _{...} and superscripts like ^{...}. When a character has both a subscript and a superscript, put the subscript first. Remove any blanks on the main line that have a sub- or superscript above or below them. Preserve any other blanks on the main line and within sub- or superscripts. There will be 10 test cases each separated by an asterisk “*”. Output For each input, write the TeX equivalent. Input File: D:\DKC3\AlgebraicIn.txt Output File: D:\DKC3\AlgebraicOut.txt Examples: Input:
2 x n+1
= x + (y - x )/2x n n n
* 3 x
2 = (x +(y-x) )/2x n n
* Output: x_{n+1} = x_{n} + (y - x_{n}^{2})/2x_{n} x^{3} = (x_{n}+(y-x)^{2})/2x_{n}
3
3
DKC 2013 Short Computing Problems
3. Bob’s Simple Sort
(5 pts)
Accounting has yet another task for Bob to solve for them. They have lists of integers that they need to be sorted in ascending order. Not only sorted but separated out into odds and evens. (I think they're just messing with Bob now.) Input Each line in the file will start with an identifier (which may contain numbers but no spaces) followed by a list of integers. Spaces will be used as separators. There will be 10 test cases. Output Each line should start with the identifier, followed by the ordered list of odd numbers and then the ordered list of evens. Everything should be space separated. Input File: D:\DKC3\SortIn.txt Output File: D:\DKC3\SortOut.txt Examples: Input: HiBob! 9 8 7 6 5 4 3 2 1 AccountingRulez55 23 1 100 29 201 Output: HiBob! 1 3 5 7 9 2 4 6 8 AccountingRulez55 1 23 29 201 100
4
3
DKC 2013 Short Computing Problems
4. Wrap Around Code
(15 pts)
In this program you will be given a set of letters to encode. The difference here is that different rules are used for different letters and the counting process starts where the last letter ends. Using the numerical value of each letter (A=1, B=2, … Z=26) the rules are as follows: If the letter is between the given letters, inclusive:
The number of letters to count is given by:
A-E
Multiply its numerical value by 2
F-J
Divide its numerical value by 3. Multiply the integer remainder by 5. Divide its numerical value by 4. Multiply the integer part of the quotient by 8 Multiply the sum of the digits of its numerical value by 10 Find the largest integer factor of its numerical value less than the value itself. Multiply it by 12.
K-O P-T U-Z
As an example, if the set of letters to encode consists of the letters B, G and Z, then the B with a numerical value of 2 encodes to a 4. Counting 4 letters from A produces an E. The G, with a numerical value of 7, encodes to a 5. Counting down 5 letters from the E produces the letter J. The Z with a numerical value of 26 has 13 as its largest factor. Count 156 letters (12*13) has the effect of wrapping around the alphabet 6 complete times and ending at J. The encoded solution for the letter set B, G, Z is E J J. Input There will be 10 input lines. Each will consist of a series of upper case letters and will end with a $. The $ is not encoded. Output Output will consist of a single line per test case. Input File: D:\DKC3\WrapIn.txt Output File: D:\DKC3\WrapOut.txt Examples: Input:
Output:
BGZ$ ARJ$
EJJ COT
5
3
DKC 2013 Short Computing Problems
5. Minesweeper
(20 pts)
Have you ever played minesweeper? The goal of the game is to find where all the mines are located within a M x N field. The game shows a number in a square which tells you how many mines there are adjacent to that square. Each square has at most eight adjacent squares. For instance, suppose you have the 4x4 field below with 2 mines (which are represented by an * character). If we would represent the same field placing the hint numbers described above, we would end up with the field on the right. *... .... .*.. ....
*100 2210 1*10 1110
Input The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n, m ≤ 100) which stands for the number of lines and columns of the field, respectively. Each of the next n lines contains exactly m characters, representing the field. Safe squares are denoted by “.” And mine squares by “*”, both without the quotes. The first field line where n = m = 0 represents the end of the input and should not be processed. The end of the file will be identified with a 0 x 0 minefield. There will be 10 test cases. Output For each field, print the message “Field #x:” on a line alone, where x stands for the number of the field starting from 1. The next n lines should contain the field with the “.” Characters replaced by the number of mines adjacent to that square. There must be an blank line between field outputs. Input File: D:\DKC3\MineIn.txt Output File: D:\DKC3\MineOut.txt Examples: Input:
Output:
44 *… …. .*.. …. 35 **… ….. .*… 00
Field #1: *100 2210 1*10 1110 Field #2: **100 33200 1*100
6
3
DKC 2013 Short Computing Problems
6. Text Messaging
(10 pts)
A common cell phone’s number keypad consists of 8 digits which contain letters of the alphabet. Given an input string containing a series of digits, print out all possible strings that can be produced in alphabetical order. Below is a list of which letters correspond to which digit on the keypad: 2: 3: 4: 5: 6: 7: 8: 9:
ABC DEF GHI JLK MNO PQRS TUV WXYZ
Input Input will consist of 10 test cases. Each test case is a string made up of a series of digits, each on its own line. Output Output will be a list of each possible string that can be created from the corresponding line of the input. Output the strings in alphabetical order, separated by commas. Each output case will be on its own line and terminated with an asterisk ‘*’. Output strings should be all caps. Input File: D:\DKC3\TextIn.txt Output File: D:\DKC3\TextOut.txt Examples: Input: 386 3444 Output: DTM,DTN,DTO,DUM,DUN,DUO,DVM,DVN,DVO,ETM,ETN,ETO,EUM,EUN,EUO,EVM,EVN,EVO,FTM,F TN,FTO,FUM,FUN,FUO,FVM,FVN,FVO* DGGG,DGGH,DGGI,DGHG,DGHH,DGHI,DGIG,DGIH,DGII,DHGG,DHGH,DHGI,DHHG,DHHH,DHHI,D HIG,DHIH,DHII,DIGG,DIGH,DIGI,DIHG,DIHH,DIHI,DIIG,DIIH,DIII,EGGG,EGGH,EGGI,EGHG,EGHH,EG HI,EGIG,EGIH,EGII,EHGG,EHGH,EHGI,EHHG,EHHH,EHHI,EHIG,EHIH,EHII,EIGG,EIGH,EIGI,EIHG,EI HH,EIHI,EIIG,EIIH,EIII,FGGG,FGGH,FGGI,FGHG,FGHH,FGHI,FGIG,FGIH,FGII,FHGG,FHGH,FHGI,FH HG,FHHH,FHHI,FHIG,FHIH,FHII,FIGG,FIGH,FIGI,FIHG,FIHH,FIHI,FIIG,FIIH,FIII*
7
3
DKC 2013 Short Computing Problems
7. Fibonacci Lengths
(10 pts)
The Fibonacci sequence is defined such that the first and second terms are 0 and 1 respectively and the current term is the sum of the previous two. The first 10 terms of the sequence are as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… Given an integer input, calculate which term in the Fibonacci sequence produces the first Fibonacci number to contain at least that many digits. Input There will be 10 test cases. Each test case will consist of an integer each on its own line. Output Output will be the term number of the first Fibonacci number to contain at least n digits where n is the input value. Input File: D:\DKC3\FibonacciIn.txt Output File: D:\DKC3\FibonacciOut.txt Examples: Input: 10 25 Output: 46 118
8
3
DKC 2013 Short Computing Problems
8. Brad’s Kaiser Burgers
(10 pts)
Brad owns a restaurant, and he recently came up with a great gimmick to make his business soar! He wanted to put his competition to shame by providing customers with Brad’s Kaiser Burger menu, made up of an assortment of giant burgers made of other burgers. However, Brad’s customers haven’t liked his new menu due to quality issues – ingredients in wrong places, unmatched buns, etc. He wants you to be his new quality check rep. to make sure every burger going out is made correctly. You need to ensure all non-bun ingredients are within a top and bottom bun and all top buns have a bottom bun. Write a program to verify each burger, determining which ones are the good burgers and reporting outof-place ingredients of the bad burgers. Input The input file will contain 10 test cases, one test case per line. Each test case will consist of a single burger with fewer than 100 ingredients. The ingredients of each burger will be separated by spaces and can be any of the following: bun, mayo, ketchup, mustard, onion, tomato, cheese, lettuce, beef, turkey, bison, veggie, or bacon. Bun tops are indicated by a left parenthesis, “bun(“, and bun bottoms are indicated by a right parenthesis, “bun)”. Output Your program should produce 10 lines of output, one line for each test case. The output for each test case containing a bad burger will be a list of numbers indicating which ingredients are incorrect – the first ingredient being 1, second ingredient being 2, and so on. An incorrect ingredient is any unmatched bun (top bun with no bottom or bottom bun with no top) or any other ingredient not within a top bun and a bottom bun. Delimit each incorrect ingredient from others with a space, and list the ingredients in order from smallest to largest of their numbers. If a burger is found to be good, then output “good burger” for that test case. Case is sensitive. Input File: D:\DKC3\BKBurgersIn.txt Output File: D:\DKC3\BKBurgersOut.txt Examples: Input: bun( mayo bun( ketchup beef mustard bun) ketchup bun( bun( bun( cheese bun) cheese beef bun) bun) bun) tomato bun( mustard ketchup cheese bun( turkey veggie beef bacon bun) lettuce bun( cheese bacon cheese bacon bun)
Output: good burger 1 2 3 4 5 12
9
3
DKC 2013 Short Computing Problems
9. Prime Finder
(5 pts)
A prime number is a non-negative integer greater than one and has only two positive divisors, one and itself. A number’s neighboring prime numbers are the greatest prime number less than the number and the least prime number greater than the number. Twin primes are two consecutive odd prime numbers such as 3 and 5. Write a program that, when given a number greater than 2 and less than 100,000, will output the number’s two neighboring prime numbers and whether or not the number is prime. Tip: There are 9,591 prime numbers greater than 2 and less than 100,000. Input The input file will contain 10 test cases, each case being a number on its own line. Output There will be 10 lines of output, one for each test case. Each line will contain “yes” when the number given is prime and “no” when it’s not prime, followed by first the prime number preceding the number, then the following prime number. Each portion of the answer of a test case will be separated from the others with a space. Input File: D:\DKC3\PrimeIn.txt Output File: D:\DKC3\PrimeOut.txt Examples: Input: 1337 77773 Output: no 1327 1361 yes 77761 77783
10
3
DKC 2013 Short Computing Problems
10. Busses
(20 pts)
Lee loves riding busses. He likes riding long busses, short busses, and regular busses. However, he doesn’t really like crowded busses, so sometimes he will pick the bus that he rides based on the number of people already on the bus and the number of people waiting to get on the bus. Lee will only get on a bus if it is at least 20% empty. Long busses can hold up to 80 passengers, regular busses can hold up to 50 passengers, and short busses can only hold up to 20 passengers. The bus stop Lee likes to use usually sends more than one bus at a time, and they always seem to arrive at the same time. Other people aren’t as concerned about crowds as Lee -- when the busses arrive, they board them in an even distribution until they are either full or there are no more people to board. That is, if bus A has 5 empty seats and bus B has 20 empty seats, five of the first 10 people will board the bus A, and the rest of the people will board bus B. Input In each test case the first line will be how many people are waiting at the bus stop (this number does not include Lee). Each line of the input file after the first one will consist of the type of bus, the number of people on it, and the number of those people who are getting off at this stop (separated by spaces). There are 10 test cases and each test cases will be delimited by an asterisk. Output The output should be one line listing the type(s) of busses that Lee can ride. Your answer should be formatted from the smallest to the largest type. If Lee can ride all three types, they should be separated by commas, otherwise they should just be separated with an “or”, such as “Lee can ride the regular or long bus today.” or “Lee can ride the short, regular, or long bus today.” If none of the busses fit Lee’s criteria, you should output “Lee can’t ride a bus today.” Input File: D:\DKC3\BussesIn.txt Output File: D:\DKC3\BussesOut.txt Examples: Input:
Output:
75 Short 4 0 Regular 49 12 Regular 12 3 Long 3 3 * 0 Short 3 3 *
Lee can ride the regular or long bus today. Lee can ride the short bus today.
11
3
DKC 2013 Short Computing Problems
11. Alarmingly Awkward Alliterations Are Annoying
(5 pts)
Tim “The Wordsmith” Johaneson likes words. One of his favorite games is to come up with alliterations, where all of the first letters in the word are the same (such as the title of this problem). During a recent newspaper contest (sponsored by Tim), contestants were encouraged to submit alliterations. The longest (most number of words) alliteration will be declared the winner. The grand prize for winning is a trip to Looney Larry’s Leaping Liberian Llama Land (taxes and transportation not included) and a $5 coffeehouse gift certificate. Surprisingly, there haven’t been very many entries, but Tim still would like a program to help him figure out how many words are in each line of input. If the input is not alliterative, Tim doesn’t really want to know anything about it. Input Each test case will consist of a line of text that may or may not be an alliteration. There will be 10 test cases. Output The output should either be how many words are in the alliterated sentence, or “Not alliterative” if the sentence is not an alliteration. Input File: D:\DKC3\AAAAAIn.txt Output File: D:\DKC3\AAAAAOut.txt Examples: Input: Busy Beavers Bus Busily, Barely Breaking Bandages. My foot hurts, I wish someone would be my friend. Output: 7 Not alliterative
12
3
DKC 2013 Short Computing Problems
12. Tenstrike Bowling
(30 pts)
In the country of Tenstrike the most popular pastime is bowling. Over the last few decades everyone has become so good at bowling that scoring a 300 is now a very common occurrence. So the National Bowling Association has decided to change the rules of bowling to make the game more difficult. The lanes are no longer 60 feet long, they are now 100 feet long. The lanes are no longer 42 inches wide, they are 60 inches wide. Finally there are no longer 10 pins, there are 21 pins. Also, after a strike you count the next 3 scores instead of the next 2, and after a spare you count the next 2 scores instead of the next 1. Because of these changes the current automatic scoring machines in all the bowling alleys in Tenstrike need to have new software written for them. Write a report that will read the results of 10 different games and output the scores of each game. Input Each input line will contain the scores for a single game, with the scores for each roll of the ball separated by a single space. The score of a single roll will be represented by a single character – either a number indicating the number of pins knocked down, a ‘/’ for a spare, or a ‘X’ for a strike. I almost forgot, they now play for 13 frames instead of 10. Output The program should output the total game score for each game in the input file. Input File: D:\DKC3\TBowlingIn.txt Output File: D:\DKC3\TBowlingOut.txt Rules for Tenstrike Bowling A single bowling game consists of 13 frames. The object in each frame is roll a ball at 21 bowling pins arranged in an equilateral triangle and knock down as many pins as possible. A maximum of 3 rolls is allowed per frame. On the first roll If a bowler knocks down all 21 pins on the first roll the frame is scored as a strike. A second roll for that frame is not given. If a bowler doesn’t knock down all the pins, the number of pins knocked down is scored for the first roll of the frame. On the second roll If a bowler knocks down all of the remaining pins, the second roll of the frame is scored as a spare. If a bowler doesn’t knock down all the pins, the number of pins knocked down is scored for the second roll of the frame. On the third roll If a bowler knocks down all of the remaining pins, the third roll of the frame is scored as a spare.
13
3
DKC 2013 Short Computing Problems
If a bowler doesn’t knock down all of the remaining pins the number of pins knocked down is scored for the third roll of the frame.
- If a bowler scores a strike in the first throw of the13th frame the bowler is allowed two more rolls. - If a bowler scores a spare on the second throw of the 13th frame, the bowler is allowed one more roll. - A bowler never gets more than three throws in the 13th frame. Scoring a Bowling Game The score for a bowling game consists of the sum of the scores for each frame. The score for each frame is the total number of pins knocked down in the frame plus bonuses for strikes and spares. If a bowler scores a strike in a particular frame the score for that frame is 21 plus the sum of the next three rolls. If a bowler scores a spare in a particular frame the score for that frame is 21 plus the score of the next two rolls. A gutter ball or a ball that misses any pins still standing is marked down as a 0. The maximum possible score in a game of Tenstrike bowling (strikes every frame plus two extra strikes for the thirteenth frame) is 1071. Examples: Input: Output:
X 14 6 / 15 5 / 15 / 10 5 5 18 / X 12 5 3 16 3 / 10 10 / 10 8 2 16 4 / 15 5 / 458
Input: Output:
XXXXXXXXXXXXXXX 1071
14
3
DKC 2013 Short Computing Problems
13. Longest Chain
(35 pts)
Imagine a grid composed of upper case letters. Within the grid are chains of various lengths. A chain is defined as a succession of distinct letters of the same kind running horizontally or vertically, no diagonals. The chain may span multiple rows and columns. Input Each test will consist of the following. The first line of input will be the height, m, of the grid. The second line of input will be the width, n, of the grid. m and n will be greater than 2 and less than 20. The next m lines will be the composition of the grid. There will be 10 test cases and there will be a blank line between each test case. Output Your program should output the character that is represented by the longest chain of characters that exists in the grid, as well as the length of the chain.
Input File: C:\DKC3\ChainIn.txt Output File: C:\DKC3\ChainOut.txt Examples: Input:
10 15 GTGTAUJEPJOZIIM YOHQGGQNEQDDJPT JMSPXGPXKICLVQW MKSHLGRVKBBSOSN XIUTGGBKTEFQQQQ CIFIBNBLBVEXCIW IIILBBBHGKRMJOM ZEIBRZATFZQXBYY IDIPALLLLEIRUSM IVULQLLLKGJSWON
Input:
8 8 XTGTDIEY DKQUDYBP ZXPMYGNW MKSHLGRV XIUTGGBK CIFIBNBL IXILBZBH HEVOIBMH
Output:
L7
Output:
G4
15
3
DKC 2013 Short Computing Problems
14. Angularly Clocktastic
(20 pts)
Gary is a mathematician with a strange habit – he loves finding the angles of things. He likes measuring the angles between two flower petals, he loves measuring the angle between two intersecting streets, and he even loves finding the angle between the ground and the moon in the sky. One object lends itself particularly well to angles: a clock. The angle between the hour and minute hands of an analog clock is always between 0 and 180 degrees (inclusive). For example, when the time is 12:00, the angle between the hour and minute hands is 0 degrees. When the time is 6:00, the angle between the hour and minute hands is 180 degrees. Gary loves angles, but his eyesight isn’t what it used to be. His new favorite activity is asking his granddaughter, Susan, the time. Then, after she tells him, he immediately wants to know what the angle is between the hour and minute hands. Being a brilliant mathematician, he already knows the answer – he is just trying to train Susan to think of angles (and clocks) like he does. He knows, for example, that the hour hand of a clock moves slowly between the hours as it moves around the face – that is, when it is 3:15 the hour hand is one quarter of the way between 3 and 4, not directly pointed at 3. Susan is not a mathematician, so she needs help answering these questions. Write a computer program that takes in a time and responds with the angle between the hour and minute hand to help Susan. Input The input data will consist of a time formatted as HH:MM. There are 10 test cases. Output The output data should be the angle formed by the minute and hour hand in degrees, followed by “degrees.”. The output should always have one and only one number after the decimal point (for example, “120.0 degrees.”). Input File: C:\DKC3\ClockIn.txt Output File: C:\DKC3\ClockOut.txt Examples: Input 12:30 9:00 Output 165.0 degrees. 90.0 degrees.
16
3
DKC 2013 Short Computing Problems
15. Dome Builder Dennis
(30 pts)
Dennis is a home builder, but he doesn’t like square structures so he builds geodesic domes instead. A geodesic dome is made up of triangles where the vertices of each triangle lie on an imaginary sphere (e.g. the Epcot Center is a geodesic dome). The resulting structure uses far fewer materials than an equivalent rectangular house and is significantly stronger. However, there are a few extra challenges when building a dome. One of those is calculating how much of each building material to buy. Dennis’ domes are of the hub-and-strut type. Each triangle in the dome framework is made up of 3 wooden struts that bolt into a hub at each vertex. A piece of plywood is nailed to the outside of each triangle forming the “skin” of the dome. Depending on the size of the dome, there can be from 1 to 6 different lengths of struts. Each is given a letter designation (A = the smallest strut, B = the next biggest, etc.). Each triangle can then be designated by the struts that make it up (e.g. a CCB triangle has a B length strut at its base and C length struts on its other two sides). The diagram below illustrates the framework of a “2 frequency” dome, which is made up of two strut lengths. Dennis has a few domes to build and is trying to figure out how many bolts to buy (he can get a sizable discount if he buys them up front in bulk). Each strut requires 8 bolts (4 at each end). Note that all struts form the sides of two triangles, except the ones at the base. Write a program that will calculate how many bolts will be required to attach all of the struts to the hubs.
Input Each line of input will contain the quantity of each type of base strut and the number of each type of triangle for a planned dome. There are 10 test cases. Output One line per test case containing the number of bolts needed. Input File: C:\DKC3\DomeIn.txt Output File: C:\DKC3\DomeOut.txt Examples: Input
17
3
DKC 2013 Short Computing Problems
A:10 B:0 AAB:30 BBB:10 A:0 B:5 C:10 D:0 AAB:15 CCB:31 CCD:32 Output 520 996
18
