### PROBLEM LINKS

### DIFFICULTY

Easy

### PREREQUISITES

Ad-Hoc

### PROBLEM

Given an integer N, let S_{N} be the string formed by concatenating all the integers between 1 and N, inclusive.

Thus, S_{20} = 1234567891011121314151617181920

Given an integer K, find the number of times K appears as a substring of N.

### EXPLANATION

This problem was intended to be trivial. A lot of doubts were raised about how many test cases were crunched into a file, but all such questions were intentionally left unanswered.

See, the real limit on T was defined in the problem statement, cheekily, as a limit on **sum of N** across all test cases in a file. This limit was 1,000,000. An algorithm of the order of O(N) will not take more than O(sum(N)) for a test file. In fact, solutions with complexity O(N log_{10} K) will pass as well.

The following python-code will solve the problem. (C like code snippets are in the next section)

import re T = int(raw_input()) for _ in xrange(T): N, K = raw_input().split() S = "".join(map(str,range(1,int(N)+1))) R = [m.start() for m in re.finditer('(?='+K+')', S)] print len(R)

If only ICPC rules allowed languages besides C/C++ and JAVA!

### CODE COMMENTARY

The problem can be solved by generating the entire string S_{N} for each test case. To achieve faster times, once can pre-compute the string S_{1000000} and then store the last-indices, up to which the checks should be performed.

The following C-code is enough to solve the problem. It is almost equivalent to the python code above.

char A[10000000]; int main() { char K[10], nk; int T, N, t = 0, result = 0; scanf("%d",&T); while(T--) { scanf("%d %s",&N,K); nk = strlen(K); t = 0; for(int i=1;i<=N;i++) t += sprintf(A+t, "%d", i); result = 0; for(int i=0;i<t;i++) result += !strncmp(K,A+i,nk); printf("%d ",result); } }

Check the tester’s solution for an approach that pre-computes S_{1000000}.

### SETTER’S SOLUTION

Can be here

### TESTER’S SOLUTION

Can be here