Editorial for An Animal Contest 3 P2 - Monkey Potato - Olympiads Online Judge

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)$ $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 \leq 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$ $b 00 \dots 00 b$ .
$\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$ $b b \dots b b$ .

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

Comments

There are no comments at the moment.