Задача заставила подумать.
Как уже описано на форуме,  нужно научиться считать количество единиц, которые встречаются в числах от 1 до X и подбирать X бинарным поиском.

И вот мне этот подсчет долго не давался.

Итог такой.

Считать можно рекурсивно.
Для этого нужно воспользоваться тем,  что для чисел вида X=999...999 искомое количество единиц равно (log10(X)+1) *10^log10(X).
Этот факт я заметил эксперимнтально.

То есть я имею в виду
count_ones (99)=20
count_ones (999)=300
count_ones (9999)=4000
и так далее.

Отсюда и вытекает способ .

Вычисляем сначала для X с зануленными разрядами кроме самого главного,  затем прибавляем значение функции от X с зануленным главным разрядом .

Я приведу пример для небольшого числа.

Пусть X=666.

Тогда посчитаем отдельно для 0-99, умножим на 6,  прибавим к ответу; затем отдельно для 100-200, прибавим это к ответу , затем рекурсивно для 600-666 то есть просто для 0-66.

What's wrong, if the second test is 10^18?

Obvious solution looks as:
1) Suggest f(n) = amount of ones in numbers from 1 to n
2) Make binary search for f(i)
It is obvious right, but constraint for input number don't allow to fast writing this solution in cpp (because we need in BigInteger). So, in my opinion, constraint are bad.
If we want to make hardships with standart types in cpp and pascal, should take 1 <= n <= 10^100. In other hand, if we don't want to make it, should take 1 <= n <= 10^15.

Am I wrong?

subj

What's the test?
I use unsigned __int64, in debugger even the input of 10^18 is processed correctly, though...

20 -> 91
21 -> 100
31 -> 109
32 -> Petr lies
33 -> 110
35 -> Petr lies
36 -> 111

NEXT CODE IS NOT AC SOLUTION
but it a way to test your Solution


next class run with command: "java tester >test.txt"
then you can run your solution and compare your answers with this tester's
But you cant test some tests where n>30000, therefore
try to think and about it.
Good luck to TEST, I AC))
////////////////////////tester.java///////////////////////////
import java.io.*;
import java.util.*;

public class tester{
 public static void main(String[] args){
  int s=0,ts=0;
  int t;
  int a[]=new int[30000];
  for(int i=0;i<30000;i++){
   a[i]=0;
  }
  for(int i=1;i<=50000;i++){
   ts=s;
   t=i;
   while(t>=10){
    if(t%10==1){
     s++;
    }
    t/=10;
   }
   if(t==1){
    s++;

   }
   if(ts!=s)
    a[s-1]=i;
  }

  for(int i=0;i<30000;i++){
   if(a[i]!=0)
    System.out.println((i+1) + " "+ a[i]);
   else
    System.out.println((i+1)+ " " +"Petr lies");
  }
 }
}

////////////////////////end///////////////////////////

What is the first test and it's correct answer?

I have TL#8, but i didn't use any special algo only calculation. can anybody say me the way and algo of this problem? my e-mail yashar25.92@mail.ru

give me smb tests, pleaze