Lewis University



ACCA Programming Contest February 21, 2009

Problem #1

SCRAMBLED TEXT

Advanced

Source File: problem1.cpp or problem1.java

Acocdrnig to rseaecrh at Cabmirgde Uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Are you surprised that you can read the above text without too much problem, even though the letters are not in the correct order? But is what it says true. Not really. The way the letters of the words were rearranged in the passage makes them fairly easy to read. Here are alternate word scrambles:

|Real Word |Passage Scramble |Harder Scramble |

|According |Acocdrnig |Aronidccg |

|Cambridge |Cabmirgde |Crmigdbae |

|research |rseaecrh |rsreecah |

Why are the passage versions easier to read? First note that the first and last letters are in the right place. It seems when we read, we extract a lot of information from the context, so understanding several words in a sentence can help us guess another one. Also the words are not fully scrambled. The order of the letters are nearly maintained. The Harder Scramble column above illustrates the difficulty of making out the word when the letters are more fully scrambled.

The purpose of this problem is to generate scrambled word sentences from a given sentence. In fact, you will generate two scrambled sentences. The general rules for scrambling words are: 1) The word must be four or more letters in length in order to be scrambled and 2) The first and the last letters will remain in their places. Each scrambled sentence is terminated with a period (.). The first scrambled sentence will be created by interchanging adjacent pairs of letters starting with the last pair. The second scrambled sentence will be created by ordering the letters in reverse alphabetical order. The words in the table above illustrate these two scrambles. The Passage Scramble is generated by interchanging the letters. The Harder Scramble column is generated by ordering the letters. (Note that the entire text above does not use either one of these methods consistently.)

INPUT: Your program should accept a sentence at the prompt: “Enter sentence: “. Assume that all sentences entered will be less than 200 characters in length. Your program should continue to accept sentences until only a period (.) is entered. At this point your program should terminate with no further output.

OUTPUT: Your program should output on two consecutive lines the sentence created by interchanging the letters followed by the sentence created by ordering the letters.

EXAMPLE: Enter sentence: Enjoy doing something different this coming weekend.

Enojy donig soemhtnig diffrenet tihs cmonig wekened.

Eonjy donig stonmiheg drniffeet tihs conmig wnkeeed.

Enter sentence: Happiness always accompanies with you.

Happnises awlyas acocpmnaeis wtih you.

Hsppnieas aywlas aponmieccas wtih you.

Enter sentence: A pleasant surprise is awaiting you.

A pelsanat srurpsie is aawtinig you.

A psnleaat susrrpie is awtniiag you.

Enter sentence: .

ACCA Programming Contest February 21, 2009

Problem #2

EGYPTIAN FRACTIONS

Advanced

Source file: problem2.cpp or problem2.java

Egyptian fractions provide a representation of rational numbers that is anything but intuitive. An Egyptian fraction is the representation of a standard fraction as the sum of distinct unit fractions (i.e., fractions with a numerator of 1). For example, the Egyptian fraction for 6/7 is:

[pic]

The algorithm for converting a standard fraction to an Eqyptian fraction can be specified recursively as:

Using the fractions 6/7 again as an example, the largest unit fraction that is less than 6/7 is 1/2. Thus, we reduce the problem to the conversion of the fraction 6/7 – 1/2 = 5/14. The largest unit fraction that is less than 5/14 is 1/3 leaving the fraction 5/14 – 1/3 = 1/42. Since 1/42 is a unit fraction, the algorithm terminates. Your problem is to implement this algorithm, outputting the Egyptian fraction given a fraction.

INPUT: Your program should accept two integers, separated by at least one space, at the prompt “Enter fraction: “. The first integer entered will be the numerator and the second integer entered will be the denominator. Only proper fractions will be entered, that is p will always be less that q. Your program should continue accepting pairs of integers until two zeroes are entered. At this point your program should terminate.

OUTPUT: Your output should be of the form:

Egyptian fraction is 1/d1 + 1/d2 + 1/d3 … + 1/dn

EXAMPLE: Enter fraction: 6 7

Egyptian fraction is: 1/2 + 1/3 + 1/42

Enter fraction: 0 5

Egyptian fraction is: 0

Enter fraction: 2 3

Egyptian fraction is: 1/2 + 1/6

Enter fraction: 33 34

Egyptian fraction is: 1/2 + 1/3 + 1/8 + 1/82 + 1/16728

Enter fraction: 0 0

ACCA Programming Contest February 21, 2009

Problem #3

DOUBLE-REVERSING NUMBERS

Advanced

Source File: problem3.cpp or problem3.java

Notice that when you double the binary integer 0111 (7 base 10), the result is 1110 (14 base 10), the reverse of the original binary integer 0111. Another binary integer 01000001 (65 base 10) when doubled results in 10000010 (130 base 10), the reverse of the original binary integer 01000001. There are many binary integers which have the property that its digits reverse when added to itself as long as the number of bits in both the binary integer and its doubled sum are the same. The purpose of this problem is to generate the total number of binary integers that have this property for all binary integers less than or equal to a given integer n, where n is a base 10 integer. For example, if n = 50, you are to determine how many binary integers have this double-reversing property that are in the range from 1 to 50, inclusive, when written each is written as a binary integer.

INPUT: Your program should accept an input representing the integer n (n ≤ 1000000) at the prompt: “Enter integer: “. Your program should continue to accept inputs until a 0 is entered. At this point your program should terminate without further output.

OUTPUT: Your output should be in the form: “Number having this property = XX”.

EXAMPLE: Enter integer: 10

Number having this property = 5

Enter integer: 50

Number having this property = 12

Enter integer: 88

Number having this property = 17

Enter integer: 0

ACCA Programming Contest February 21, 2009

Problem #4

UV INDEX

Advanced

Source File: problem4.cpp or problem4.java

The sun emits three types of ultraviolet (UV) radiation: UVA, UVB, and UVC. UVA penetrates deep into the skin often causing intense damage like wrinkles and skin discoloration. Exposure to UVB causes sunburn, a skin reaction where blood vessels expand and leak fluids, producing inflammation, pain, and redness. Sunburn, whether severe or mild, can cause permanent and irreversible skin damage. Cumulative exposure to UV radiation and the number of severe sunburns received, especially during childhood, significantly increases the risk of developing skin cancer.

The ozone layer blocks almost all of the sun’s output of UVC and most UVB radiation. The UVB radiation that does reach the earth’s surface poses the greatest danger for sunburn and skin damage. Ozone gas high in the atmosphere is vital in filtering out much of the sun’s UV, making ozone depletion a major environmental issue.

Forecasting the intensity of UV at ground level takes into account information factors on the time of day, date, latitude, amount of cloud cover, altitude from sea level, presence of haze and ozone concentrations.

The UV index is a simple and informative way of describing the daily danger of solar UV radiation intensity. It can be calculated from a direct measurement of the UV spectral power at a given place and specified by the following formula: UV index = UVA * 0.8911 + UVB * 0.0818 + UVC * 0.0078. The resultant value is then rounded to the nearest integer. The following table gives information on the various UV index values.

|UV Index |Exposure |Description |Media Graphic |Recommended |

| |Level | |Color |Protection |

|0-2 |Low |No danger to the average person |Green |Wear sunglasses; use sunscreen if you have |

| | | | |particularly fair skin. |

|3-5 |Moderate |Little risk of harm from unprotected sun |Yellow |Wear sunglasses and use sunscreen, cover the body |

| | |exposure | |with clothing and a hat, and seek shade around |

| | | | |midday. |

|6-7 |High |High risk of harm from unprotected sun exposure|Orange |Wear sunglasses and use sunscreen having SPF 15 or |

| | | | |higher, cover the body with sun protective clothing|

| | | | |and a wide-brim hat, and reduce time in the sun |

| | | | |from two hours before to three hours after solar |

| | | | |noon. |

|8-10 |Very High |Very high risk of harm from unprotected sun |Red |Take all precautions and do not stay out in the sun|

| | |exposure | |too long. |

|≥11 |Extreme |Extreme risk of harm from unprotected sun |Violet |Take all precautions above, including wearing a |

| | |exposure | |long sleeve shirt and trousers and avoid the sun |

| | | | |from two hours before to three hours after solar |

| | | | |noon. |

The purpose of this problem is to determine the Exposure Level given the spectral powers of UVA, UVB, and UVC measured at a given place. ththth

INPUT: Your program should accept three spectral power decimal values in the order UVA, UVB, and UVC at the prompt: “Enter spectral values: “. The values are separated by one or more spaces. Your program should continue to accept inputs until three zeroes are entered. At this point your program should terminate without further output.

OUTPUT: Your output should be one of the exposure levels indicated by the chart above given the calculated UV Index value. The format of your output should be: Exposure level: XXXXXXXX where XXXXXXXX is the exposure level.

EXAMPLE: Enter spectral values: 7.1850 36.5099 67.6423

Exposure level: Very High

Enter spectral values: 3.2953 21.8804 46.0311

Exposure level: Moderate

Enter spectral values: 0 0 0

ACCA Programming Contest February 21, 2009

Problem #5

PATTERN MATCHING

Advanced

Source File: problem5.cpp or problem5.java

Structured Query Language (SQL) is a language used to create relational databases and manipulate the data in them. The Select statement in SQL allows for the retrieval of data from the database through a number of row limiting expressions. One example of a Select statement is:

select CustomerName

from Customer

where CustomerAddress LIKE ‘%Chicago, IL%’;

This statement will retrieve all customer names whose addresses contain the substring ‘Chicago, IL’. This works because of the pattern matching capability built into SQL for use in the LIKE form of the where clause. The pattern ‘%Chicago, IL%’ is matched against the subject string, the contents of the CustomerAddress field of the record.

SQL includes the following pattern matching characters.

% matches any number of characters, possibly none

_ matches any one character

The matching pattern may be composed of any of characters, along with alphabetic characters which must match exactly.

For example:

‘abc’ would only match “abc”

‘%a’ would match only those strings ending in “a” like “a”, “alpha”, “aaa”

‘_____a’ would match only those five character strings ending in “a” like “alpha” and “quota”

‘_a%’ would match only those strings containing an “a” in the second position, like “cash”,

“aa”, and “taste”

‘%r%z’ would match only those strings containing an “r” with a “z” as the last character of the string, like “jazzerciz”, “rz”, “arrqz”

The purpose of this program is to match a given pattern against a given character string and report whether a valid match is found.

INPUT: Your program should accept a series of pattern string pairs in the form of / entered at the prompt: “Enter pattern/string: “. Your program should continue to accept inputs until a ‘/’ alone is entered. At this point your program should terminate with no further output.

OUTPUT: Output the message ‘Valid’ if the string matches the pattern; otherwise output the message ‘Invalid’.

EXAMPLE: Enter pattern/string: _a%/cash

Valid

Enter pattern/string: %r%z/crazy

Invalid

Enter pattern/string: %p_p%m__/hippopatamus

Valid

Enter pattern/string: %p_p%m__/approximate

Invalid

Enter pattern/string: /

ACCA Programming Contest February 21, 2009

Problem #6

OUT AND UNDER

Advanced

Source file: problem6.cpp or problem6.java

When I was a kid, one of my friends showed me a “trick” he had just learned. From a deck of cards he took out one each of the A, 2, 3 … 10, J, Q, K. He arranged the cards out of my sight, then proceeded to deal them out thusly:

The top card was placed face up on the table. The second was transferred from top to bottom. The third card was thrown out face up, the fourth transferred to the bottom, and so on. The cards as they were thrown out face up came in the order: A, 2, 3 … 10, J, Q, K. He challenged me to discover the correct initial order of the cards to produce this result. By trial and error I discovered the secret. And now I have determined that this process of arranging a set of cards to obtain a certain face-up order when dealing the cards using “out and under” can be automated. This is the purpose of this problem.

Write a program that will generate the order of the integers from 1 to n (n ≤ 52) so that when they are dealt “out and under”, the face-up order will be 1, 2, 3, … n.

For example, for n = 5, the “out and under” order would be: 1 5 2 4 3.

INPUT: Your program should accept an integer representing the number of cards at the prompt: “Enter number of cards: “. Your program should continue to accept inputs until a zero is entered. At this point your program should terminate without further output.

OUTPUT: Your output should be a listing of the order the cards should be placed in the deck from top to bottom. The first number indicates the card that is at the top of the deck and the last number indicates the card that is at the bottom of the deck. The list should be output on one line with wraparound for longer lines being acceptable.

EXAMPLE: Enter number of cards: 5

1 5 2 4 3

Enter number of cards: 13

1 12 2 8 3 11 4 9 5 13 6 10 7

Enter number of cards: 0

ACCA Programming Contest February 21, 2009

Problem #7

PATHS ON A CHECKBOARD

Advanced

Source File: problem7.cpp or problem7.java

If a checker is placed on one of the four black squares in the first row of an otherwise empty checkerboard, it can move (by a standard checker moves) to any of the four black squares on the last (eighth) row by a variety of different paths. The following checkerboard illustrates the number of different paths that a checker starting in the lower right hand corner (labeled as 1) could take to end up on each of the black squares in the eighth row (labeled as A, B, C, and D). A standard checker move is one square forward on the diagonal. Therefore, a checker may never move onto a white square.

|A | |B | |C | |D | | |14 | |14 | |6 | |1 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |1 | |2 | |3 | |4 | | |

One pair of starting and ending squares is joined by a maximum number of different routes. The purpose of this problem is to identify these two squares by number and letter and give the number of different ways the checker can move from one to the other. Here is the clinker. Your program must be able to solve this problem for a checkerboard of any size from 4 to 32; that is, from 4x4 boards up to 32x32 boards. The lower left-hand corner of the checkerboard is always black.

INPUT: Your program should accept an integer representing the size of the checkerboard at the prompt: “Enter size: “. Your program should continue to accept integers until a zero (0) is entered. At this point your program should terminate without further output.

OUTPUT: Your output should be of the form: #-A: XXXX different paths

where # is the number of the starting black square given that the black squares in the first row are numbered starting with 1, A is the letter of the ending black square given that the black squares are lettered in the last row starting with A, and XXXX is the number of different paths.

EXAMPLE: Enter size: 4

2-A: 3 different paths

Enter size: 8

3-B: 35 different paths

Enter size: 32

9-H: 300540195 different paths

Enter size: 0

-----------------------

Egyptian Fraction Conversion Algorithm

The Egyptian fraction equivalent of the fraction p/q is f as defined in the following cases:

Case 1: p=0

f is 0

Case 2: p = 1

f is p/q

Case 3: p > 1

f ·¨¸¨¿¨Þ¨ß¨©©K©L©R©b©c©l©r©z©©ª®ð®ò®ô®ö®ø®íÞÌÞ¾¬¾¬¾žŒž¾ž¾}{¾jfbíis 1/k + (the Egyptian fraction equivalent of (p/q – 1/k)) where k is the smallest positive integer such that p/q ≥ 1/k.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download