An Animal Contest 3 P2 - Monkey Potato

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

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 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, 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.


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

1 \le D \le 10

0 \le d_i \le 9

All d_i are distinct.

Subtask 1 [20%]

1 \le d_i \le 9

Subtask 2 [80%]

No additional constraints.

Input Specification

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

The next line will contain 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 using some non-empty combination of the 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 is the smallest valid positive 5-digit integer that can be formed with the digits 3, 1, 2, 5, 4, 9.

Sample Input 2

1 1

Sample Output 2


Sample Input 3

6 1

Sample Output 3



  • 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.


    • 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.