PROBLEM STATEMENT
The TopCoder Super3 is a lottery in which participants purchase tickets where
they choose a 3-digit number between 000 and 999. Each day from Monday to
Friday, inclusive, the Super3 lottery randomly picks a 3-digit number and all
those people who purchased tickets for that day with that same number are
winners. The Super3 has not been too successful in selling tickets, so
TopCoder has decided to add a twist. Every Saturday, an extra drawing will
occur. People are not able to purchase tickets for this drawing, but all
tickets purchased on the Monday to Friday of that week are eligible for prizes
in this drawing if they match the winning number. Furthermore, TopCoder has
decided that all numbers that have previously occurred in a specific digit in a
winning number earlier that week cannot occur in that same digit again for the
Saturday drawing.
Given a list of winning numbers for the week, and given a list of tickets that
were purchased by one person for that week, return the probability out of 1000
that this person has a winning ticket for the Saturday drawing. If the decimal
portion of your solution is greater than or equal to .5, round up to the
nearest integer; otherwise, round down.
DEFINITION
Class: Super3
Method: winlotto
Parameters: String[], String[]
Returns: int
Method signature (be sure your method is public): int winlotto(String[]
winners, String[] purchased);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- winners will contain exactly 5 elements (winning ticket for each of Monday
through Friday, inclusive).
- purchased will contain between 0 and 20 elements, inclusive.
- each element of winners and purchased will be of length 3.
- each element of winners and purchased will only have the characters '0'-'9',
inclusive.
EXAMPLES
1) winners: {"111","222","333","444","555"}
purchased: {"666","777","888","999","000"}
For each of the three digits, the numbers 6,7,8,9,0 are possible in the
Saturday drawing. Therefore, there's a 1/5 chance of matching each of the
digits, or a 1/125 chance of matching all 3. Since there are 5 tickets, there
is a 5/125 chance of this person winning, or 40/1000.
returns: 40
2) winners: {"123","234","345","234","123"}
purchased: {"111","222","333","444","555"}
None of these tickets can possibly win, because they all contain at least one
digit which cannot possibly occur in the Saturday drawing.
returns: 0
3) winners: {"135","246","357","468","149"}
purchased: {"111","222","333","444","555","982"}
The hundreds digit cannot be 1, 2, 3, or 4, the tens digit cannot be 3, 4, 5,
or 6, and the ones digit cannot be 5, 6, 7, 8, or 9. Thus, the only purchased
ticket which has a chance of winning is "982". The chance of this ticket being
a winner is (1/6)*(1/6)*(1/5), or 1/180.
returns: 6
4) winners: {"594","234","561","578","996"}
purchased:
{"794","586","234","216","759","584","568","965","316","574","862","986","975","
782","791","298","387","474","345"}
returns: 16
5) winners: {"111","222","333","444","555"}
purchased:
{"777","777","777","777","777","777","777","777","777","777","777","777","777","
777","777","777","777","777","777","777"}
returns: 8