Editorial for An Animal Contest 3 P2 - Monkey Potato


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sjay05

Denote S = \{a_1, a_2, a_3, \dots, a_D\} to be the set of all valid digits given in input.

Subtask 1

For this subtask, notice that we can take the smallest digit in S and output it K times.

Time Complexity: \mathcal{O}(K)

Subtask 2

Consider 4 cases:

  • S = \{0\}:

    • No valid integer can be formed with the digit 0, so -1 should be outputted.
  • \min S = 0:

    Let the second smallest digit in S be b.

    • K \le 2
      • The smallest palindrome consists of K b's.
    • K > 2
      • A K length palindrome can be constructed with the form: b000 \dots 000b.
  • \min S > 0:

    • Let the smallest digit in S be b. The K length palindrome is: bbb \dots bbb.

Time Complexity: \mathcal{O}(K)


Comments

There are no comments at the moment.