Author: Andoko Chandra
You can calculate the probability with this formula:
Pi: the probability of ball number i will pop up.
Fi: the frequency of each number in your winning number.
T: the number of different ball in your winning number.
Explanation: Multiply all of your numbers’ odds to get the probability that your number is the winning number in the exact order. Since order doesn’t matter, you should multiply this result with its permutation, and don’t forget to handle duplicate element in the permutation.
The author, Andoko Chandra, together with Felix Halim code this in Java using BigDecimal (to avoid precission error) while I try to code in C/C++ using a mere double data type. Surprisingly, mine and theirs gave the same result. To handle the output formatting in C/C++ when you work with double data type, you can exploit sprintf and sscanf function like this:
int b; char s, a; sprintf( s, "%.5le", ans ); sscanf( s, "%[^e]e%d", a, &b ); printf( "%s x 10^%d\n", a, b );
This problem was solved by 16 teams. The first team to solve this problem: whatever from National Taiwan University, minute 77.