I precalculated digits for segment from 1e5 to 2e5, then i computed all digits from 1 to 1e5(if n >= 1e5), then i stepped from 1e5 to n with step size = 1e5. And after all this I computed digits from last step to n. It does about 1e9/1e5 steps and works 0.015 sec.

I think that it's dumb solution, so I want to know, how to solve this task in O(log10(n)) or smth similar.

Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую.
Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%)
Удачи.

Edited by author 04.07.2018 23:18

Edited by author 04.07.2018 23:18

Precompute the results for ~200 numbers (at regular intervals) and hardcode them.
Then you can just bruteforces starting from the closest precomputed number.

here is my code im getting test# 1 WA
btw im using python 2.7


import sys
print sys.argv
pages = raw_input()
pages = int(pages)

nums = [0]*10

def countingNums(pages):
    global nums
    if pages == 0:
        return ""
    else:
        sPages = str(pages)
        for i in range(len(sPages)):
            nums[int(sPages[i])] += 1
        return countingNums(pages-1)

countingNums(pages)
for i in range(len(nums)):
    print nums[i]

Edited by author 10.05.2017 17:30

#include<conio.h>
#include<math.h>
#include<stdio.h>
int k,t[10];
double fonction (int n, int i)
{
       int h;
    if(n==1)
    {
            if(t[n]>=i)
            {
                       return 1;
            }
            else
            {
                return 0;
            }
    }
    else
    {
        if(t[n]>i)
            {
                       return ((pow(10,n-1))+(t[n]*pow(10,n-2))+(fonction(n-1,i)));
            }
        if(t[n]==i)
            {
                       h=int(k/pow(10,n-1));
                       return (((k-(h*pow(10,n-1)))+1)+(t[n]*pow(10,n-2))+(fonction(n-1,i)));
            }
        if(t[n]<i)
            {
                       return ((t[n]*pow(10,n-2))+(fonction(n-1,i)));
            }
    }
}

int main()
{
    int n=0,i=1,j,m,r=1,w=0;
    scanf("%d",&k);
    m=k;
   // double q=1.56;
    while(m!=0)
    {
               n++;
               t[n]=m%10;
               m=m/10;
               //printf("%d",t[n]);


    }
    for(i=0;i<n;i++)
    {
                    w+=pow(10,i);
    }
    r=int(fonction(n,0));
    printf("%d\n",r-w);
    for(i=1;i<10;i++)
    {
    r=int(fonction(n,i));
    printf("%d\n",r);
}
    getch();

return 0;
}

Today in TC was similar problem and my solution was failed. I submit my code here and get AC. I think tests is weak.

My program fail on: 900 000 000
My answer:
710123457
808888890
718888890
709888890
708988890
708898890
708889890
708888990
708888900
708888891

Edited by author 01.03.2009 16:27

I tried to solve it with a stupid exhaustive search, but for 99999999 it will be very much!!! Is there the formul with which I can solve this problem?

I have tried the Digitis problem by using TURBO C/C++ compiler and its working fine for me. But the judges said as it has compilation problem. I want to know the compile which they are using for testing......

I can't see a problem in this soluton, but I get WA on test#3
I compared it with a lot of tests to a solution, that is surely correct - the results were always equal.

#include <cstdlib>
#include <cstdio>
#include <cctype>

int func(long pages,int dgts);
char temp[10];

int main()
{
    long pages;
    long dgts = 0;
    scanf("%i",&pages);
    char strpages[10];
    sprintf(strpages,"%i",pages);

    long j = 0;

    while(isdigit(strpages[j]))
    {
              dgts++;
              ++j;
    }

    if(pages > 100)
    {
             func(pages,dgts-1);
             system("pause");
             return 0;
    }

    int digits[] = {0,0,0,0,0,0,0,0,0,0};
    for(long i = 1; i <= pages; ++i)
    {
            j = 0;
            sprintf(temp,"%i",i);
            while(isdigit(temp[j]))
                      digits[temp[j++]-48]++;
    }
    for(long i = 0; i < 10; ++i)
            printf("%i\n",digits[i]);

    system("pause");
    return 0;
}

int func(long pages,int dgts)
{
    long j = 0;
    long long_o, long_t;
    char* one = new char[dgts];
    char* two = new char[dgts+1];

    one[0] =  dgts + 46;
    for(long k = 1; k < dgts-1; ++k)
            one[k] = '8';

    one[dgts - 1] = '9';
    long_o = atoi(one);

    two[0] =  dgts + 48;
    for(long k = 1; k < dgts; ++k)
            two[k] = '0';

    long_t = atoi(two);

    long digits[10];
    digits[0] = long_o;
    for(long i = 1; i < 10; ++i)
            digits[i] = long_t;

    long start = 100;
    for(long i = 0; i < dgts - 2; ++i)
            start *= 10;

    for(long i = start; i <= pages; ++i)
    {
            j = 0;
            sprintf(temp,"%i",i);
            while(isdigit(temp[j]))
                      digits[temp[j++]-48]++;
    }
    for(long i = 0; i < 10; ++i)
            printf("%i\n",digits[i]);

    return 0;
}

Edited by author 05.10.2006 23:19

My program works wrong when N has consecutive 0.But I got AC!Here's my program.It works wrong when N=300.

[code deleted]

Here's the correct program.

[code deleted]

Edited by moderator 20.11.2019 23:32

n=2984210864
21975
21818
11974
11967
11964
11964
11964
11907
11707

n=120
22
53
23
22
22
22
22
22
22
22

n=1000000000
788888898
900000001
900000000
900000000
900000000
900000000
900000000
900000000
900000000
900000000

n=1595999
887689
1594800
998800
998800
998800
994800
897800
897800
897800
893800

n=2009999
1112889
2204000
1214000
1204000
1204000
1204000
1204000
1204000
1204000
1204000

n=123456789
96021948
130589849
100589849
96589849
96089849
96029849
96022849
96022049
96021959
96021949

n=10000
2893
4001
4000
4000
4000
4000
4000
4000
4000
4000

n=20000
6893
18000
8001
8000
8000
8000
8000
8000
8000
8000

n=30000
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

n=9999
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

My program works wrong when N = 10^K, but gets AC! Please add test with such N.

I can count digits 1-9, but can't do it with zeroes. Help me!

Hi
I think this Problem is very very Nice
Easy to understand Hard 2 solve!
i got AC with all theoric methods:

[code deleted]

Sincrely
Aidin_n7

Edited by moderator 20.11.2019 23:24

I think my program is right , but I get WA .

program Ural_1150;
        // Digits
const
  bit:array[1..10] of longint=
(1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000);
var
  num:array[0..9] of longint;
  n,i,j,x:longint;

begin
  readln(n);
  for i:=1 to 9 do
  begin
    x:=n mod bit[i+1] div bit[i];
    for j:=1 to 9 do
    begin
      num[j]:=num[j]+n div bit[i+1]*bit[i];
      if x>j then
        num[j]:=num[j]+bit[i]
      else
      if x=j then
        num[j]:=num[j]+n mod bit[i]+1;
    end;
    if n>=bit[i+1] then
    begin
      num[0]:=num[0]+n div bit[i+1]*bit[i]-bit[i];
      if x>0 then
        num[0]:=num[0]+bit[i]
      else
        num[0]:=num[0]+n mod bit[i]+1;
    end;
  end;
  for i:=0 to 9 do
    writeln(num[i]);
end.

var
  tot : array [0..9] of longint;
  i : byte;
  zg : longint;
  n : string;
  r : longint;
  error : integer;
function cf(ll:byte) : longint;
var
  tt,ti : longint;
begin
  tt := 1;
  for ti := 1 to ll do
    tt := tt * 10;
  cf := tt;
end;
function change(aa,bb:byte) : longint;
var
  tstr : string;
  o : longint;
begin
  tstr := copy(n,aa,bb-aa+1);
  val(tstr,o,error);
  change := o;
end;

procedure solve(now:byte);
var
  k : byte;
  ttt : string;
begin
  str(now,ttt);
  for k := 1 to length(n) do begin
    if k = 1 then begin
          if ttt[1] < n[1] then tot[now] := tot[now] + cf(length(n)-
k);
          if ttt[1] = n[1] then tot[now] := tot[now] + change(2,length
(n)) + 1;
        end;
    if k = length(n) then begin
                  tot[now] := tot[now] + change(1,k-1);
                  if ttt[1] <= n[k] then inc(tot[now]);
                end;
    if (k>1) and (k<length(n)) then begin
      tot[now] := tot[now] + change(1,k-1) * cf(length(n) - k);
      if ttt[1] < n[k] then tot[now] := tot[now] + cf(length(n) - k);
      if ttt[1] = n[k] then tot[now] := tot[now] + change(k+1,length
(n))+1;
    end;
end;
end;
procedure out;
begin
  tot[0] := zg - tot[1] - tot[2] - tot[3] - tot[4] - tot[5]
            - tot[6] - tot[7] - tot[8] - tot[9];
  for i := 0 to 9 do
    writeln(tot[i]);
end;
begin
  readln(n);
  val(n,r,error);
  zg := 0;
  for i := 1 to length(n)-1 do
    zg := zg + 9 * cf(i-1) * i;
  zg := zg + length(n) * (r mod cf(length(n))+1-cf(i));
  for i := 1 to 9 do
    solve(i);
  out;
end.

I have been accepted with time result 0.13 sec. so I do not show off
but this is good result. I have written it in C++, but my idea is to
jump with 9999 pages with these functions:
void calc9999(void)
{ pArr[0]+=1104+2889+3;// ???
  pArr[1]+=4000;pArr[2]+=4000;pArr[3]+=4000;
  pArr[4]+=4000;pArr[5]+=4000;pArr[6]+=4000;
  pArr[7]+=4000;pArr[8]+=4000;pArr[9]+=4000;
}
// the second is only at start!!!
void calc1to9999(void)
{ pArr[0]+=2889;
  pArr[1]+=4000;pArr[2]+=4000;pArr[3]+=4000;
  pArr[4]+=4000;pArr[5]+=4000;pArr[6]+=4000;
  pArr[7]+=4000;pArr[8]+=4000;pArr[9]+=4000;
}
:))
I jump up to all pages if possible otherwise i use one by one page
calculation. If pages are less than 10000 I use the same method.

If some one got it type some thanks!!!

Zahari