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, \dots, a_D\}$ ~S = \{a_1, a_2, \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$ ~S~ and output it $K$ ~K~ times.

Time Complexity: $\mathcal{O}(K)$ ~\mathcal{O}(K)~

Subtask 2

Consider $4$ ~4~ cases:

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

Let the second smallest digit in $S$ ~S~ be $b$ ~b~.
- $K \le 2$ ~K \le 2~
  - The smallest palindrome consists of $K$ ~K~ $b$ ~b~'s.
- $K > 2$ ~K > 2~
  - A $K$ ~K~ length palindrome can be constructed with the form: $b00 \dots 00b$ ~b00 \dots 00b~.
$\min S > 0$ ~\min S > 0~:
- Let the smallest digit in $S$ ~S~ be $b$ ~b~. The $K$ ~K~ length palindrome is: $bb \dots bb$ ~bb \dots bb~.

Time Complexity: $\mathcal{O}(K)$ ~\mathcal{O}(K)~

Comments

There are no comments at the moment.