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

An Animal Contest 3 P2 - Monkey Potato

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

George the monkey was hanging off his favourite branch while watching his favourite anime, when all of a sudden, a potato fell from the sky! Upon examining the potato, he notices $D$ ~D~ distinct digits carved on it.

George wants you to use some non-empty combination of digits from the potato to form a positive integer of length $K$ ~K~, with no leading zeros. He also tells you that you can use the same digit more than once. Additionally, George doesn't remember if he should read numbers from left to right or right to left, so he tells you to make him an integer that reads the same either way!

In addition, George doesn't like processing large integers, so he'll only accept the smallest possible answer. If it is impossible to satisfy this task, you'll have to tell him, and he will become a very sad monkey.

Constraints

$1 \le K \le 2 \times 10^3$ ~1 \le K \le 2 \times 10^3~

$1 \le D \le 10$ ~1 \le D \le 10~

$0 \le d_i \le 9$ ~0 \le d_i \le 9~

All $d_i$ ~d_i~ are distinct.

Subtask 1 [20%]

$1 \le d_i \le 9$ ~1 \le d_i \le 9~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input will contain $K$ ~K~ and $D$ ~D~ separated by a single space.

The next line will contain $D$ ~D~ space-separated integers, denoting the digits that you can use to construct the integer.

Output Specification

Output the minimum positive integer of length $K$ ~K~ using some non-empty combination of the $D$ ~D~ digits, or -1 if there is no valid answer.

Sample Input 1

5 6
3 1 2 5 4 9

Sample Output 1

Explanation for Sample 1

It can be proven that $11111$ ~11111~ is the smallest valid positive $5$ ~5~-digit integer that can be formed with the digits $3, 1, 2, 5, 4, 9$ ~3, 1, 2, 5, 4, 9~.

Sample Input 2

1 1
1

Sample Output 2

Sample Input 3

6 1
0

Sample Output 3

-1

Comments

17

Jinx commented on Jan. 8, 2022, 7:20 p.m.

Don't you just hate it when you're watching anime and a potato falls on your head

11

22yeetz22 commented on Sept. 18, 2022, 12:09 a.m.

Yes, it is very annoying

1

dchoo333 commented on Aug. 4, 2021, 12:29 p.m.

Could anyone advise me on why my output stops getting AC after Test Case #4 in Batch #2?

3

Riolku commented on Aug. 5, 2021, 6:20 p.m. ← edit 2 →

A reminder that sharing solutions in the comments is strongly discouraged. Asking for help in DMOJ Discord is preferable.

Also, editorials exist for the purposes of discussing solutions...

9
ryanguorocket commented on Aug. 4, 2021, 4:05 p.m.
Try the case

1 2 0 1

1

dchoo333 commented on Aug. 5, 2021, 12:18 p.m.

Thanks.

1

dxke02 commented on Aug. 4, 2021, 12:34 p.m. ← edit 2 →

Please ask for help in the Discord server.

1

dchoo333 commented on Aug. 5, 2021, 12:19 p.m.

Sorry, I will do that next time.