A - Antichain of Integer Strings

Contest Duration: 2022-05-07(Sat) 12:00 - 2022-05-07(Sat) 15:00 (local time) (180 minutes) Back to Home

A - Antichain of Integer Strings Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

正整数からなる集合 $A$ は次の条件を満たすとき、良い集合であるといいます。

任意の相異なる $2$ 要素 $a, b \in A$ に対して、 $a$ を $10$ 進法表記した文字列は、 $b$ を $10$ 進法表記した文字列の部分文字列ではない。

部分文字列とは？

部分文字列とは連続する部分列のことを指します。例えば 1, 12, 23 は 123 の部分文字列ですが、21 や 13 は 123 の部分文字列ではありません。

正整数 $L, R$ が与えられます。 $L$ 以上 $R$ 以下の整数からなる良い集合 $A$ の要素数の最大値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\leq T\leq 10^4$
$1\leq L\leq R\leq 10^{9}$

入力

入力は以下の形式で標準入力から与えられます。

 $T$ 
 $\text{case}_1$ 
 $\vdots$ 
 $\text{case}_T$

各テストケースは以下の形式で与えられます。

 $L$   $R$

出力

$T$ 行出力してください。 $i$ 行目には、 $\text{case}_i$ に対する答えを出力してください。

入力例 1Copy

Copy

出力例 1Copy

Copy

6
10
900

はじめの $2$ つのテストケースについて、例えば次の $A$ が要素数が最大であるような良い集合となります。

$1$ つめのテストケース： $A=\{3,4,5,6,7,8\}$ .
$2$ つめのテストケース： $A=\{3,4,6,8,9,10,11,12,15,17\}$ .

Score : $400$ points

Problem Statement

A set $A$ of positive integers is said to be good when it satisfies the following condition.

For any two distinct elements $a, b \in A$ , the string representing $a$ in base ten is not a substring of the string representing $b$ in base ten.

What is a substring?

A substring of a string is its contiguous subsequence. For example, 1, 12, and 23 are substrings of 123, while 21 and 13 are not.

You are given positive integers $L$ and $R$ . Find the maximum possible number of elements in a good set $A$ consisting of integers between $L$ and $R$ (inclusive).

We will give you $T$ test cases; solve each of them.

Constraints

$1\leq T\leq 10^4$
$1\leq L\leq R\leq 10^{9}$

Input

Input is given from Standard Input in the following format:

 $T$ 
 $\text{case}_1$ 
 $\vdots$ 
 $\text{case}_T$

Each case is in the following format:

 $L$   $R$

Output

Print $T$ lines. The $i$ -th line should contain the answer for $\text{case}_i$ .

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

6
10
900

For the first two cases, the following are good sets $A$ with the maximum number of elements.

Case $1$ : $A=\{3,4,5,6,7,8\}$ .
Case $2$ : $A=\{3,4,6,8,9,10,11,12,15,17\}$ .