Problems - 1997 National Championship
PROBLEM 1: Stamps

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

For example, consider stamps whose values are limited to 1 cent and 3 cents; you can use at most 5 stamps. It's easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren't much harder:

  • 6 = 2*3
  • 7 = 2*3+1
  • 8 = 2*3+2*1
  • 9 = 3*3
  • 10 = 3*3+1
  • 11 = 3*3+2*1
  • 12 = 4*3
  • 13 = 4*3+1.

However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13.

The first line of the input file has K, the total number of stamps that can be used, followed by N, the number of stamp values. The second and subsequent lines list all the N stamp values, 15 per line. Your job is to compute and print M, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set.

It is promised that 1 <= N <= 500 and 1 <= K <= 500. No stamp value will exceed 10,000. Long integers (signed 32-bit) will be adequate for all solutions. It is not promised that it is possible to write a program that can solve a large case within the allotted time limit.

SAMPLE INPUT (file INPUT.TXT): 

5 2 
1 3

SAMPLE OUTPUT (file OUTPUT.TXT): 

13

[Problem|Data|Solutions]

PROBLEM 2: Runaround Numbers

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362). Furthermore, they have a neat property, exemplified by this demonstration:

  • If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the left side when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
  • Repeat this cycle (this time for six counts) and you should end on a new digit: 2 8 1 3 6 2, namely 2.
  • Repeat again (two digits this time): 8 1
  • Continue again (one digit this time): 3
  • One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.

Given a number M, find and print the next runaround number higher than M.

SAMPLE INPUT (file INPUT.TXT): 

81361

SAMPLE OUTPUT (file OUTPUT.TXT): 

81362

[Problem|Data|Solutions]

PROBLEM 3: Humble Numbers

For a given set of K prime numbers S = {p1, p2, ... pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of 'humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number. Your job is to find the Nth humble number for a given set S.

The input file has K and N respectively on the first line with K primes on the next line.

It is promised that 1 <= K <=100 and 1 <= N <= 100,000. Long integers (signed 32-bit) will be adequate for all solutions. It is not promised that it is possible to write a program that can solve a large case within the allotted time limit.

SAMPLE INPUT (file INPUT.TXT): 

4 19
2 3 5 7
SAMPLE OUTPUT (file OUTPUT.TXT): 27

[Problem|Data|Solutions]

PROBLEM 4: Digit Pals

Consider a game played with matrix of M rows and N columns of digits 0...9, for example: 

1 3 5 2 2          
2 2 3 5 1       
1 2 3 5 5
which is referenced as row,col using indexes shown here: 
row\col a b c d e
   3:   1 3 5 2 2
   2:   2 2 3 5 1
   1:   1 2 3 5 5

The lower left corner is 1a and the upper right corner is 3e.

This game involves removing sets of digits from the matrix according to the following rules:

  • 'Digit pals' are digits of the same value which are '4-connected' (adjacent either up/down or right/left; diagonal adjacency is not considered to be 4-connected). You pick a digit and remove it and all its pals and all their pals, etc. Isolated digits (those without pals) cannot be removed. In the example above, the 1's are currently all isolated and cannot be removed. You can remove two sets of digit pals that contain the digit 2 and one each digit pals containing 3 or 5.
  • When you remove digits from a column, all the digits "slide down" to stack nicely at the bottom of the column. See the examples below.
  • If there is an empty column, i.e., the bottom row of that column is blank, the column is deleted and all the columns to its right slide left (as many times as necessary) to fill in the gap. The matrix might have new neighbors and perhaps new pals or might be completely empty.
  • The object is to remove all the pals and be left with an empty matrix. If you are left with a non-empty matrix of isolated digits, you lose the game.

For example, if you are facing 

1 2
2 1
then you lose the game.

Here is an example of a win using the 15 element matrix above.

First select 3e and remove the digit 2 pals: 

1 3 5
2 2 3 5 1
1 2 3 5 5
Next, select 2b and remove the remaining digit 2 pals. The 3 slides down: 
    5
1   3 5 1
1 3 3 5 5
Next, select 1b and remove the digit 3 pals. The 5 flows down and the right-hand three columns slide to the left. 
1   5 1
1 5 5 5
Next select 1c (or 1b or 2c) to take out the digit 5 pals: 
1
1 1

Finally, select 1a to empty the grid. You win! There were several different ways to show the sequence of plays to win this game.

Given sets of matrices, print an ordered sequence of regions to be removed that will win the game or print "NO WIN". If there are multiple sequences that win the game, you need print only one.

INPUT FORMAT

The first line of the input file is two integers representing the number of rows and number of columns. On each subsequent line, the numbers in the matrix are listed in column order starting at column a. The sample input shows the example discussed above.

The matrix will contain no more than 60 rows and no more than 26 columns. It is not promised that it is possible to write a program that can solve a large case within the alloted time limit.

SAMPLE INPUT (file INPUT.TXT): 

3 5
1 3 5 2 2
2 2 3 5 1
1 2 3 5 5

SAMPLE OUTPUT (file OUTPUT.TXT): 

3e 2b 1b 1c 1a

[Problem|Data|Solutions]