BPC 1 J4 - Assignment of the Year - Olympiads Online Judge

BPC 1 J4 - Assignment of the Year

Points: 10 (partial)

Time limit: 1.5s

Memory limit: 512M

Authors:

Problem type

This year at Spirit of Math Schools, you have been assigned to find the number of unique numbers between $0$ ~0~ and $M$ ~M~ (inclusive) you can create using a list of $N$ ~N~ digits. You may add or concatenate digits. Their order must be maintained, and every digit must be used. Output the number of unique values you can create between $0$ ~0~ and $M$ ~M~.

Constraints

$1 \le N \le M \le 10^4$ ~1 \le N \le M \le 10^4~

Subtask 1 [10%]

All of the digits are the same.

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains two integers, $N$ ~N~ and $M$ ~M~.

The next line contains a string of $N$ ~N~ digits (numbers between $0$ ~0~ and $9$ ~9~).

Output Specification

Output a single line containing an integer, the number of unique values that can be created.

Sample Input

4 100
1996

Sample Output

Explanation for Sample

There are 8 possible combinations of operations:

$\displaystyle \begin{align*}1+9+9+6 &= 25 \\ 1+9+96 &= 106 \\ 1+99+6 &= 106 \\ 1+996 &= 997 \\ 19+9+6 &= 34 \\ 19+96 &= 115 \\ 199+6 &= 205 \\ 1996 &= 1996\end{align*}$

Only two of these are between $0$ ~0~ and $100$ ~100~ ( $25$ ~25~ and $34$ ~34~).

Comments

0

b_nary commented on Nov. 23, 2023, 5:10 a.m.

could anyone help with batch 2 test case #8? I'm really stuck -- https://dmoj.ca/submission/5946631