BPC 1 J4 - Assignment of the Year - DMOJ: Modern 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 \leq N \leq M \leq 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

Copy

4 100
1996

Sample Output

Copy

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*}$ $\begin{aligned} 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{aligned}$

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