TopCoder problem "WickedTeacher" used in SRM 440 (Division II Level Three)



Problem Statement

    A wicked teacher is trying to fail one of his students. He gives him the following problem:



You are given a String[] numbers containing a set of distinct integers. You can concatenate some permutation of these integers to obtain one large integer. For example, the permutation {5221, 40, 1, 58, 9} can be concatenated to form 5221401589. Find a permutation of the given numbers such that its concatenation is divisible by the integer K.



The student doesn't have a clue how to solve this problem, so he just answers with some random permutation. There may be multiple correct answers, and maybe the student has chosen one of them by chance. Return the probability that the student has chosen one of the correct answers and return it as a String in the form of an irreducible fraction "p/q" (quotes for clarity), where p is the fraction's numerator and q is its denominator. Assume that each permutation has the same probability of being chosen.
 

Definition

    
Class:WickedTeacher
Method:cheatProbability
Parameters:String[], int
Returns:String
Method signature:String cheatProbability(String[] numbers, int K)
(be sure your method is public)
    
 

Constraints

-numbers will contain between 1 and 15 elements, inclusive.
-Each element of numbers will contain between 1 and 50 characters, inclusive.
-Each element of numbers will contain digits ('0'-'9') only.
-Each element of numbers will begin with a non-zero digit.
-Elements of numbers will be distinct.
-K will be between 1 and 100, inclusive.
 

Examples

0)
    
{"3","2","1"}
2
Returns: "1/3"
If the student chooses a permutation where the number 2 is the last element, the concatenation will be divisible by 2.
1)
    
{"10","100","1000","10000","100000"}
10
Returns: "1/1"
No matter which permutation the student chooses, its concatenation will be divisible by 10.
2)
    
{"11","101","1001","10001","100001"}
10
Returns: "0/1"
It's possible that the teacher is cheating, and no correct answer is possible.
3)
    
{"13","10129414190271203","102","102666818896","1216","1217","1218","101278001","1000021412678412681"}
21
Returns: "5183/36288"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10289

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13748&pm=10289

Writer:

gojira_tc

Testers:

PabloGilberto , ivan_metelsky , Vasyl[alphacom]

Problem categories:

Dynamic Programming, Math