WickedTeacher
SRM 440 · 2009-05-12 · by gojira_tc
SRM 440 · 2009-05-12 · by gojira_tc · Dynamic Programming, Math
Problem Statement
Problem Statement
A wicked teacher is trying to fail one of his students. He gives him the following problem:
You are given aString[] 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 aString 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.
You are given a
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
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"
4)
{"139012963127893461274126478482"}
1
Returns: "1/1"
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WickedTeacher with a public method string cheatProbability(vector<string> numbers, int K) · 119 test cases · 2 s / 256 MB per case