CharmingTickets
SRM 382 · 2007-12-11 · by dkorduban
Problem Statement
A ticket number that contains exactly 2*K digits is called charming if and only if at least one of the following conditions is satisfied:
- The sum of the first K digits is equal to the sum of the last K digits.
- The sum of all the digits at positions with odd indices is equal to the sum of all the digits at positions with even indices.
Also, you think that some digits are better than others, so a charming number must contain only digits that you consider to be good. These digits are given in the
Constraints
- K will be between 1 and 1000, inclusive.
- good will contain between 1 and 10 characters, inclusive.
- good will contain only digits ('0' - '9').
- All characters in good will be distinct.
1 "0123456789" Returns: 10
Only "XX" numbers are charming.
2 "21" Returns: 8
Only 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222 are charming numbers.
2 "0987654321" Returns: 1240
137 "0123456789" Returns: 630063
1000 "0123456789" Returns: 495241
max test
1000 "8" Returns: 1
border case: single digit
1 "2" Returns: 1
border case: single digit
123 "8123" Returns: 894140
digits aren't sorted
971 "82109467" Returns: 166953
digits aren't sorted
Submissions are judged against all 93 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CharmingTickets with a public method int count(int K, string good) · 93 test cases · 2 s / 256 MB per case