«Call your program file: filename.c, filename.cpp, or filename.java Call your input file: filename.in For example, if you are solving The Law of ...»
University of Central Florida
High School Programming
Problem Name Filename
Chinary Search chinary
Purmteed Slleinpg spelling
The Law of Signs signs
Sleeping Astronauts sleep
He Got the Box! box
These Are the Voyages… voyages
The Sixth Cents cents
Duck Duck Boot! duckboot Call your program file: filename.c, filename.cpp, or filename.java Call your input file: filename.in
For example, if you are solving The Law of Signs:
Call your program file: signs.c, signs.cpp or signs.java Call your input file: signs.in Chinary Search Filename: chinary A more appropriate name for this problem would be Chisection, but part of the title was lost in translation by our Chinese to English dictionary. Do worry not, problem translated statement perfect.
In Chinese markets, the only communication between the vendors and the customer (you) is through the LCD of a four-function calculator. You push through crowds, scooters and bicycles to find your desired item in the market. You point at it to let the vendor know that you are interested, and she types in a number into the calculator. This initial price, n, is not completely unreasonable, but one of the fun parts about being a tourist in China is haggling with the shop keepers, so you punch in a much lower number, p, than the one initially presented. The vendor laughs and mentions something about her family and how she has mouths to feed at home.
Although she is not yet willing to sell you the item at your low offer, she will be; it just takes patience and persistence. She wants to get as much of your money as she possibly can, so she lowers her price by a percentage, r. But, you have been in China for a couple of days and know that the vendor will eventually reduce her price to yours, so you punch your initial offer back in the calculator to let her know that you mean business. Again, she repeats the process of lowering her current price by the percentage r, and you again type in your initial offer. This process repeats until the price she enters is less than or equal to your initial offer. How can you sleep at night knowing you haggled her down to such a low price, thus taking food out of her children’s mouths?
You will be given three numbers: two integers representing the vendor's initial price of the item and the price that you are willing to pay. The third value will be a floating-point number indicating the percentage the vendor lowers herprice each iteration. Your job is to determine how many times the Chinary Search algorithm iterates before you are satisfied.
Here is an example to illustrate how the algorithm works:
Notice that in iteration 1, the initial price 150 was dropped by 25% (37.50). This produces a new value for n, 112.50, but because prices in China rarely contain fractions of a Yuan (Chinese dollar), the vendor will always round down to set her new price when the new value contains fractions. The answer to this example would be 4.
Each line of input will contain 3 numbers (n, p and r), separated by one or more spaces (0 p n 2000 and 0.001 ≤ r ≤ 0.999). The input terminates when p equals zero.
For each input case, print out the number of iterations required before the Chinary Search yields a result less than or equal to p.
150 50 0.25 350 80 0.01 1999 2 0.20 0 0 0.0
4 115 28
Psychologists have shown that we can read entire paragraphs with words that are misspelled and understand the entire paragraph. In particular, if a word has the correct first and last letter, all the letters in between can be permuted any which way, and we can still read the word properly.
Consider the following paragraph:
You wloud tnhik taht this pgraaaprh wulod be vrey dfcluiift to read. But inasted, you can usrednantd elaxcty waht is wtetirn wtuoiht too mcuh sairtn. Does tihs maen you are dxyelsic, or taht we all hvae a llitte dliysexa in us? Who kowns? But, it deos seapk to the radnuecndy in the Eslingh lgaagune and our mnids atiilby to cceorrt for mktiases.
After learning this little tidbit of trivia, your smart-aleck brother has resorted to writing all of his messages to you in this manner. When properly transformed, each word has the correct first and last letter, but the letters in between are randomly permuted. In addition to letters, the only other characters (besides spaces) his messages use are the following punctuation marks: period (.), comma (,), question mark (?) and exclamation point (!). All punctuation remains in its proper place, at the end of a word. (Though sometimes, for emphasis, he will repeat a punctuation mark at the end of a sentence several times.) Sometimes however, he accidentally changes letters such that they are no longer a properly transformed permutation of a real word.
Although you can read his messages, you are tired of his poor form and want to write a program that will fix his messages, or tell you that they are invalid, meaning that they contain at least one jumbled word that is not a valid transformation of a real word.
The first line of the input will contain a single positive integer, n (0 n ≤ 1000), representing the number of words in the dictionary. The following n lines will contain the words from the dictionary, one word per line. All dictionary words will be entirely lowercase letters and less than 20 in length. The following line will contain a single positive integer, k (0 k 100), representing the number of messages to decipher. Each of the following k lines will contain a message each that is 80 characters or shorter, will contain at least one letter, and will not contain leading or trailing spaces. The message should be considered in a case insensitive manner, meaning that a word is valid as long as it contains the correct letters and no others, regardless of capitalization. In all original messages, the only letter in any word that will be capitalized is the first letter. Also, you are guaranteed that at most one possible word in the dictionary will match any jumbled word in any input message.
You will produce one line of output for each of the k messages, each separated by a blank line.
The beginning of each line of output will read:
where m is replaced with the message number (1 ≤ m ≤ k).
If the message is invalid (meaning any word in the message cannot be permuted as described to
match a word in the dictionary), output the following:
Otherwise, correct the spelling in the message (based on the given dictionary), and output the corrected messages, with the punctuation intact. Your output should reflect the capitalization and spacing of the original message.
12 a an is can commas have invalid long sentence sentences this too 4 Tihs sceennte is lnog.
Is this a steencne?
Tihs is an invalid snteenec!
Snteecnes can hvae, cmomas, too.
Message 1: This sentence is long.
Message 2: Is this a sentence?
Message 3: Invalid message.
Message 4: Sentences can have, commas, too.
Stan’s Signs is a huge, nationwide supplier of signage for all kinds of businesses who want to advertise along the country’s highways. Stan makes signs in all kinds of shapes and sizes, but his best seller has always been his triangular signs. Stan believes that the key to his success is his quality control. You see, Stan insists that his triangle signs all conform to what he calls the “Law of Signs.” The Law of Signs simply states that the ratio of the length of one of the sides of the sign and the sine of the angle opposite that side must be the same for all three angle/side pairs. This may sound similar to another law that you’ve heard from analytic geometry, but Stan
insists that it’s company proprietary. To better understand the Law of Signs, here’s a diagram:
Stan realizes that his Law of Signs is ambiguous, in that two different angles can have the same sin value (45 degrees and 135 degrees, for example), so to account for this, he only sells acute triangular signs (all of the sign’s angles are less than 90 degrees).
Unfortunately, Stan’s order database recently suffered a hard drive crash, and the tape backup system failed to run that weekend, so Stan had to resort to a data recovery service to get his orders back. The service couldn’t restore the data completely, so all Stan has now is partial measurements for all the signs that must be made. He’s hired you to write a program to rebuild the database. Stan is clear that you’re only to use the Law of Signs in this endeavor. You protest that other techniques would also be helpful in solving this problem, but Stan is worried about copyright infringement law suits from other sign companies. After a bit of convincing, Stan agrees to also let you use the triangle’s angle sum property, which states that all three angles of a triangle always sum to 180 degrees.
Given a partial set of angle and side measurements for each sign, reconstruct the complete measurements for the sign, such that they conform to the Law of Signs and the angle sum property. Some data may have been corrupted, so if the measurements can’t possibly be reconciled with each other such that the sum of the angles is within 0.01 of 180 degrees and the three terms of the Law of Signs are within 0.01 of each other, you must reject the order, and the customer must order again (a slightly annoyed customer is much better than an inferior Stan’s Signs product!) Use 3.14159 as the value of Π in the recovery process. Also, in some cases there may not be enough recovered data to be able to reconstruct all the measurements using just the Law of Signs and the angle sum property. You’ll need to identify these cases as well.
6 There will be multiple signs. Each sign consists of one line containing six real numbers, (A, B, C, a, b, c) separated by whitespace. The first three numbers represent the angle measurements of the sign. Angles will be given in degrees (greater than 0 and less than 90), and specified in counter-clockwise order. The second three numbers will be non-zero and represent the lengths of the sides (given in inches) opposite those angles, respectively. If any of the measurements are negative, it means that that measurement is missing. Input is terminated by a line containing six negative numbers.
For each sign, print “Sign #n:”, where n is the number of the sign (starting with 1), followed by a space and the reconstructed set of three angle measurements and three side measurements, given in the same order as the input data. Print the measurements rounded to two decimal places (0.014 rounds to 0.01 and 0.015 rounds to 0.02). Separate each measurement by a single space.
If a sign that conforms to both the Law of Signs and the angle sum property cannot be reconstructed, print “Rejected!” in place of the measurements. Similarly, if any reconstructed sign includes a non-acute angle, print “Rejected!” since it couldn’t possibly be a Stan’s Sign. If there aren’t enough data to reconstruct all measurements using the techniques described, print “Lost!” in place of the measurements.
60.0 -1.0 -1.0 36.0 -1.0 36.0
-1.0 65.0 -1.0 40.0 -1.0 50.0 75.0 55.0 -1.0 10.0 -1.0 10.0
-1.0 -1.0 -1.0 -1.0 -1.0 -1.0
Sign #1: 60.00 60.00 60.00 36.00 36.00 36.00 Sign #2: Lost!
Sign #3: Rejected!
NASA is finally sending astronauts to other planets, and you’re on the team to help develop programs for them to use. Since the astronauts have been training for a while, all of the missioncritical programs (like navigation) have been completed. There’s one small catch, however: not all planets in the galaxy have the same day length as Earth does. In fact, the planet they are traveling to has a 26-hour-long day. This might introduce problems with astronauts’ sleep schedules. So, since regular scheduling programs can’t be relied upon due to the difference in day lengths, NASA project managers have asked you to write a program to verify sleep schedules.
The flight surgeon is planning the sleep schedule for the astronauts, but he must run his plans through your program to verify that each astronaut is getting enough sleep during that week (seven nights) of the mission. So, given a weekly schedule, as well as the desired number of hours of sleep, your job is to see if the schedule for that astronaut is valid for one week (again, seven nights) of 26-hour-long days.
The first line of the input file will consist of an integer, n, representing the number of sleep plans in the file. Each sleep plan will contain 8 lines each. The first line of the sleep plan will contain a single integer number, x, representing the minimum amount of total time (in hours) that that astronaut should sleep that week. The next seven lines will contain the times, in 26-hour format, for the sleep plan. The time the astronaut will go to sleep and the time the astronaut will wake up will be separated by a dash. The times will be in “HH:MM” format, where HH is the hour and MM is the minutes. All times will be in sequential order, meaning that the time the astronaut is scheduled to wake up will always be after the time the astronaut is scheduled to go to sleep.