Connection Status:
Competition Arena > FourDistinctDigits

FourDistinctDigits

TCO19 Semifinal 2 · 2019-11-14 · by misof

TCO19 Semifinal 2 · 2019-11-14 · by misof · Math, Search
Class Name: FourDistinctDigits
Return Type: String
Method Name: find
Arg Types: (long long, int, int)
Problem Statement

Problem Statement

The time limit for this problem is 5 seconds.

You are given positive integers N. D and B. Find any positive integer X with the following properties:

  • X is a multiple of N.
  • When written in base B, X has exactly D digits.
  • When written in base B, X has at most four distinct digits.

Return a String of length D containing the base-B representation of X. Use 'A'-'Z' for digits 10-35, and 'a'-'z' for digits 36-61. For the given constraints a solution always exists, and any valid solution will be accepted.

Notes

  • The returned string cannot start with a zero.

Constraints

  • N will be between 1 and 10^11, inclusive.
  • D will be between 40 and 120, inclusive.
  • B will be between 5 and 62, inclusive.
Examples
0)
4247
40
10
Returns: "4247424742474247424742474247424742474247"

The number 4247 has only three distinct digits in base 10. If we repeat those digits nine more times, we'll get a 40-digit number that is a multiple of 4247 and has only three distinct digits: 2, 4, and 7.

1)
2
43
46
Returns: "Ad04400AdAdd4AdA404A0d44d04A40AAdAd4004dAdA"

Here we are looking for a valid 43-digit number in base 46. The character 'A' represents the digit 10, the character 'd' is the digit 39.

2)
46029
47
7
Returns: "62661141446422642461241446421222624162642612416"
3)
45447465934
73
11
Returns: "AAA11000AA010000001110A9AAAA010AA9AAAA0A9AAA9AA0009A000AAA0AA0AA9AA100000"
4)
92704666151
120
62
Returns: "10zz0z10000z0zzzyzz0z0zzyzyyyz0zz00z10yzyzzyzzyyz0yyyyzz0z0010zz10000yzz0zzzzzz10z0zz0yzzyzzyyyzzzzzzzyyzz010yz00yyz1010"

Submissions are judged against all 230 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FourDistinctDigits with a public method string find(long long N, int D, int B) · 230 test cases · 2 s / 256 MB per case

Submitting as anonymous