ACCA Programming Contest February 23, 2008
Problem #1
MATHEMATICAL SURVIVOR
Advanced
Source File:problem1.cpp or problem1.java
The television show “Survivor” starts with a set of people and systematically eliminates one until only one remains. Mathematical Survivor is based on this concept but with a collection of n integers, n 2. Any two integers are selected and deleted from this collection. Let’s call them x and y. Now add to the collection of integers the result of xy + x + y. Now the collection has n-1 integers. Repeat the process on this new collection until only one integer remains. This integer is the “Mathematical Survivor”.
The purpose of this problem is to play the game of Mathematical Survivor on a given collection of integers that you will create from a specification of the collection. Your output will be the Mathematical Survivor for that collection.
INPUT:Your program should accept collection specifiers of the following forms at the prompt: “Enter specification: “. The collection specifiers are defined as follows:
in: The collection of integers from 1 to n
en: The collection of even integers from 2 to n with n being even
on: The collection of odd integers from 1 to n with n being odd
cn: The collection of n copies of an integer v entered at another prompt “Enter value: “
Your program should continue to accept collection specifiers until the specifier ‘q’ is entered. At this point your program should terminate.
OUTPUT:Your program should output the Mathematical Survivor in the form:
The Mathematical Survivor is XXXXX
EXAMPLE:Enter specification: i5
The Mathematical Survivor is 719
Enter specification: e6
The Mathematical Survivor is 104
Enter specification: o3
The Mathematical Survivor is 7
Enter specification: c4
Enter value: 3
The Mathematical Survivor is 255
Enter specification: q
ACCA Programming Contest February 23, 2008
Problem #2
ARITHMETIC SEQUENCES
Advanced
Source file:problem2.cpp or problem2.java
The purpose of this problem is to determine the next integer in a sequence of integers. A sequence of integers that have a common difference between successive pairs of integers is called an arithmetic sequence. A simple example of this is the arithmetic sequence: 2, 4, 6, 8. The next integer in this sequence is 10 as the common difference between the integers in the sequence is 2, 2, and 2. A more complicated example is the arithmetic sequence: 20, 28, 40, 56. This sequence does not have a common difference as the successive differences are: 8, 12, and 16. But now taking the successive differences of this new sequence results in: 4 and 4. So adding 4 to 16 gives the next integer in the 8, 12, 16 sequence as 20. And then adding 20 to the last integer in the original sequence gives 76 as the next integer in that sequence. This multilevel analysis is applied repeatedly to any arithmetic sequence until a common difference is found. Once that common difference is found, the next integer in the arithmetic sequence can be determined by working back up the levels of sequences.
INPUT:Your program should accept an arithmetic sequence at the prompt: “Enter a sequence: “. An integer value of 0 terminates the sequence. Your program should continue accepting arithmetic sequences until only a 0 is entered. At this point your program should terminate.
OUTPUT:Your output should be of the form: The next integer is XXXXX
EXAMPLE:Enter a sequence: 2 4 6 8 0
The next integer is 10
Enter a sequence: 20 28 40 56 76 0
The next integer is 100
Enter a sequence: 0
ACCA Programming Contest February 23, 2008
Problem #3
NINES
Advanced
Source File:problem3.cpp or problem3.java
In the first 10 integers, the digit 9 appears in only one of them (10%). Of the first 100 integers, 19 integers have the digit 9 in them, which is 19%. What is the percent of integers containing the digit 9 of the first 1000 integers? 10,000 integers? And so on.
The purpose of this problem is to generate a table which lists the percentages of integers containing the digit 9 of the first 10i integers, 1 ≤ i ≤ 8.
INPUT:There is no input to this problem.
OUTPUT:A table, where each line contains the power of 10 along with the percent of integers containing the digit 9 of the first 10 to the power integers. The percent should be displayed to 1 decimal place. The table should be in columns.
EXAMPLE:110.0%
219.0%
327.1%
. .
. .
ACCA Programming Contest February 23, 2008
Problem #4
THE M:I CODE
Advanced
Source File:problem4.cpp or problem4.java
On December 17, 1967, the television series ‘Mission: Impossible’ aired an episode entitled, “The Photographer”.In this episode, the IM force, among other tasks, were to obtain the key to a code so that they could decipher a secret message that spells out an imminent attack on the U.S. Your task, if you decide to take it, is to apply the key to create the superkey, decipher the code using the decoding algorithm, and report the contents of the secret message. As always, should you or any of your teammates be caught fumbling this task, the Secretary of ACCA will disavow any knowledge of your actions. This problem will self-destruct in five seconds. Good luck, team.
The following is the algorithm for enciphering (coding) a message from the key: ‘photographer’ (This is the one used in the episode.) along with an example.
Step 1: Write down the key, eliminating duplicate characters found after their first occurrence.
p h o t g r a e
Step 2: Append to this string of letters the rest of the letters of the alphabet not found in the key in alphabetical order. This forms the superkey.
p h o t g r a e b c d f i j k l m n q s u v w x y z
Step 3: Using a phone numbers found on a particular page of the yellow pages in the phone book, code each letter of the message by counting from that letter to the right over the number of letters represented by the digit of the phone number. The letter you end up on is the encoding for the letter in the message. Repeat this step for the entire message.
Enciphering the message: ‘Attack at midnight’
Using the phone numbers: 820-5699, 585-9417, and 907-9718, in that order
A t t a c k a t m i d n i g h t
8 2 0 5 6 9 9 5 8 5 9 4 1 7 9 0
k r t f l x l b y n s v j f d t
The encoded message: krtflxlbynsvjfdt
Note: Treat the alphabet string as circular, that is, if your count takes you off the right end, continue your count at the left end.
REMEMBER, your task is to decode a message, not encode.
INPUT:Your program should accept in the following order: the key (≤ 20 characters) , a line of four telephone numbers in the format given, and the encoded message (≤ 28 characters) using prompts as indicated in the example below. Your program should continue to accept inputs until ‘quit’ is entered. At this point your program should terminate.
OUTPUT:Output the decoded message in the form: ‘Message = XXXXXXXXXXXXXXXX’
EXAMPLE:Enter key: photographer
Enter phone numbers: 820-5699 585-9417 907-9718 898-1981
Enter encoded message: krtflxlbynsvjfdt
Message = attackatmidnight
Enter key: quit
ACCA Programming Contest February 23, 2008
Problem #5
KNIGHT ON A PHONE KEYPAD
Advanced
Source File:problem5.cpp or problem5.java
Everyone is familiar with the standard telephone keypad
Assume a knight from the chessboard has hopped onto the keypad onto one of the keys. The purpose of this problem is to determine the number of unique simple paths a knight can travel around the keypad starting at a given key. A simple path is a path that begins at a key, passes through every key once and only once, and ends at some key. The key that ends the simple path does not have to be same key that begins the simple path.
A knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The complete move looks like the letter 'L'. The following diagram shows the squares (marked with white circles) that a knight can move to from its current position.
A valid simple path starting at the 0 on the keypad is: 0-4-3-8-1-6-7-#-5-*-9-2.
INPUT:Your program should accept an input representing the key at the prompt: “Enter key: “. Your program should continue to accept inputs until a ‘q’ is entered. At this point your program should terminate.
OUTPUT:Your output should be in the form: “Number of unique paths = XX”.
EXAMPLE:Enter key: 5
Number of unique paths = 0
Enter key: q
ACCA Programming Contest February 23, 2008
Problem #6
DECIMATION
Advanced
Source file:problem6.cppor problem6.java
A long time ago, the lawful penalty for mutiny was to execute one-tenth of the crew. Custom ordained that the victims be selected by counting off every tenth man from a random arrangement of the crew in a circle. Hence, the term decimation. This term has come to be applied to any selection of an assemblage by a fixed interval, regardless of whether the interval is ten or another number.
The Turks and the Christians is a very old puzzle about decimation and is listed in one of Martin Gardner’s books. The story goes that 15 Turks and 15 Christians were aboard a ship, preparing for a big feast. The captain realized that food stuffs were low and only half his passengers could partake in the feast. The rest were to have peanut butter and jelly sandwiches. In order to leave the selection of feast participants to chance, the captain ordered that all 30 be arranged in a circle, with the announced intention of counting off every thirteenth man, starting with the first. The first 15 counted off would participate in the feast. A clever Christian pointed out to his fellow Christians how to take places in the circle so that all 15 Christians would be able to participate in the feast.
The purpose of this problem is to determine the positions of the Christians in the circle so that when the captain counts off every nththththt man starting with the first, only the Christians will participate in the feast.
INPUT:Your program should accept an integer representing the count-off number at the prompt: “Enter the count-off value: “. Your program should continue to accept inputs until a zero is entered. At this point your program should terminate.
OUTPUT:Your output should be a string of C’s (for Christian) and T’s (for Turk) where each C or T indicates the position of a Christian and Turk, respectively, such that all Christians will be counted out first. The count will start with the first character in the output string.
EXAMPLE:Enter a count-off value: 13
TTTTTCCCCTTCCTCTTCTCTCCTCCTTCC
Enter a count-off value: 3
TTCCTCTCCTTCCTCTCCTTCCTCTTCTTC
Enter a count-off value: 0
ACCA Programming Contest February 23, 2008
Problem #7
WORD PALINDROMES
Advanced
Source File:problem7.cpp or problem7.java
The purpose of this problem is to determine whether a complete sentence is a word palindrome; that is, the words of the sentence read the same forwards and backward. Here are two examples, “That is not, is that?” and “Girl, bathing on Bikini, eyeing boy, finds boy eyeing bikini on bathing girl.”
A few rules:
1.Words in the sentences may consist of upper and lower case letters and apostrophes.
2.Words are not case sensitive. “That” and “that” in the example sentence above are treated as the same word.
3.Words are terminated by either a space, any punctuation other than apostrophes, or end of line.
INPUT:Your progam should accept a sentence as input with the prompt: “Enter a sentnece: “. Your program should continue to accept inputs until “quit” is entered as the only input value. At this point your program should terminate.
OUTPUT:Your output should be of the form:This is a sentence palindrome. Or
This is not a sentence palindrome.
EXAMPLE:Enter a sentence: That is not, is that?
This is a sentence palindrome.
Enter a sentence: Quit or continue, why o why, continue or quit.
This is a sentence palindrome.
Enter a sentence: How now brown cow know how.
This is not a sentence palindrome.
Enter a sentence: Girl, bathing on Bikini, eyeing boy, finds boy
eyeing bikini on bathing girl.
This is a sentence palindrome.
Enter a sentence: quit
ACCA Programming Contest February 23, 2008
Problem #8
SUDOKU
Advanced
Source File:problem8.cpp or problem8.java
Test Data File:TestSudoku.txt
Has anyone not seen a Sudoku puzzle? A Sudoku puzzle is a 9x9 grid with some numbers from 1 to 9 entered. The object is to complete the Sudoku by filling in the remaining blank grid elements with the numbers from 1 to 9 such that the numbers 1 through 9 occur exactly once in each row, column, and 3x3 box.
Here is a Sudoku puzzle on the left and its solution on the right.
Now some person messed up the solutions at the back of the Sudoku magazine to be published next week. That person switched the position of two of the numbers in some of the Sudoku solutions. They need someone to write a program that will quickly determine if a Sudoku is a valid Sudoku or not. That someone is your team! If it is not a valid Sudoku, your team must report the row and column positions of the two offending numbers.
INPUT:The input will come from a text file. The first line of the text file contains an integer indicating the number of Sudoku solutions in the file. Following this line will be lines consisting of nine integers. The first nine of these lines represents Sudoku 1, the next nine lines represents Sudoku 2, and so on. You should use file redirection to access this data. There should be no prompts for input for this problem.
OUTPUT:Your output should be a line of the form:
“Sudoku X: CORRECT” or
“Sudoku X: (i,j) AND (k,l) HAVE BEEN SWITCHED”
where X is the number of the Sudoku in the file and i,j and k,l are the row, column pairs of the two switched numbers in the solution.
EXAMPLE: The following is the correct output when processing the data in the test file.
Sudoku 1: CORRECT
Sudoku 2: (4,3) AND (4,7) HAVE BEEN SWITCHED
Sudoku 3: (3,3) AND (7,7) HAVE BEEN SWITCHED