[ Problem F | 1992 ACM East-Central Regional problem set | My ACM problem archive | my home page]

Every Wednesday and Saturday night, thousands of Ohioans watch Karen
Harris oversee the selection of that evening's winning Super Lotto
numbers. Forty-seven numbered balls are released into a mixing
chamber, and six are randomly extracted to establish the winning
combination. Cash prizes await those who match four, five, or all six
of the winning numbers. The cash prizes increase significantly in
magnitude between these three prize levels--that's the *good*
news for lottery players.

According to the rules of combinatorics, the number or unique winning
combinations of these balls is given by the formula 47!/(6!*(47-6)!).
This means that the odds of a single wet of six numbers beting
selected is 1 is 10,737,573--and that's the *bad* news for
lottery players.

The Ohio Lottery Commission must be capable of processing millions of
tickets for each drawing. Its staff must be able to record the
numbers on each ticket sold, recall these numbers, and quickly verify
them whenever winning tickets (if any) are presented. In order to do
this effectively, a *sequence number* must be assigned to each
winning combination. This naturally entails the development of an
ordering scheme over the set of possible combinations. Note that when
viewed from this perspective, the Ohio Lottery is really picking only
one sequence number from the 10,737,573 possible combinations which
exist--the use of the individually numbered balls, while providing an
entertaining and suspense-filled method of selecting the winning
combination, also serves to somewhat conceal the true nature of the
game.

Suppose that there are to be *n* balls selected from a pool of
*m*. Consider numbering the combinations according to the
following scheme: two different combinations of balls are represented
by A1, A2, ..., A*n* and B1, B2, ..., B*n*, where
A*i* < A(*i*+1) and B*i* < B(*i*+1). To
determine which combination appears first in the ordering, each
corresponding ball number is examined beginning with A1 and B1 until a
difference is found. The combination with the lower differing number
comes earlier in the ordering. Because this produces a deterministic
ordering, sequence numbers may be applied directly.

Consider the following example: suppose that 3 balls are to be chosen from a pool of 8 to determine a winning combination. Two possible combinations are 2-3-8 and 2-4-7. Both combinations begin with a 2, so the second element of each triple must be considered. Since 3 comes before 4, the combination 2-3-8 comes earlier in the ordering. 1-2-3 is the first combination in the ordering, so it has the sequence number of 1. 6-7-8 is the last combination in this case, with a sequence number of 56.

Write a program that will accept a lottery description as outlined above (total number of balls and number of balls drawn to determine a winner) along with a sequence number for that lottery, and generate the set of winning numbers corresponding to the supplied sequence number.

All data values which appear in the input file will be positive integer values.

whereInnofmlotteries,combinationhas sequence numbers.

In each output sentence, requested lottery number combinations must be separated by hyphen characters (hyphern characters which lead off or trail behind the requested lottery combination are not acceptable). All of the characters in the output sentence must appear as given, including the comma (with its trailing space) and the period.

Should a requested sequence number not exist for an input lottery description, the output sentence should read:

Innofmlotteries, no combination corresponds to sequence numbers.

8 3 4 8 3 1 8 3 56 8 3 57 8 5 10 5 2 7 47 6 2034

In 3 of 8 lotteries, 1-2-6 has sequence number 4. In 3 of 8 lotteries, 1-2-3 has sequence number 1. In 3 of 8 lotteries, 6-7-8 has sequence number 56. In 3 of 8 lotteries, no combination corresponds to sequence number 57. In 5 of 8 lotteries, 1-2-3-7-8 has sequence number 10. In 2 of 5 lotteries, 2-5 has sequence number 7. In 6 of 47 lotteries, 1-2-3-6-14-25 has sequence number 2034.

This page maintained by Ed Karrels.

Last updated December 12, 1999