Show all threads Hide all threads Show all messages Hide all messages | Page 1 | I got it by precalc, but wanna know smart solution | Apkawa | 1150. Page Numbers | 10 Oct 2023 12:33 | 2 | 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 | Задача | a2ch | 1150. Page Numbers | 24 Aug 2020 22:12 | 1 | Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую. Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%) Удачи. | shitty problem but i like him | ag2cidk | 1150. Page Numbers | 4 Jul 2018 23:17 | 1 | Edited by author 04.07.2018 23:18 Edited by author 04.07.2018 23:18 | No maths needed | mouse_wireless2 | 1150. Page Numbers | 26 Oct 2020 20:21 | 2 | 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? | what is test#1?? | Xiaohan Yu | 1150. Page Numbers | 10 May 2017 22:47 | 2 | 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 | why, i get compile error | XMAN | 1150. Page Numbers | 30 Jul 2010 04:24 | 2 | #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. | NO.5!! | ☞ⓩⓢⓨⓩ™ⓣⓔⓢⓣ☜ | 1150. Page Numbers | 18 Mar 2009 10:34 | 1 | NO.5!! ☞ⓩⓢⓨⓩ™ⓣⓔⓢⓣ☜ 18 Mar 2009 10:34 | from TC. To admins. | Tchurov_Tim (PomorSU) | 1150. Page Numbers | 3 Mar 2009 11:07 | 2 | 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 | Help me! | Vlad | 1150. Page Numbers | 30 Apr 2010 22:37 | 2 | 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? | Which compiler are using..... | Anand Kumar | 1150. Page Numbers | 5 Jan 2007 15:38 | 2 | 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:) | s.o. to test this ?? | Black^n^White | 1150. Page Numbers | 5 Oct 2006 23:18 | 2 | 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 | The tests have problem. | Gansh Kong | 1150. Page Numbers | 5 Aug 2006 19:15 | 1 | 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 | Some tests which will help during a program debug...(+) | Ivasyuk Roman [KPSU] (onlinehunter@gmail.com) | 1150. Page Numbers | 31 Oct 2019 18:51 | 4 | 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(( | Bad tests! | Vlad Veselov | 1150. Page Numbers | 20 Mar 2015 23:02 | 2 | 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. | How to count zeroes? | Sbreg | 1150. Page Numbers | 16 Aug 2003 22:17 | 2 | 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! | Very Nice Problem | Locomotive | 1150. Page Numbers | 8 Jan 2015 18:34 | 10 | 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 | Help! Why do I get WA? | zhou MX | 1150. Page Numbers | 25 Nov 2018 19:42 | 4 | 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. | Would you like to tell me why I got WA using this source code? | lyj_george | 1150. Page Numbers | 6 Feb 2002 15:17 | 2 | 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. | Some hints about "Digits" problem ;)) | nullman | 1150. Page Numbers | 4 Sep 2009 18:37 | 3 | 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 | Why I get WA? Pelase, help me!!!!!!! Gave me any hints!! | Happy New Year! Russia. | 1150. Page Numbers | 16 Jan 2002 20:47 | 3 | Give any hints about your solution for everybody to help8-) > it's working here but still i'm getting wa. |
Pages: 1 |
|