Description

Stamps

You are going to help the Ruritanian Postal Service (RPS) design their new postage software. The software allocates stamps to customers based on customer needs and the denominations that are currently in stock.

Now, Ruritania is filled with stamp collectors. To provide service to them, the RPS asks that all stamp allocations have the maximum number of different types of stamps in it. Furthermore, the RPS often issues several stamps of the same denomination in order to please customers (these count as different types, even though they have the same denomination). The maximum number of different types of stamps issued at any time is 25.

To save money, the RPS would like to issue as few duplicate stamps as possible (given the constraint that they want to issue as many different types). Further, the RPS won’t sell more than 4 stamps at a time for a customer. The RPS wants to determine the “best” combination that is exactly equal to the customer’s needs, with a maximum of 4 stamps. The “best” combination is defined as the maximum number of different stamp types. There can exist several valid stamps combinations at a time, which is so called a “tie”. In case of a “tie”, the combination with the fewest total stamps is best. If still tied, the set with the highest single-valued stamp is the best. If there is still a tie, the system will print ”tie”. For example, in the sample test input, input-02.txt, the set of stamps is (1, 1) and one customer requests 3 as the total denomination. The customer can choose either a combination with two of the 1st type and one of the 2nd type stamps, or a combination with one of the 1st type and two of the 2nd type stamps. Thus, there is a “tie” in between of the two combinations.

Here the program outputs the solution for a set of 2 different stamps and a set of 4 customers’ needs. This is the same as test input, input-03.txt.

For this project, you’re going to implement a program, stamp, that tells whether a customer request can be fulfilled by a valid combination of stamps, or there is a “tie” for possible valid combinations, i.e., it meets the requirements given above with or without a “tie”, or is invalid (“none”) because it does not meet the requirements. Also, your program should assume that the different types of stamps have denominations within the range of 1-25.

To help get you started, we’re providing you with a test script, and several test input files and expected output files. See the Getting Started section for instructions on how to set up your development environment so that you can be sure to submit everything needed when you’re done.

This project supports a number of our course objectives. See the Learning Outcomes section for a list.

In the design section, you’ll see some instructions for how your implementation is expected to work. Be sure you follow these rules. It’s not enough to just turn in a working program; your program has to follow the design constraints we’ve asked you to follow. This helps to make sure you get some practice with the parts of the language we want to make sure you’ve seen.

Requirements

Requirements are a way of describing what a program is supposed to be able to do. In software development, writing down and discussing requirements is a way for developers and customers to agree on the details of a system’s capabilities, often before coding has even begun. Here, we’re trying to demonstrate good software development practice by writing down requirements for our program, before we start talking about how we’re going to implement it.

Program Input

The stamp program reads input from standard input with a pair of the number of stamps’ types (stpNum) and the number of customers (cusNum) separated by a space, followed by a pair of positive integer sequences consisting of two lines. The first sequence are the available values of stamps, while the second sequence is a series of customer requests. For example, the input below is equivalent to input-01.txt

1     3 # one stamp type and three     customers

2     # stamp type

4 7 6 # customers

Note: the comments in this example are *not* part of the data file; data files contain only integers.

Invalid Input

If the number of stamp types is not valid because it is not an integer between 1 and 25, the program should print a line with the following message terminate with an exit status of 1.

Invalid number of types

If the denomination of a stamp type is not valid because it is not an integer between 1 and 25, the program should print a line with the following message and terminate with an exit status of 1. Invalid denomination

Program Output

For each customer, you should print the “best” combination that is exactly equal to the customer’s needs, with a maximum of 4 stamps. If no such combination exists, print ”none”.

Again, the ”best” combination is defined as the maximum number of different stamp types. In case of a tie, the combination with the fewest total stamps is best. If still tied, the set with the highest single-value stamp is best. If there is still a tie, print ”tie”.