Integer concatenation solution codechef

Integer concatenation solution codechef

Concatenation of two integers is obtained as follows: First, convert both integers to strings. Then concatenate both strings into one and convert this concatenated string back to integer.

For example, concatenation of 66 and 77 is CONC(6,7)=67CONC(6,7)=67, concatenation of 123123 and 4545 is CONC(123,45)=12345CONC(123,45)=12345.

Integer concatenation solution codechef

You are given an array AA consisting of NN integers. You are also given two integers LL and RR. Find the number of pairs (iijj) such that 1i,jN1≤i,j≤N and LCONC(Ai,Aj)RL≤CONC(Ai,Aj)≤R

Note: Since the size of the input and output is large, please use fast input-output methods.

Input Format Integer concatenation solution codechef

  • The first line will contain TT, the number of test cases. Then TT test cases follow.
  • The first line of each test case contains three integers N,L,RN,L,R.
  • The second line of each test case line contains NN integers A1,A2,,ANA1,A2,…,AN.

Output Format Integer concatenation solution codechef

For each testcase, output in a single line the number of suitable pairs.

Constraints Integer concatenation solution codechef

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 1LR10151≤L≤R≤1015
  • 1Ai1071≤Ai≤107
  • Sum of NN over all test cases does not exceed 106106.

Sample Input 1 Integer concatenation solution codechef

4
2 10 52
2 5
3 58 100
4 2 3
4 100 1000
1 10 100 1000
5 28 102
3 2 1 9 10

Sample Output 1 Integer concatenation solution codechef

3
0
2
11

Explanation Integer concatenation solution codechef

Test case 1:

  • (i=1,j=1)(i=1,j=1)CONC(A1,A1)=22CONC(A1,A1)=22 and 10225210≤22≤52.

  • (i=1,j=2)(i=1,j=2)CONC(A1,A2)=25CONC(A1,A2)=25 and 10255210≤25≤52.

  • (i=2,j=1)(i=2,j=1)CONC(A2,A1)=52CONC(A2,A1)=52 and 10525210≤52≤52.

  • (i=2,j=2)(i=2,j=2)CONC(A2,A2)=55CONC(A2,A2)=55 and 105510≤55 but 555255≰52.

So there are three suitable pairs.

Test case 2: There is no suitable pair.

Test case 3: The suitable pairs are (2,1)(2,1) and (1,2)(1,2).

Leave a Reply

Your email address will not be published. Required fields are marked *

*