ACCA Programming Contest February 25, 2006

ACCA Programming Contest February 25, 2006

Problem #1

ORDERED SENTENCES

Advanced

Source file:problem1.extension

The purpose of this program is to classify sentences as either UP sentences, DOWN sentences, or MIXED-UP sentences. An UP sentence is a sentence in which its words are in non-decreasing alphabetical order as read from left to right. A DOWN sentence is a sentence in which its words are in non-increasing alphabetical order as read from left to right. A MIXED-UP sentence is a sentence which is neither an UP sentence or a DOWN sentence.

INPUT:Your program should accept a sentence at the prompt: “Enter sentence: “. Your program should continue to accept sentences until the sentence ‘Stop’ is entered. At this point your program should terminate. Sentences may consist of punctuation, numbers, etc. An alphabetic character determines the beginning of a word. A non-alphabetic character determines the end of a word. There will be no contractions. Your program should be case insensitive.

OUTPUT:Your program should output the classification of the sentence in the form:

‘XXXXXX sentence’ where XXXXXX is either UP, DOWN, or MIXED-UP.

EXAMPLE:Enter sentence: “Hello, I love programming!” said Tom zealously.

UP sentence

Enter sentence: Zebras watch 34 purple monsters Mondays eat applesauce.

DOWN sentence

Enter sentence: How now brown cow!

MIXED-UP sentence

Enter sentence: Stop

ACCA Programming Contest February 25, 2006

Problem #2

MIXED PRIMES

Advanced

Source file:problem2.extension

An integer is a mixed prime if the integer can by split in two and the two resulting integers are prime numbers. A multimixed prime is a mixed prime that can be split in more that one way into two primes. A super mixed prime is a mixed prime which by itself is prime. A super multimixed prime is both a super mixed prime and a multimixed prime. The purpose of this problem is to classify an integer as a mixed prime, a multimixed prime, a super mixed prime, a super multimixed prime, or none of the above. In addition, list all the splits of the integer that make it a mixed prime or a multimixed prime.

Note: 1 is not a prime number.

INPUT:Your program should accept an integer at the prompt: “Enter an integer: “. Your program should continue accepting integers and classifying them until 0 is entered. You may assume that all entries will be less than one million.

OUTPUT:Your output should be of the form: x is a XXXXXX prime

Splits: XXX YYY, XX YYYY, …

or

No classification possible

EXAMPLE:Enter an integer: 89887

89887 is a mixed prime

Splits: 89 887

Enter an integer: 23599

23599 is a supermixed prime

Splits: 23 599

Enter an integer: 3743

3743 is a multimixed prime

Splits: 3 743, 37 43

Enter an integer: 73019

73019 is a super multimixed prime

Splits: 7 3019, 73 019

Enter an integer: 246804

No classification possible

Enter an integer: 0

ACCA Programming Contest February 25, 2006

Problem #3

THE BACONIAN CIPHER

Advanced

Source File:problem3.extension

Lord Francis Bacon invented a ciphering technique in which the secret message is hidden in any text message that is at least five times as long as the secret message. Each letter of the ciphertext (secret message) is encoded as a series of five letters, using a combination of two different typefaces, which in this problem will be ‘UPPER CASE’ and ‘lower case’ letters. (Other possbililities could be bold and not bold, italics and not italics, Times Roman and Courier New.) As computer scientists, we know that five characters of two possible typefaces results in 32 possible permutations, more than enough to encode 26 letters and the space. If we interpret UPPER CASE letters as a 1 and lower case letters as a 0, we can convert each sequence of five letters into a binary number, when converted to an integer, will represent a letter from A to Z and a blank. The representation will be 0  a, 1 b, 2  c, …,

25 z, and 26  blank.

As examples, ‘HeLLo’  10110  22  W (‘HeLLo’ represents a W)

‘hElLO’  01011  11  K (‘hElLO’ represents a K)

The purpose of this problem is to decode a message represented as a Baconian cipher. You should ignore all spaces and non-alphabetic characters in the cipher. Excess letters (<5) at the end of the ciphertext should be ignored

(from GAMES, April 2006)

INPUT:Your program should accept cipher text at the prompt: “Enter text: “. You should continue accepting text until an asterisk (*) is entered at the prompt by itself. The message should now be decoded. Your program should be able to decode multiple messages. Continue accepting cipher text until ‘quit’ is entered. At this point your program should terminate.

OUTPUT:The decoded text.

EXAMPLE:Enter text: brUTe fORCe IS a StraiGHt ForwArd aPprOach to SoLviNG

Enter text: a PrOBLEm, usUAlLy DirECtLY BaSEd On tHe

Enter text: pRoblem’s StateMeNT.

Enter text: *

go directly to jail

Enter text:doinG a ThINg well is ofTen a wAstE of Time. – ROBeRt BYrNe

Enter text: *

blabber

Enter text: quitACCA Programming Contest February 25, 2006

Problem #4

THE ONE’S FUNCTION

Advanced

Source file:problem4.extension

Consider a function, which, for a given integer n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13) = 6 and f(1) = 1. The purpose of this problem is to compute f(n) for any n supplied on input and to compute the next largest n after n=1 such that f(n) = n.

INPUT:Your program should accept an integer to represent n at the prompt: “Enter n: “. Your program should continue to accept inputs until a zero is entered. At this point your program should compute and output the next largest n after n=1 such that f(n) = n. Your program will then terminate

OUTPUT:For the first part of the program, your output should be of the form: ‘f(N)=XXX’ where N is the input entry and XXX is the value of f(N).

The second part of the program, your output should be of the form: ‘f(n)=n at n=YYY’ where YYY is the value of n such that f(n) = n.

EXAMPLE:Enter n: 111

f(111)=36

Enter n: 12

f(12)=5

Enter n: 0

f(n)=n at n=3111 (NOTE: This is not the correct value for n)

ACCA Programming Contest February 25, 2006

Problem #5

MAGIC CUBES

Advanced

Source file:problem5.extension

A magic cube of order n is a cubical (three-dimensional) array

Mn = [ mn(i, j, k); 1 ≤ i,j,k ≤ n]

of the integers from 1 to n3 such that the sums of the numbers along each row, column, and along each of its four great diagonals are the same, i.e. n(n3+1) / 2. The following shows the magic cube M3. The element m3(1, 1, 1) = 8 is in three rows containing the triples {8,15,19}, {8,24,10}, {8,12,22}. On the four diagonals there are the triples {8,14,20}, {19, 14, 9}, {10,14,18} and {6,14,22}. All of these triples sum to 42.

Here is an algorithm for making magic cubes of order n ≠ 2 and n ≠ 2 (mod 4).

1. If n 1 (mod 2) then mn(i, j, k) = ai,j,kn2 + bi,j,kn + ci,j,k + 1 with ai,j,k = (i - j + k - 1) mod n,

bi,j,k = (i - j - k) mod n, and ci,j,k = (i + j + k - 2) mod n.

2. If n 0 (mod 4) then mn(i, j, k) =

where f(i,j,k) = , and

The purpose of this program is to generate a magic cube given a value for n between 3 and 12, inclusive.

INPUT:Your program should accept an integer to represent n at the prompt: “Enter n: “. Your program should continue to accept inputs until a zero is entered. At this point your program should terminate.

OUTPUT:Your output should be in the form of three slices out of the cube. See the example output on the back. If a value for n is entered that does fit the above algorithm, out the message: ‘Invalid input’.

EXAMPLE:On back

EXAMPLE:Enter n: 3

8 15 19

24 1 17

10 26 6

12 25 5

7 14 21

23 3 16

22 2 18

11 27 4

9 13 20

Enter n: 8

449 63 451 61 60 454 58 456(This is the last slice! You would

56 458 54 460 461 51 463 49 have to output all slices.)

465 47 467 45 44 470 42 472

40 474 38 476 477 35 479 33

32 482 30 484 485 27 487 25

489 23 491 21 20 494 18 496

16 498 14 500 501 11 503 9

505 7 507 5 4 510 2 512

Enter n: 0

ACCA Programming Contest February 25, 2006

Problem #6

FUNCTION F

Advanced

Source File:problem6.extension

A function f is defined on the positive integers by:

f(1) = 1, f(3) = 3,

f(2n) = f(n),

f(4n + 1) = 2f(2n + 1) – f(n),

f(4n + 3) = 3f(2n + 1) – 2f(n),

for all positive integers n.

Your task is to determine the number of positive integers n ≤ 2006 for which f(n) = n. Note that there at least 2 as given in the function definition.

INPUT:No input.

OUTPUT:Output should be of form: "Number of positive integers for which f(n)=n : xxxx”.

EXAMPLE:Number of positive integers for which f(n)=n : 2006 (Not the correct result!)

ACCA Programming Contest February 25, 2006

Problem #7

TWENTY-FOUR

Advanced

Source file:problem8.extension

TWENTY-FOUR was a game popular in the late 80’s and early 90’s. The object of the game is to make 24 from four numbers (each > 0) supplied to you on a card. You can add, subtract, multiply or divide the numbers. You must use all four numbers, but use each number only once. For example, on the sample card shown, one can achieve 24 by 8 / 4 + 6 * 3, when the operations are performed from left to right without regard to algebraic precedence rules. There could be other solutions. (Note: x / y can only be performed if y divides into x evenly, that is, x mod y = 0.)

The purpose of this program is, when given 4 numbers, determine the order to apply the operations to obtain 24. You need only supply one solution.

INPUT:Your progam should accept four integers separated by spaces as input with the prompt: “Enter four numbers: “. Your program should continue to accept inputs until four zeroes are entered. At this point your program should terminate. You may assume that each set of four numbers can achieve 24 in a left to right evaluation.

OUTPUT:Your output should be of the form:n1 op1 n2 op2 n3 op3 n4

where n1, n2, n3, n4 represent each of the four numbers and op1, op2, op3 represent each operation. to perform in order from left to right. All operations are assumed to have the same precedence. Therefore, the operations will be performed in order from left to right.

EXAMPLE:Enter four numbers: 3 4 6 8

8 / 4 + 6 * 3

Enter four numbers: 4 8 1 8

8 * 4 – 8 * 1

Enter four numbers: 6 6 4 1

4 – 1 * 6 + 6

Enter four numbers: 3 9 9 5

9 * 5 / 3 + 9

Enter four numbers: 0 0 0 0

ACCA Programming Contest February 25, 2006

Problem #8

CHINESE ZODIAC

Advanced

Source file:problem8.extension

The Chinese Zodiac consists of a 12 year cycle, where each year is named after a different animal that imparts distinct characteristics to its year. Many Chinese believe that the year of a person’s birth is the primary factor in determining that person’s personality traits, physical and mental abilities and degree of success and happiness throughout his lifetime. To learn about your Chinese Zodiac sign, visit a local Chinese restaurant. The purpose of this problem is to determine the animal for any year from 1500 to 2600, inclusive, that the year is named after.

The following lists a 12-year cycle of years along with the animal after which that year is named.

1936Rat

1937Ox

1938Tiger

1939Rabbit

1940Dragon

1941Snake

1942Horse

1943Ram

1944Monkey

1945Cock

1946Dog

1947Boar

Since the Chinese Zodiac is on a 12-year cycle, then 1948 would be the Year of the Rat again and 1949 would be the Year of the Ox, etc.

INPUT:Your program should accept an integer at the prompt: “Enter a year: “ and validate the entry. Your program should continue to accept inputs until a zero is entered. At this point your program should terminate.

OUTPUT:For each year entered, output the animal the year is named for in the following format:

YEAR OF THE XXXXX

where XXXXX is the animal name in uppercase letters.

For invalid inputs, output: “Invalid entry, please re-enter” and prompt again for a year.

EXAMPLE:Enter a year: 1967

YEAR OF THE RAM

Enter a year: 1616

YEAR OF THE DRAGON

Enter a year: 2064

YEAR OF THE MONKEY

Enter a year: 1492

Invalid entry, please re-enter

Enter a year: 0