FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«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 ...»

-- [ Page 1 ] --

Nineteenth Annual

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

Vote! vote

These Are the Voyages… voyages

The Sixth Cents cents

Necklaces necklace

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?

The Problem:

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.

The Output:

For each input case, print out the number of iterations required before the Chinary Search yields a result less than or equal to p.

Sample Input:

150 50 0.25 350 80 0.01 1999 2 0.20 0 0 0.0

Sample Output:

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.

The Problem:

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

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:

Message m:

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:

Invalid message.

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.

Sample Input:

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.

Sample Output:

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.

The Problem:

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.

The Input:

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.

The Output:

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.

Sample Input:

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

Sample Output:

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

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

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.

Pages:   || 2 | 3 |

Similar works:

«FSN_Brochure_1313_RFID_Property & Evidence Management RFID Automates Police Property and Evidence Management The management of property and evidence from collection, cataloging, storage, and any movement to their ultimate use or disposition is one of the key responsibilities for a law enforcement agency. Agencies must meet strict requirements to ensure the chain of custody of the evidence collected is rigorously maintained. The challenge in managing a property unit is not only storing highly...»

«IFLA STATUTES INTERNATIONAL FEDERATION OF LIBRARY ASSOCIATIONS AND INSTITUTIONS P.O. BOX 95312 2509 CH THE HAGUE NETHERLANDS IFLA Statutes The Statutes were adopted at the IFLA Council meeting in Québec City, Canada, 14 August 2008. The text of these IFLA Statutes has been translated into Dutch, and the notarial deed of the amendment of the Statutes of IFLA shall be executed in the Dutch language, to comply with Dutch law. Inevitably, differences may occur in translating this text into Dutch,...»

«WHEN GRAVEYARDS YAWN The Apocalypse Trilogy: Book One G. Wells Taylor Copyright 2009 by G. Wells Taylor. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without the written consent of the author, except where permitted by law. Cover Design by G. Wells Taylor More titles at GWellsTaylor.com. Table of Contents Dedication Part One:...»

«VARNER.WL (DO NOT DELETE) 8/9/2010 11:35 AM IS THE DEAD HAND LOSING ITS GRIP IN TEXAS?: SPENDTHRIFT TRUSTS AND IN RE TOWNLEY BYPASS UNIFIED CREDIT TRUST N. Camille Varner* I. INTRODUCTION The classic phrase “dead-hand control” signifies the ability of an individual to direct how and to whom his property will pass after his death.1 The extent to which the law should encourage or even protect this ability is an underlying issue in almost every legislative and judicial decision creating law on...»

«28 MINUTES OF REGULAR CITY COUNCIL MEETING Call to Order The City Council of the City of Katy, Texas, convened in regular session on Monday, March 24, 2014, at 6: 30 p. m. at Katy Municipal Complex, 910 Avenue C, Katy, Texas. The following City officials were present: Fabol Hughes, Mayor Larry Gore, Mayor Pro Tem Bill Lawton, Councilmember Jimmy Mendez, Councilmember Steve Pierson, Councilmember Art Fertile, City Attorney Johnny Nelson, City Administrator Linda Vourazeris, Assistant City...»

«City and County of Denver 201 West Colfax Ave., Dept. 705 • Denver, Colorado 80202 • 720-913-5000 • FAX 720-913-5247 www.denvergov.org/auditor Dennis J. Gallagher Auditor Prevailing Wage/Certified Payroll Overview What is the basis for Prevailing Wage? It's the Law: Prevailing Wage is covered under Section 20-76 of the Revised Municipal Code of the City and County of Denver. The law declares that any contractor or subcontractor at any tier who performs construction, alteration,...»

«IN THE SUPREME COURT OF CANADA (ON APPEAL FROM THE COURT OF APPEAL FOR ONTARIO) B E T W E E N: CHARON ENTERTAINMENT INC. Appellant and PANDEMONIUM PRODUCTIONS CORP. ET AL. Respondents APPELLANT’S FACTUM Team No. 11 2013 Canadian Corporate/Securities Law Moot Court Competition TABLE OF CONTENTS PART I – STATEMENT OF FACTS A. OVERVIEW B. RELEVANT FACTS (i) Pandemonium’s Poor Performance (ii) Charon’s Announcement (iii) The Rights Plan (iv) The Convertible Notes (v) The Surrender of the...»

«Notes and Solved Problems for Common Exam 2 3. GAUSS LAW Key concepts: Gaussian Surface, Flux, Enclosed Charge Gauss Law is equivalent to the Coulomb law but sometimes more useful. Gauss law considers a flux of an electric field thru some hypothetical surface (called a Gaussian surface) The flux of the field E thru the surface S is formally an integral rr Φ = ∫ EdS The Gauss law relates the flux of the electric field thru the Gaussian surface with the total charge enclosed by this surface rr...»

«A CHEAP LAUGH FOR THE INTERNET A DRAMATIC DUET by Bradley Walton Brooklyn Publishers, LLC Toll-Free 888-473-8521 Fax 319-368-8011 Web www.brookpub.com Copyright © 2011 by Bradley Walton All rights reserved CAUTION: Professionals & amateurs are hereby warned that A Cheap Laugh for the Internet is subject to a royalty. This play is fully protected under the copyright laws of the United States of America, Canada, the British Commonwealth and all other countries of the Copyright Union. RIGHTS...»

«THE ARGUMENTS FOR PROTECTION The importance of SERIES forest protected areas to drinking water RunningPure A research report by the World Bank / WWF Alliance for Forest Conservation and Sustainable Use Running Pure Running Pure: The importance of forest protected areas to drinking water A research report for the World Bank / WWF Alliance for Forest Conservation and Sustainable Use Written and edited by Nigel Dudley and Sue Stolton With major research and contributions by Rachel Asante Owusu,...»

«CEPF FINAL PROJECT COMPLETION REPORT I. BASIC DATA Organization Legal Name: The East Foundation Project Title (as stated in the grant agreement): Community-Initiated Red Panda Conservation Project in North-East Region of Sankhuwasabha District in Eastern Nepal, Himalaya Implementation Partners for this Project: Community Forest User Groups, Buffer zone Management Committee of Makalu-Barun National Park, Area-level Federations of Community Forest Users, Village Development Committees, District...»

«Wells-to-Guzzlers Environmental Assessment page 1 of 43 ENVIRONMENTAL ASSESSMENT for a Proposal to Convert 12 Ranching Wells into Wildlife Guzzlers Mojave National Preserve, California Mojave National Preserve 2701 Barstow Road Barstow, CA 92311 Wells-to-Guzzlers Environmental Assessment page 2 of 43 TABLE OF CONTENTS SECTION I: PURPOSE OF AND NEED FOR ACTION Introduction Purpose and Need Background Related Laws, Policies, and Other Planning Documents Environmental Assessment Issues and Impact...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.