C - Buy an Integer Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋くんは整数を 1 つ買いに整数屋さんに行きました。

整数屋さんには 1 以上 10^9 以下の整数が売られていて、整数 N を買うためには A \times N + B \times d(N) 円が必要です。ここで、d(N) は N の十進表記での桁数です。

高橋くんの所持金が X 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0 を出力してください。

制約

  • 入力は全て整数である。
  • 1 \leq A \leq 10^9
  • 1 \leq B \leq 10^9
  • 1 \leq X \leq 10^{18}

入力

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

A B X

出力

高橋くんの買うことのできる最も大きい整数を出力せよ。ただし、買うことのできる整数が 1 つもない場合は 0 を出力せよ。

入力例 1

10 7 100

出力例 1

9

9 の値段は 10 \times 9 + 7 \times 1 = 97 円で、これが買うことのできる最大の整数です。 他の整数の値段の例をいくつかあげると

  • 10: 10 \times 10 + 7 \times 2 = 114 円
  • 100: 10 \times 100 + 7 \times 3 = 1021 円
  • 12345: 10 \times 12345 + 7 \times 5 = 123485 円

です。

入力例 2

2 1 100000000000

出力例 2

1000000000

お店に売られている最大の整数を買うことができます。入力が 32 bit整数型に収まらないことがあることに注意してください。

入力例 3

1000000000 1000000000 100

出力例 3

0

入力例 4

1234 56789 314159265

出力例 4

254309

Score : 300 points

Problem Statement

Takahashi has come to an integer shop to buy an integer.

The shop sells the integers from 1 through 10^9. The integer N is sold for A \times N + B \times d(N) yen (the currency of Japan), where d(N) is the number of digits in the decimal notation of N.

Find the largest integer that Takahashi can buy when he has X yen. If no integer can be bought, print 0.

Constraints

  • All values in input are integers.
  • 1 \leq A \leq 10^9
  • 1 \leq B \leq 10^9
  • 1 \leq X \leq 10^{18}

Input

Input is given from Standard Input in the following format:

A B X

Output

Print the greatest integer that Takahashi can buy. If no integer can be bought, print 0.

Sample Input 1

10 7 100

Sample Output 1

9

The integer 9 is sold for 10 \times 9 + 7 \times 1 = 97 yen, and this is the greatest integer that can be bought. Some of the other integers are sold for the following prices:

  • 10: 10 \times 10 + 7 \times 2 = 114 yen
  • 100: 10 \times 100 + 7 \times 3 = 1021 yen
  • 12345: 10 \times 12345 + 7 \times 5 = 123485 yen

Sample Input 2

2 1 100000000000

Sample Output 2

1000000000

He can buy the largest integer that is sold. Note that input may not fit into a 32-bit integer type.

Sample Input 3

1000000000 1000000000 100

Sample Output 3

0

Sample Input 4

1234 56789 314159265

Sample Output 4

254309