/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 枚のカードがあり、1 から N までの番号が付けられています。はじめはどのカードも何も書かれていません。
あなたはそれぞれのカードに 0 個以上の正整数を書き込むことができます。
正整数 k を 1 回書き込むときにかかるコストは、k の十進表記での桁数に等しいです。
以下の条件を満たすことが可能か判定し、可能であれば必要な総コストの最小値を、不可能であれば -1 を出力してください。
- 1 \leq x < y \leq K を満たすどの正整数組 (x,y) についても、そのうち片方だけを含むカードが存在する。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^6
- 2 \leq K \leq 10^6
- ひとつの入力における N の総和は 10^6 以下
- ひとつの入力における K の総和は 10^6 以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N K
出力
T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。
入力例 1
4 3 5 100 25 5 1225 180 998244
出力例 1
5 39 -1 17655598
この入力には 4 個のテストケースが含まれています。
1 個目のテストケースにおいて、以下のように書き込めば総コスト 5 で条件を満たします。
- カード 1 には 1, 5 を書き込む。
- カード 2 には 2, 5 を書き込む。
- カード 3 には 3 を書き込む。
2 個目のテストケースにおいて、条件を満たすのに必要な総コストの最小値は 39 です。
3 個目のテストケースにおいて、条件を満たすことは不可能なので -1 を出力します。
4 個目のテストケースにおいて、条件を満たすのに必要な総コストの最小値は 17655598 です。
Score : 500 points
Problem Statement
There are N cards, numbered 1 through N. Initially, nothing is written on any of the cards.
You can write zero or more positive integers on each card.
The cost of writing a positive integer k once is equal to the number of digits in the decimal representation of k.
Determine whether it is possible to satisfy the following condition. If it is possible, output the minimum total cost required; if it is not possible, output -1.
- For every pair of positive integers (x,y) satisfying 1 \leq x < y \leq K, there exists a card containing exactly one of x and y.
T test cases are given; solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^6
- 2 \leq K \leq 10^6
- The sum of N in each input is at most 10^6.
- The sum of K in each input is at most 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N K
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
4 3 5 100 25 5 1225 180 998244
Sample Output 1
5 39 -1 17655598
This input contains four test cases.
For the first test case, writing as follows satisfies the condition with a total cost of 5.
- Write 1, 5 on card 1.
- Write 2, 5 on card 2.
- Write 3 on card 3.
For the second test case, the minimum total cost required to satisfy the condition is 39.
For the third test case, it is impossible to satisfy the condition, so output -1.
For the fourth test case, the minimum total cost required to satisfy the condition is 17655598.