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. Two ways I know - 1) Solve for each number of digits 2) Better way (hint): 1 to 10, 11 to 20, etc. each digit is counted once in the ones place Edited by author 10.10.2023 12:37 Edited by author 10.10.2023 12:37 Precompute the results for ~200 numbers (at regular intervals) and hardcode them. Then you can just bruteforces starting from the closest precomputed number. Yea, this works fine, but how to solve it fairly? Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую. Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%) Удачи. 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 Thanks for the tests! I got AC :) But... I have some small correntions: 1) N <= 1 000 000 000, so N = 2 984 210 864 is an impossible test 2) for N = 9999 the right output is: 2889 4000 4000 4000 4000 4000 4000 4000 4000 4000 Also this one is a good test: 11 1 4 1 1 1 1 1 1 1 1 correct first test is n = 29842 ans 10864 21975 21818 11974 11967 11964 11964 11964 11907 11707 and n = 9999 0 2889 1 4000 2 4000 3 4000 4 4000 5 4000 6 4000 7 4000 8 4000 9 4000 I deduced the formula, but in numbers with zeros it does not work(( 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. Edited by author 04.07.2018 23:18 Edited by author 04.07.2018 23:18 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 Test #1 answer is 1 5 2 (7)1 My program works wrong when N = 10^K, but gets AC! Please add test with such N. To Admins: my AC program gives wrong answers for 105, 20087. Please add these numbers to tests. 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 Change Var n,k :longint; >> i,j,s :longint; m :array[0..9] of longint; And all will be correct! > Change > > Var > n,k :longint; > >> i,j,s :longint; > m :array[0..9] of longint; > > > And all will be correct! When N>100,his answer isn't right,either. DON`T POST YOUR CODE!!! >>Messages should NOT contain source code (especially correct solutions) Edited by author 08.01.2008 14:01 50% have in it forums solutions with AC :) I hate this problem!!! I've been solving it 2 days. And now I'm very tired. :( I do very easy, but have Time Limit excepted :( Aaaa, too much code ) Want a shorter solution, email me ) cebotari.vladislav@gmail.com #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; } It's not allowed to use <conio.h> and getch(). Read FAQ. 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 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 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 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'm using dev-cpp ide with gcc 3.4.2 compiler, works fine:) 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 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 I can count digits 1-9, but can't do it with zeroes. Help me! Do it as other digits.and the result of digit 0 must dec power(10,n)+power(10,n-1)+...+power(10,0) (n is the length of the page) Good luck! 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. Give any hints about your solution for everybody to help8-) > it's working here but still i'm getting wa. |
|