|
THE LOTTERY
The country of Elbonia runs a weekly lottery. To enter, you pick
seven numbers. Then the King picks seven numbers out of a hat,
if your ticket has three or more of the King's numbers on it - YOU WIN!!
How many tickets do you have to fill out to guarantee a win?
I'll tell your program how many numbers are in the King's hat,
and your program will "fill out" a bunch of lottery tickets.
If your tickets guarantee a lottery win, and your program needs
fewer tickets than anyone elses - you may win the next POTM!!!
Thanks for this idea go to Luc Kumps and Alfons Lievens from Belgium.
By the way - if anyone can offer an equation and proof that derives
the minimum number of tickets (given N, M, and K), Luc has offered a
GIANT box of Belgian chocolates ... mail to me and I'll send it to Luc!
(N, M, and K are defined in section II below)
Now on to the long rules. As always, the intent is to clarify the
rules and to close any loopholes - generally the POTMs should be
assumed to be fairly straightforward, but if you have any questions
just send them to me and I'll answer them in the weekly FAQ ...
I. THE ELBONIAN LOTTERY RULES AND REGULATIONS
1) The King will place N balls in a "hat". Each of the
balls will have a different number on it. The numbers
will begin at ONE and run sequentially through to N.
2) To enter the lottery, you fill out a "ticket" on which
you select SEVEN different numbers, each of which may
range from ONE to N. Your program will fill out your
tickets for you, and it may fill out as many tickets
as you wish.
3) The tension mounts. The King approaches the podium
and selects SEVEN balls (randomly) from the hat
representing SEVEN different numbers.
4) You WIN the LOTTERY if one of your tickets has THREE or more
of the King's numbers among the SEVEN on the ticket. You
WIN the POTM if you filled out fewer tickets than anyone
else, but enough tickets to guarantee that you'd have at
least one ticket with the winning three numbers on it!
II. YOUR PROGRAM AND YOUR TASK
1) M=7 is fixed. This is the number of selections on each of
your entry "tickets" and the number of balls the King picks.
2) K=3 is fixed. This is the number of the King's numbers that
you must match on your ticket in order to "win" the lottery.
3) N is the number of balls, each with a unique number on it,
that the King has in his hat. The balls are numbered from
ONE up to (and including) N. N will be provided to your
program at run time. N will be greater than SEVEN and
less than or equal to TWO HUNDRED. ( 8 <= N <= 200 )
Your program must take a single argument of the value
defining N ... for example, I may execute:
entryname 100
if the king has 100 balls in his hat. Your program must
read this argument and then print out your ticket selections.
1) Your program must print out your ticket selections with
one selection on each line - where a selection consists
of a set of exactly SEVEN unique numbers.
2) You may print out as many tickets as you wish, one per line.
3) Each ticket (line) MUST contain seven DIFFERENT numbers.
4) Your collection of tickets MUST guarantee a win for every
possible set of SEVEN numbers the King can pick.
5) Each output line (or ticket) will contain SEVEN different
numbers separated by white space, for example, 2 tickets
might be:
7 24 92 16 1 88 100
16 7 92 99 3 4 5
6) Do not print out any blank lines or extra output besides
the collection of tickets - one per line!
III. SOME RESTRICTIONS TO MAKE YOUR JOB HARDER
1) You may NOT pre-compute solutions and simply print
them out ... not even for the system test problem!
2) You must complete your task in less than ten minutes.*
3) Your source code must be less than 25K bytes.*
4) Your executable must be less than 1M bytes.*
5) All tickets go to standard output ... nothing may
be printed to standard error.
*approximately ... I will be the sole judge.
IV. THE FINALS AND THE SCORING
For the finals, I'll pick a value of N <=200 and run all the
programs. I'll examine the ticket collection that each
prints out to insure complete coverage of all possible
drawings by the King. If the entry exhibits complete coverage
and completes within a reasonable approximation of ten
minutes and is of the requisite size, it will be scored.
** THE POTM WINNER will be the program that printed out
the fewest number of tickets satisfying requirements.
** In the event of a tie (two or more programs print out
the smallest number of tickets), I'll add up all the
numbers on all the tickets - the collection with the
SMALLEST total will win the POTM.
** If still tied, the FASTEST program will win - as measured
by system+user time using the timex (times) command.
Because of the difficulty involved with scoring large values of
N, I have decided to conduct the finals in three rounds as follows:
ROUND 1: All programs will be run with a value of 2510 minutes are eliminated)
ROUND 2: All remaining programs will be run with a value of 5110 minutes are eliminated)
ROUND 3: All remaining programs will be run with a value of 101>> IMPORTANT: submit early so we can resolve any
>>> portability problems!!! (Particularly if you
>>> are working in a PC environment.
NOTE: assembly code submissions are NOT acceptable. I must be
the one to compile your code so I can check for cheating!
c) if you wish to submit a shell program, Bourne, Korn, and csh
are available ... along with any bin or /usr/bin tools that
are available as generic Unix tools - my judgement!!!
Also nawk, awk, dc, or whatever.
(again - submit early in case there are version differences)
d) Temporary files may be created in /tmp, but MUST be removed
when you are done ... creation of files anywhere else is
strictly prohibited.
e) Maximum size of the source code is roughly 25K characters -
different rules may apply for specific POTMS, and
comments don't count against you.
f) Maximum size of executable is 1 Megabyte ... please!!!!
g) Maximum malloc'able space is a bit over 50 Meg ....
h) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1
i) a = 0x80000000 = -2147483648
a - 1 = 2147483647
a + 1 = -2147483647
{a} is true. {a == 0} is false.
II. The system testing ....
a) mail me an entry as soon as possible - you can always submit
another entry if you improve your solution .. but try and
keep it down to one a week once the porting issues are
resolved .... please!
b) one entry per person (or team) please. I associate each entry
name with an email address and a person for communication
purposes. Communication is fine - and encouraged - but
everyone's code should be their own unless there is a
stated collaboration and a single team entry. Honor system!
c) on receipt of your entry, I'll run a system test to make sure
your program works ... you'll receive the results and
a weekly standing of how you fared against other entries.
(I usually will get to new mail once a night but perhaps not!)
d) please make sure your program works on the system test problem.
e) your program must perform the task specified within 10 minutes
sys+user time as measured by timex on MY execution system.
Your time will be provided along with your system test run
so you can see the differences in speed between yours and mine.
All execution time measurements used for tiebreakers (if any)
will be measured using time via timex (similar to
time command).
===> NOTE: A code fragment to measure elapsed time
===> is available from the POTM-master for the asking.
III. SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!
Please email (not uuto, no attachments) your source code to me.
IMPORTANT: Please use the following (or equivalent) lines at the
front of the program you mail to me (this will help immeasurably!):
/* POTM ENTRY: entryname (something clever please!) */
/* Your Name: First Last */
/* Your email: log@machine.att.com (or whatever) */
/* compile instructions (if other than "make entryname") */
NOTE: If you submit a shell program, please include these lines
with a leading "#" and indicate which shell to run it under!
IMPORTANT: ENTER EARLY - you will receive weekly standings and
you will resolve any portability issues early. You may improve
your entry at any time by simply sending me another entry - so it
pays to enter earlier! (I process most everything in a day or so)
Thanks! If you have any questions, mail 'em to me - if I answer them
I'll include them in the Frequently Asked Questions (FAQ) list I
circulate with the weekly standings!!! Don't call me ... please!
WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID
ERRORS I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!
=Fred
|