Csc.csudh.edu



Problem 1: Sum it Up

Source file: sumitup.{c|cpp|java}

Input file: sumitup.in

Output file: sumitup.out

Problem description:

Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is {4,3,2,2,1,1}, then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

Input:

The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1, x2, …, xn. If n=0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and x1, x2, … xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in non-increasing order, and these may be repetitions.

Output:

For each test case, first output a line containing “Sum of “, the total, and a colon. Then output each sum, one per line; if there are no sums, output the line “NONE”. The numbers within each sum must appear in non-increasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number, and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.

Example:

Input:

4 6 4 3 2 2 1 1

5 3 2 1 1

400 12 50 50 50 50 50 50 25 25 25 25 25 25

0 0

Output:

Sums of 4:

4

3+1

2+2

2+1+1

Sums of 5:

NONE

Sums of 400:

50+50+50+50+50+50+25+25+25+25

50+50+50+50+50+25+25+25+25+25+25

Problem 2: Palindromes

Source file: palind.{c|cpp|java}

Input file: palind.in

Output file: palind.out

Problem description:

A palindrome is a string that reads the same forward (from left to right) and backward (from right to left). An L-palindrome is a string which is a palindrome if you ignore its first character. An R-palindrome is a palindrome if its last character is ignored. Your job is, given a string, to decide whether it is a palindrome, an L-palindrome, or an R-palindrome.

Input:

Each input line contains only a string of at least 1 and at most 25 uppercase letters. End of input is signaled by a line containing only the word END, which should be processed.

Output:

For each input string, output one or more of the following messages:

is not any type of palindrome.

is a palindrome.

is an L-palindrome.

is an R-palindrome.

where is the input string in the input file.

If more than one message applies, they should be output in the order given above. Leave a blank line after the output for each input string.

Example:

Input:

HELLOWORD

OTTO

OTTOR

LTOOT

AAAAAA

TOTO

Output:

HELLOWORD is not any type of palindrome.

OTTO is a palindrome.

OTTOP is an R-palindrome.

LTOOT is an L-palindrome.

AAAAAA is a palindrome.

AAAAAA is an L-palindrome.

AAAAAA is an R-palindrome.

TOTO is an L-palindrome.

TOTO is an R-palindrome.

Problem 3: Word Transformation

Source file: word.{c|cpp|java}

Input file: word.in

Output file: word.out

Problem description:

A common word puzzle found in many newspapers and magazines is the word transformation. By taking a starting word and successively altering a single letter to make a new word, one can build a sequence of words which changes the original word to a given end word. For instance, the word ``spice'' can be transformed in four steps to the word ``stock'' according to the following sequence: spice, slice, slick, stick, stock. Each successive word differs from the previous word in only a single character position while the word length remains the same.

Given a dictionary of words from which to make transformations, plus a list of starting and ending words, your job is to write a program to determine the number of steps in the shortest possible transformation.

Input:

The input will be a single file in two sections. The first section will be the dictionary of available words with one word per line, terminated by a line containing an asterisk (*) rather than a word. There can be up to 200 words in the dictionary; all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.

Following the dictionary are pairs of words, one pair per line, with the words in the pair separated by a single space. These pairs represent the starting and ending words in a transformation. The pairs are terminated by the end-of-file. All pairs are guaranteed to have a transformation using the dictionary given. The starting and ending words will appear in the dictionary.

Output:

The output should contain one line per word pair, and must include the starting word, the ending word, and the number of steps in the shortest possible transformation, separated by single spaces.

Example:

Input:

dip

lip

mad

map

maple

may

pad

pip

pod

pop

sap

sip

slice

slick

spice

stick

stock

*

spice stock

may pod

Output:

spice stock 4

may pod 3

Problem 4: Slurpys

Source file: slurpys.{c|cpp|java}

Input file: slurpys.in

Output file: slurpys.out

Problem description:

A Slurpy is a character string that consists of a Slimp followed by a Slump, which are defined as follows:

A Slump is a character string that has the following properties:

1. Its first character is either a 'D' or an 'E'.

2. The first character is followed by a string of one or more 'F's.

3. The string of one or more 'F's is followed by either a Slump or a 'G'.

The Slump or 'G' that follows the F's ends the Slump. For example

DFFEFFFG is a Slump since it has a 'D' for its first character,

followed by a string of two F's, and ended by the Slump 'EFFFG'.

4. Nothing else is a Slump.

A Slimp is a character string that has the following properties:

1. Its first character is an 'A'.

2. If it is a two character Slimp then its second

and last character is an 'H'.

3. If it is not a two character Slimp then it is in

one of these two forms:

a. 'A' followed by 'B' followed by a Slimp

followed by a 'C'.

b. 'A' followed by a Slump (see above)

followed by a 'C'.

4. Nothing else is a Slimp.

Examples:

Slumps: DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG

Not Slumps: DFEFF, EFAHG, DEFG, DG, EFFFFDG

Slimps: AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC

Not Slimps: ABC, ABAH, DFGC, ABABAHC, SLIMP, ADGC

Slurpys: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG

Not Slurpys: AHDFGA, DFGAH, ABABCC

Your program will read in strings of characters and output whether or not they are Slurpys.

Input:

The first line contains an integer N between 1 and 10 describing how many strings of characters are represented. The next N lines each contain a string of 1 to 60 alpha characters.

Output:

The first line of output should read SLURPYS OUTPUT. Each of the next N lines of output should consist of either YES or NO depending on whether or not the corresponding input line is a Slurpy. The last line of output should read END OF OUTPUT.

Example:

Input:

2

AHDFG

DFGAH

Output:

SLURPYS OUTPUT

YES

NO

END OF OUTPUT

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

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

Google Online Preview   Download