Lewis University



ACCA Programming Contest February 20, 2010

Problem #1

FAST TRACK

Advanced

Source File: problem1.cpp or problem1.java

Fast Track is a race between two players over a circular track created from 14 cards from a deck of playing cards. The moves for each player along the track are based on 7 playing cards dealt to each player. The player that advances the furthest along the track is declared the winner. If a player advances past the 14 cards, his moves continue back at the first card.

When moving around the track, players must obey the following rules:

1. If the card is the same color (but not the same suit or rank) as the track card that the player is on, the player advances one card forward along the track.

2. If the card is the same suit as the track card that the player is on, the player advances 2 cards forward along the track.

3. If the card is the same rank (even if the same color) as the track card that the player is on, the player advances 4 cards forward along the track.

Both players start from the first card of the 14. Play continues until all 7 of the players’ cards are applied according to the rules above.

As an example, assume that the following is the 14-card track:

(J (A (3 (4 (7 (J (6 (4 (K (9 (5 (3 (10 (A

and the player is dealt the following seven cards: (K (4 (K (4 (2 (K (5

Applying these cards in order on the track starting at the (J, the moves proceed as follows:

On (J with (K, advance 1 card to (A. On (A with (4, advance 0 cards, stay on (A.

On (A with (K, advance 2 cards to (4. On (4 with (4, advance 4 cards to (4.

On (4 with (2, advance 1 card to (K. On (K with (K, advance 4 cards to (10

On (10 with (5, advance 2 cards to (J (Note wraparound back to the start of the track)

The purpose of this problem is to determine the winner of a race between Player 1 and Player 2 and specify the card that the winner ends up on. If the race ends in a tie, this will be specified along with the card both players end up on.

INPUT: Your program should accept input from an external file. No prompts are required. The first line of the file contains the 14 cards representing the track. The second line of the file contains an integer, say N, representing the number of races to be run. On the next N pairs of lines, the 7 playing cards representing the plays for each player are listed. The first line of each pair is Player 1’s cards and the second line of each pair is Player 2’s cards. Each card is specified with the rank first followed by the suit, with at least one space separating each card. The suit symbols (, (, (, and ( are represented by S, H, D, and C, respectively. The rank 10 is represented by a 0. You may assume all input data is valid. The test data file is called: Prob1testdata.txt and is illustrated below.

OUTPUT: The output will consist of the winner (Player 1 or Player 2) and the card that the player ends on or a tie message in the following formats: Winner: Player 1 on JC

Tie: Players on 0H

EXAMPLE INPUT: JC AH 3S 4D 7D JH 6S 4S KC 9H 5S 3H 0H AC

1

KS 4C KH 4H 2C KD 5H

6C 2D 6D 0C 8S 8H AS

EXAMPLE OUTPUT: Winner: Player 1 on JC

ACCA Programming Contest February 20, 2010

Problem #2

7’s WILD

Advanced

Source file: problem2.cpp or problem2.java

This is a tabulation problem with a very simple description. Write a program that counts, for every integer from 1 to 1000, the number of squares that:

a. contain at least one 7,

b. contain exactly two sevens, and

c. contain two consecutive 7’s anywhere in the square.

and

counts the total number of 7’s in all the squares.

INPUT: No input.

OUTPUT: Four lines of output in the following form:

Total with at least one 7: XXX

Total with exactly two 7’s: XXX

Total with two consecutive 7’s: XXX

Total number of 7’s: XXX

where the XXX’s are the various counts.

EXAMPLE: Total with at least one 7: 393

Total with exactly two 7’s: 18

Total with two consecutive 7’s: 6

Total number of 7’s: 432

NOTE: The counts in the example above are not the actual results.

ACCA Programming Contest February 20, 2010

Problem #3

MONKEY BUSINESS

Advanced

Source File: problem3.cpp or problem3.java

Not everyone can speak Monkey, in fact only monkeys can speak Monkey. The syntax of the Monkey language is quite simple and is known to all, yet only monkeys can speak it flawlessly. The alphabet of the Monkey language is {a, b, c, d, #}, where # represents 1 space. The complete grammar of the Monkey language is:

( | #

( |

( | | a | a

( c a

( b | d

As director of monkey intelligence, you have just been given a machine-readable version of a transcript of a conversation among several important monkeys. There is at least one spy, and possibly more than one, in this group of monkeys. A monkey spy does not speak proper Monkey. You have been assigned the task of determining which monkeys are spies.

INPUT: The lines of dialogue from the monkey conversation will be the input. Each line of dialogue will have the name of the monkey speaker, a colon (:) character, and then the sentence spoken by that monkey. There will be no blanks (spaces) on a line, except possibly in the spoken sentence. Each sentence will be at most 100 characters long. There will be at most 25 monkeys in the conversation, and, of course, each monkey may speak more than once. The end of the conversation will be a line spoken by a monkey named ‘OMEGA’. This line should not be processed or generate any output. The test data file is called: Prob3testdata.txt.

OUTPUT: Your output should contain a list of the “spies” in their order of appearance in the conversation, one per line of output. A spy should only show up on the list once.

EXAMPLE INPUT:

CHUMP:abadad cdabcdaabadacbacbabab cbad

FRED:acbacbacda acdaadcda cdadad

SCRATCHY:cbadcdabcdad cdaacdaadcbabacba ab

CHUMP:abadabadabcbacda abadab acba cbabababcbacbab

FRED:acbaab cdacdabab

HAIRRY:acbaacdaacba ababad cdad cdacdab

SLICK:cdaabcdaadcbababacbacbadcdad acbaabacda cdaabadcbabacda

OMEGA:ad

EXAMPLE OUTPUT:

FRED

HAIRRY

ACCA Programming Contest February 20, 2010

Problem #4

ASCII and Ye Shall Receive

Advanced

Source File: problem4.cpp or problem4.java

The ASCII computer code represents the letters of the alphabet as an increasing series of binary numbers, where ‘A’ = 65 or binary 01000001, ‘B’ = 66 or binary 01000010, … and ‘Z’ = 90 or 01011010.The purpose of this problem to determine a secret word formed by 0s and 1s embedded within a text string, disguised as o’s and i’s, respectively, either in lower or upper case. The sequence of 1s and 0s in each text string will correspond to an ASCII character. For example, the text: Torsion/Inigo Montoya= t0rs10n/1n1g0 m0nt0ya = 01011000 = ‘X’.

INPUT: Your program should accept text strings at the prompt: ‘Enter text:’. Each text string entered has one and only one binary number embedded within it that represents an alphabetic character. You will continue accepting text strings until the text ‘done’ is entered. At this point you will output the word formed by the letters generated by applying the ASCII code from the first text string to last text string. Continue repeating this process of extracting words until the text ‘quit’ is entered.

OUTPUT: Output the word found in the form:

Word: XXXXXX

where XXXXXX are the letters of the word with no spaces between them.

EXAMPLE: Enter Text: Do-si-do/Opposition

Enter Text: Onion dome/Nihilistic

Enter Text: Motioning/Notorious

Enter Text: Going, Going, Gone/Igloo

Enter Text: Oink, oink/Promotion

Enter Text: Robin Hood/Orthodontia

Enter Text: Coin-Op/Prohibition

Enter Text: done

Word: FORTRAN

Enter Text: Oil Corporation/Lion

Enter Text: Potion/Toll House Cookies

Enter Text: Sorvino/Imposition

Enter Text: Polio/Voodooist

Enter Text: done

Word: JAVA

Enter Text: quit

ACCA Programming Contest February 20, 2010

Problem #5

NUMBRIX

Advanced

Source File: problem5.cpp or problem5.java

73 | | | |77 | | | |13 | | | | |81 | |1 | | | | | | | | | | | | | | | |65 | | | | | |9 | | |63 | | | | | | | |17 | | |53 | | | | | |19 | | | | | | | | | | | | | | | |49 | |31 | | | | |59 | | | |47 | | | |27 | |

Numbrix is a new puzzle that consists of a 9x9 matrix puzzle board in which several of the squares are filled in with numbers. The above puzzle is a Numbrix puzzle. To solve each puzzle, you must complete the number matrix using logic and memory.  Just fill in the puzzle so the numbers follow a horizontal or vertical path from 1 to 81 (no diagonals). The following is the solution to this puzzle.

73 |74 |75 |76 |77 |2 |3 |12 |13 | |72 |71 |70 |81 |78 |1 |4 |11 |14 | |67 |68 |69 |80 |79 |6 |5 |10 |15 | |66 |65 |40 |39 |38 |7 |8 |9 |16 | |63 |64 |41 |42 |37 |36 |35 |18 |17 | |62 |53 |52 |43 |44 |33 |34 |19 |20 | |61 |54 |51 |50 |45 |32 |23 |22 |21 | |60 |55 |56 |49 |46 |31 |24 |25 |26 | |59 |58 |57 |48 |47 |30 |29 |28 |27 | |

Your task is not to solve one of these problems. Your team has been asked by the web-site publisher of these puzzles to write a program that will verify that a user’s solution to a puzzle is correct. Your program will input a series of Numbrix puzzle solutions and determine the validity of each solution.

INPUT: The input consists of the value of N on the first line indicating the number of Numbrix puzzles that follow on the next 9*N lines. Each line consists of nine integers, separated by at least one space. Every nine lines after the first represent a puzzle solution.

OUTPUT: Output ‘valid’ if the solution is valid or ‘invalid’ if the solution is invalid.

EXAMPLE INPUT: 1

73 74 75 76 77 2 3 12 13

72 71 70 81 78 1 4 11 14

67 68 69 80 79 6 5 10 15

66 65 40 39 38 7 8 9 16

63 64 41 42 37 36 35 18 17

62 53 52 43 44 33 34 19 20

61 54 51 50 45 32 23 22 21

60 55 56 49 46 31 24 25 26

59 58 57 48 47 30 29 28 27

EXAMPLE OUTPUT: valid

ACCA Programming Contest February 20, 2010

Problem #6

INTEGER PLAY

Advanced

Source file: problem6.cpp or problem6.java

Two consecutive integers that add up to 2009 are 1004 and 1005. Seven consecutive integers that also have a sum of 2009 are 284, 285, 286, 287, 288, 289, and 290. In fact, there are three more series of consecutive integers that also have the sum of 2009. The integer 2010 is even more prolific as there are seven series of consecutive integers that sum to 2010. There are even some integers where no series of consecutive integers to that integer.

Your task in this problem is to generate all sequences of consecutive integers that add to a given integer. And if no sequences are generated, report that fact.

INPUT: Your program should accept a positive integer n (n ≤ 10000) 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: For each sequence of consecutive integers that sums to n, you should output the first integer of the sequence and the last integer of the sequence, separated by at least one space. There is no particular list order required for this output. If no sequence exists, you should output “No sequence”.

EXAMPLE: Enter integer: 2009

1004 1005

284 290

137 150

29 69

17 65

Enter integer: 88

3 13

Enter integer: 0

ACCA Programming Contest February 20, 2010

Problem #7

BIPARTITE PRIVATE KEYS

Advanced

Source File: problem7.cpp or problem7.java

The executive officers of the company where you work want to send each other encrypted messages. Rather than use off-the-shelf encryption software such as PGP, they have tasked the IT staff with handling the encryption problem. The IT staff decided on a solution that requires “public” and “private” integer keys. The idea is that everyone can see your public key, but only you know your private key.

In this company is a wonderful person but a not-so-wonderful programmer. He has created a public-private key scheme as follows. A public key can be any positive integer. The corresponding private key is the smallest bipartite number that is greater than and a multiple of the public key.

A bipartite number is any positive integer that contains exactly 2 distinct decimal digits s and t such that s is not 0 and all occurrences of s precede all occurrences of t. For example, 44444411 is bipartite (s=4 and t=1). So are 41, 10000000, and 5555556. However, neither 4444114 nor 44444 are bipartite.

Notice that a bipartite number 88888888888800000 can be nicely described as 12 8’s followed by 5 0’s. Therefore, you can express any bipartite number using four numbers: m s n t. The numbers s and t are the leading and trailing digits as described above, m is the number of times the digit s appears in the bipartite number, and n is the number of times the digit t appears.

The trouble with his scheme is that it is not too difficult to compute a private key if you know the public key. You need to convince him that his public-private key scheme is inadequate before he loses his job over his bad decision! The purpose of this program is to accept public keys as input and display the corresponding private keys in the m s n t form described above.

INPUT: Your program should accept an integer representing the public key (in the range 1 ... 99999) at the prompt: ‘Enter public key:’. Your program should continue to accept inputs until a 0 is entered. At this point your program should terminate without further output.

OUTPUT: For each input, output a line consisting of the label ‘Private key’, a colon, then 4 integers m s n t each separated by a space, where m, n, s, and t are as described above. See the examples below for the form.

EXAMPLE: Enter public key: 125

Private key: 1 5 2 0

Enter public key: 17502

Private key: 4 7 4 8

Enter public key: 2009

Private key: 3 2 3 9

Enter public key: 0

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

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

Google Online Preview   Download