A DAY AT THE POST OFFICE
All submissions for this problem are available.
Chintoo is pursuing his B.Tech degree in Computer Science & Engineering from Shivaji College of Engineering. He arrives at the post office one day and happens to get engrossed in an interesting chat with the the postmaster. He gets interested in the problems of the post office. The postal service works to minimize the number of stamps needed to provide seamless postage coverage. Chintoo thinks of writing a program to assist the postal service.
Envelope size restricts the number of stamps that can be used on one envelope.For example, if Re. 1 and Rs. 3 stamps are available and an envelope can accomodate 5 stamps, all postage from Rs. 1 to 13 can be "covered" :
|Postage||No. of Re. 1 stamps||No. of Rs. 3 stamps|
Although five Rs. 3 stamps yield an envelope with Rs. 15 postage, it is not possible to cover an envelope with Rs. 14 postage using at most five Re. 1 and Rs. 3 stamps. Since the postal service wants maximal coverage without gaps, the maximal coverage is Rs. 14.
The first line of each data set contains the integer S, representing the maximum no. of stamps that an envelope can accomodate. The second line contains the integer N, representing the number of sets of stamp denominations in the data set.Each of the next N lines conatins a set of stamp denomnations. The first integer on each line is the number of denominations in the set, followed by a list of stamp denominations , in order from smallest to largest, with each denomination separated from others by one or more spaces.There will be atmost S denominations on each of the N lines.The maximum value of S is 10,the largest stamp denomination is 100, the maximum value of N is 10. The input is terminated by a data set beginning with zero ( S is zero).
Output one line for each of the data sets giving the maximum no-gap coverage followed by the stamp denominations that yield that coverage in the following format :
max coverage = (value) : (denominations)
If more than one set of denominations in a set yield the same maximal no-gap coverage, the set with the fewest number of denominations should be printed (this saves on stamp printing costs). If two sets with the same number of denominations yeild the same maximal no-gap coverage , then the set with the lower maximum stamp denomination should be printed. For example, if five stamps fit on an envelope then stamp sets of 1,4 ,12,21 and 1,5,12,28 both yield maximal no-gap coverage of Rs. 71. The first set would be printed because both sets have the same number of denominations but the first set's largest denomination(21) is lower than that of the second set (28). If multiple sets in a sequence yeild the same maximal no-gap coverage, have the same number of denominations, and have equal largest denominations, then any one of the sets is acceptable.
Input: 5 2 4 1 4 12 21 4 1 5 12 28 6 2 3 1 5 8 4 1 5 7 8 0 Output: max coverage = 71 : 1 4 12 21 max coverage = 48 : 1 5 7 8
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.