A Sum from a Set

Sum From A Set -- Page 1 of 2

Problem 1: A Sum From A Set

(Call your program sum.cpp or sum.c or sum.pas)

From the set {1, 6, 9, 17}, a subset exists whose elements sum to 7; namely, the subset {1, 6}. Similarly, the elements of the subset {6, 9, 17} sum to 32; whereas, no such subset exists whose elements sum to 12. Given a set S of positive integers, the problem is to find a subset of S whose elements sum to a given positive integer M and to output this subset. Several such subsets may exist; however, you need only find one. Numbers in the set S can be used at most once in forming the sum.

The input to the program consists of a sequence of positive integers, one number per line, followed by a negative integer (a sentinel to terminate the input). The number M is the last positive integer entered in the sequence and the set S consists of the integers entered prior to the value of M.

Your program is to process one set S with one positive integer M and output the subset, one number per line which sums to M. If no such subset exists, output “NO SUBSET EXISTS”. You may assume that the set S contains no duplicate numbers and the number of elements in the set does not exceed 50.

Here is a sample input data file, accessible to you as :\contest\sum1.dat:

-6

The set S for the above sample input data file is S = {2, 7, 13, 19, 12} and M = 21. A correct run of your program for this input data file is:

Sum Problem by <team name>

Enter file name: sum1.dat

End of Output

A second correct run of your program for this input data file is:

Sum Problem by <team name>

Enter file name: sum1.dat

End of Output

Another sample input data file, accessible to you as O:\contest\sum2.dat is:

-8

The set S for this sample input data file is S = {19, 23, 11, 22, 41} and M = 35. The correct run of your program for this input data file is:

Sum Problem by <team name>

Enter file name: sum2.dat

NO SUBSET EXISTS

End of Output

Problem 2: Savings Account Summary

(Call your program account.cpp or account.c or account.pas.)

Here is a listing of the file O:\contest\account1.dat which represents typical input for your program:

1400

4.5

3 40.88 d

3 10.60 w

3 100 d

20 40.50 w

27 125.01 w

The first line of the file contains the balance of a savings account at theend of the last day of the preceding month. The second line of the file contains the annual interest rate for the savings account. If the file contains any additional lines, they represent the transaction history for the current month. Each such line will contain:

a positive integer representing the date (day of the month) on which the transaction occurred
one or more blank spaces
the amount of the transaction
one or more blank spaces
a code ‘d’ or ‘w’ indicating a deposit or a withdrawal.

The dates of transactions will be in non-decreasing order. There may be more than one transaction on any given day. Withdrawals and deposits on a given day may be listed in any order. The total number of deposits for the month will not exceed 99. The total number of withdrawals for the month will also not exceed 99. You may assume that the current month has exactlythirty days.

The savings account’s balance will be compounded daily. For each day of the month, your program will

1)add the day’s deposits to (and subtract the day’s withdrawals from) the preceding day’s ending balance

2)add the daily interest to the balance, resulting in the ending balance for the day.

The daily interest is calculated by the formula

daily_interest = current_balance * ((annual_interest_rate / 100 )/ 365).

The current balance is evaluated after the day’s transactions have taken place.

Here is the run based on the input file listed above:

Account Problem by <team name>

Enter file name: account1.dat

PREVIOUS BALANCE: 1,400.00

2 DEPOSITS TOTALING: 140.88

3 WITHDRAWALS TOTALING: 176.11

INTEREST PAID: 5.52

NEW BALANCE: 1,370.29

End of Output

Here INTEREST PAID means the total interest paid during the currentmonth; NEW BALANCE means the balance at the end of the last day of the current month.

The input file O:\contest\account2.dat which contains the two lines:

1000.50

6.25

will yield the following run:

Account Problem by <team name>

Enter file name: account2.dat

PREVIOUS BALANCE: 1,000.50

0 DEPOSITS TOTALING: 0.00

0 WITHDRAWALS TOTALING: 0.00

INTEREST PAID: 5.15

NEW BALANCE: 1,005.65

End of Output

The file name entered by the user will not exceed 60 characters.

Formatting details:

Pay attention to the upper/lower case characters and to the absence of blank lines in the output.
On the lines which summarize deposits/withdrawals, the number of deposits/withdrawals is right-justified in columns 1 – 2 of the line; column 3 is blank. The next word of the line begins in column 4.
On the other three lines containing numerical output, columns 1 – 3 are blank and the first word of the line begins in column 4.
Consecutive words of text (such as “PREVIOUS BALANCE”) are separated by exactly one blank.
Colons are not preceded by a blank.
The decimal points are aligned in column 33. They are followed by exactly two digits.
All dollar amounts in excess of 999.99 are displayed with a comma between the thousands’ and hundreds’ places.
The largest dollar amount your program may need to output will not exceed 999,999.99.

Problem 3: Adaptive Sports Association

(Name your program ADAPTIVE.CPP or ADATPIVE.C or ADAPTIVE.PAS)

The Adaptive Sports Association (ASA) provides ski lessons for persons with disabilities at Purgatory Ski Resort. ASA is staffed mainly by volunteer ski instructors who are certified to teach people with various disabilities. When a person with a specific disability signs up for a lesson, an instructor who is certified to instruct that disability is assigned to teach the lesson.

You are to write a program to help ASA schedule its daily lessons. Three input files are available. . All input files have the same format with a name in the first 30 columns and a disability code (an integer) in the next two columns.

A file of volunteer ski instructors which contains the instructor’s last name and first name (in the first 30 columns) and a code which indicates a disability for which that instructor is certified to teach (in the next 2 columns). Instructors who are certified for more than one disability have multiple records in the file, one for each disability they are certified to teach.

A file of skiiers who have signed up for lessons consisting of the name of the person (in the same format as the instructor names) and a code which represents the disability which the person possesses. People with multiple disabilities have multiple records in the file, one record for each disability.

A disabilities file containing the name of the disability and the code assigned to that disability (again with the same file format specified above).

Your program is to process the file of skiiers (in sequential order) who have requested lessons and to assign a certified instructor to teach the lesson. The instructors must also be processed sequentially according to the order in which they appear in the instructors file. In the case of a person with multiple disabilities, assign an instructor for each disability and the ASA staff will manually decide which instructor(s) should teach the lesson.

Your program is to produce output in the format shown on the next page which represents the instruction schedule for one day. As the output format suggests, a skiier is assigned an instructor for each disability which the skiier possesses. An instructor can be assigned to only one lesson. Output is to the terminal screen.

Your program is to prompt the user for three file names representing disabilities, instructors and skiiers. Test data is available in the files DISAB.DAT, INSTRUCT.DAT and SKIIER.DAT in the O:\CONTEST directory. The example output on the next page is based upon these test files. The contents of the test data files appears below:

Contents of sample input file DISAB.DAT

Blind 10

One Leg 11

Both Legs 12

One Arm 13

Both Arms 14

Learning Disabled (1) 15

Learning Disabled (2) 16

Epileptic 17

Developmentally Disabled (1) 18

Developmentally Disabled (2) 19

Bad Back 20

Contents of sample input file INSTRUCT.DAT

Adams, Evans J 10

Adams, Evans J 11

Wixom, Jim 12

Wixom, Jim 10

Wixom, Jim 11

Jones, Bill 12

Jones, Bill 13

Jones, Bill 14

Jones, Bill 15

Contents of sample input file SKIIER.DAT

Adams, Palmer 10

Adams, Joseph 11

Williams, June 12

Williams, Melanie 10

Williams, Melanie 11

Williams, Melanie 13

Sample Output:

Adaptive Sports Program by <team name>

Disabilities File : Name of Input File? disab.dat

Instructors File : Name of Input File? instruct.dat

Skiiers File : Name of Input File? skiier.dat

For Skiier : Adams, Palmer

With Disability : Blind

Instructor Assignment : Adams, Evans J

For Skiier : Adams, Joseph

With Disability : One Leg

Instructor Assignment : Wixom, Jim

For Skiier : Williams, June

With Disability : Both Legs

Instructor Assignment : Jones, Bill

Problem 4: Coloring A Map

(Call your program coloring.cpp or coloring.c or coloring.pas)

A region of the United States consists of N states each of which borders one or more of the others. A map of the region showing these states must be colored such that no two states with a common border are the same color. The problem is to find a suitable coloring for a given region using a given number of colors, if such a coloring exists. It is known that any such map can be colored with four or fewer colors.

The first line of input contains two positive integers, separated by one blank space. The first integer represents N, the number of states in the region, and the second represents the number of colors (from 1 to 4) to be used to color the map. The colors to be used are red, yellow, green and brown, in this order. Thus, if two colors are to be used to color the states on the map, then the colors are red and yellow. Each of the remaining N lines of input describe one state and those which share a border with it. The name of the state appears in columns 1 through 14, left justified and blank filled. The name of the state is followed (beginning in column 15) by a string of 0’s and 1’s of length N. The value 1 indicates a common border; whereas, a value 0 indicates no common border.

Specifically, if N = 5, then the states are numbered from 1 to 5 according to their input order. A typical entry is

COLORADO 01001

and the string 01001 indicates COLORADO shares a common border only with states 2 and 5.

Whereas, the entry

MISSISSIPPI 11011

indicates MISSISSIPPI shares a common border with states 1, 2, 4 and 5. By convention, a state will not share a common border with itself. Viewing the strings as the row data in an N X N array produces a matrix with the properties that the main diagonal contains only zeros and it is symmetric about the main diagonal.

If the map can be colored using the specified number of colors, then the output consists of one line for each state containing the name of the state and the color used to color it. The name of the state is to appear in columns 1 through 14 and the color begins in column 15. The names of the colors are to consist of lower case letters. The states are to be output in the same order as input. If a coloring is not possible, then output the message ‘CANNOT COLOR THE REGION’.

Here is a sample input data file, accessible to you as O:\contest\color1.dat:

5 3

Colorado 01100

Wyoming 10111

Utah 11001

Montana 01001

Idaho 01110

A second sample input data file, accessible to you as O:\contest\color2.dat:

5 2

Colorado 01100

Wyoming 10111

Utah 11001

Montana 01001

Idaho 01110

Here are two runs of your program for the input files listed above:

Coloring A Map Problem by <team name>

Enter file name: color1.dat

Colorado red

Wyoming yellow

Utah green

Montana green

Idaho red

End of Output

Coloring A Map Problem by <team name>

Enter file name: color2.dat

CANNOT COLOR THE REGION

End of Output

The above examples represent actual shared border with the states. There is no guarantee the input data will reflect actual states in the United States or correctly shared borders. (Any resemblance to an actual United States map is purely coincidental; however, all maps can be represented as planar graphs and can be colored with 4 or fewer colors.) You may assume the maximum number of states in the input data will not exceed 25.

In most cases, a coloring of a map is not unique.

For Skiier : Williams, Melanie

With Disability : Blind

No Instructor Available

With Disability : One Leg

No Instructor Available

With Disability : One Arm

No Instructor Available

End Of Output

Problem 5:Tales From Decrypt

(Name your first program ENCRYPT.CPP or ENCRYPT.C or ENCRYPT.PAS)

(Name your second program DECRYPT.CPP or DECRYPT.C or DECRYPT.PAS)

One of the first applications of computers was the field of cryptography, that is, the science of creating and breaking codes. Encrypting a message entails transforming it into a form that is unintelligible to anyone who does not know the algorithm and secret key used in the encrypting process. The fact that the message is encrypted means that it can be sent over unsecured channels because if it is intercepted, it cannot be read. The intended recipient decrypts the message using the inverse of the algorithm used to encrypt it.

A public-key encryption algorithm uses a pair of keys, one that is known only to the recipient (the secret key) and one that is known to everyone (the public key). When you wish to send a message to a particular person, you begin by looking up that person’s public key. You then encrypt the message using this key and transmit the message. The recipient uses his or her secret key to decrypt the message.

The Rivest, Shamir, Adelman (RSA) public-key cryptosystem uses a pair of very large integers (B, P) as the public key and another pair of very large integers (B, S) as the secret key. The encryption process begins by breaking a message into numbers that are smaller than the bounding value (B). You then encrypt each piece of the message M using the formula:

E = MP mod B

and transmit the encrypted message E. The recipient uses the formula:

M = ESmod B

to decrypt the encrypted message, yielding the original message M.

Example: Assuming B = 143, P = 47, and S = 23

If the Message M = HI (the characters H (ASCII 48) and I (ASCII 49)), it is encrypted as follows:

H : 4847 mod 143 which yields 41

I : 4947 mod 143 which yields 83

which results in encrypted message E = 41 83

When the recipient receives the encrypted message E (41 83), it is decrypted as follows:

4123 mod 143 which yields 48 (the ASCII code for H)

8323 mod 143 which yields 49 (the ASCII code for I)

Since the original message M = HI, the decryption process is complete and correct.

For this problem, you will use the small values above for B, P and S so that we can send messages as individual characters rather than in the large pieces that practical applications using large values for B, P and S typically generate.

You are to write two programs. The first program (named ENCRYPT) will encrypt a message, character by character using the RSA public-key cryptosystem with B = 143, P = 47. The message will be stored as ASCII characters in a file (whose file name your program is to prompt the user for). To simplify your program, the input file will contain only one line of less than 80 characters. The encryption program reads the file character by character and converts each character into an integer according to the encryption formula given above. The encrypted message is then written to an ASCII (text) file as a sequence of integers separated by spaces. The first integer written to the output file represents the length of the encrypted message (the number of encrypted integers). This number is then followed by the encrypted integers. The output file name must be ENCRYPT.OUT.

Assuming the input file named NICEJOB.DAT contains the message:

NICE Job!

The ENCRYPT.OUT file created by the encryption program should contain the integers:

9 78 83 111 75 76 68 67 54 132

A sample run of the encryption program must produce the following dialogue on the terminal screen:

Encryption Program by <team name>

Name of Input File? NICEJOB.DAT

Name of Output File? ENCRYPT.OUT

End of Encryption Program

The second program (named DECRYPT) will decrypt a message (using B = 143 and S = 43) which was encrypted by the ENCRYPT program according to the RSA algorithm. The decryption program will also prompt the user for an input file name. The program will read the encrypted integers in the input file and decrypt them using the decryption formula given above. Output from this program will appear on the terminal screen. The user should see the original message which was stored in the file processed by the encryption program on the screen.