C++

Forum

 
Arithmetic progression

samarth123 (53)
If a sequence of numbers A1, A2, ... , AN form an arithmetic progression A, calculate sum of
F(Ai), for L ≤ i ≤ R.
F(X) is defined as:
If X < 10 then F(X) = X.
Else F(X) = F(sum_of_digits(X)).
Example:
F(1378) =
F(1+3+7+8) =
F(19) =
F(1 + 9) =
F(10) =
F(1+0) =
F(1) = 1
Input
The first line of the input contains an integer T denoting the number of test cases.
Each test case is described in one line containing four integers: A1 denoting the first element of the
arithmetic progression A, D denoting the common difference between successive members of A, and L
and R as described in the problem statement.
Output
For each test case, output a single line containing one integer denoting sum of F(Ai).
Constraints
1 ≤ T ≤ 10^5
1 ≤ A1 ≤ 10^9
0 ≤ D ≤ 10^9
1 ≤ R ≤ 10^18
1 ≤ L ≤ R
Subtasks
Subtask 1: 0 ≤ D ≤ 100, 1 ≤ A1 ≤ 10^9, 1 ≤ R ≤ 100
Subtask 2: 0 ≤ D ≤ 109, 1 ≤ A1 ≤ 109, 1 ≤ R ≤ 10^6
Subtask 3: Original constraints

Example
Input:
2
1 1 1 3
14 7 2 4
Output:
6
12

Example case 2.
A = {14, 21, 28, 35, 42, 49, 56, 63, 70, 77, ...}
A2 = 21
A3 = 28
A4 = 35
F(A2) = 3
F(A3) = 1
F(A4) = 8
3+1+8=12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
#include<iostream> 
#include<math.h>
using namespace std;

int main()
{
	unsigned long long t,a,d,l,r;
	unsigned long long q[9]={0,0,0,0,0,0,0,0,0};
	unsigned long long sum[9]={0,0,0,0,0,0,0,0,0};
	unsigned long long y,total;
	
	cin>>t;
	while(t--)
	{
		cin>>a>>d>>l>>r;
			
		if(d%3!=0 && d%9!=0)
	    {
	    
			for(int i=0;i<9;i++)
			{
			
				if(a<10)
		        {   
			     q[i]=a;
		        }
		        
		        else
		     {
			     while(a>=10)
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[i]=a;
						break;  
					}
					else continue;
                }
                a=a+d;
		     }
			}
			sum[0]=q[0];
			sum[1]=sum[0]+q[1];
			sum[2]=sum[1]+q[2];
			sum[3]=sum[2]+q[3];
			sum[4]=sum[3]+q[4];
			sum[5]=sum[4]+q[5];
			sum[6]=sum[5]+q[6];
			sum[7]=sum[6]+q[7];
			sum[8]=sum[7]+q[8];
			
			total=((r/9)*sum[8] + sum[r%9-1])-(((l-1)/9)*sum[8] + sum[(l-1)%9-1]);
			cout<<total<<"\n";
		}
		if(d%3==0 && d%9!=0)
		{
			for(int i=0;i<3;i++)
			{
			
				if(a<10)
		        {   
			     q[i]=a;
		        }
		        
		        else
		     {
			     while(a>=10)
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[i]=a;
						break;  
					}
					else continue;
                }
                a=a+d;
		     }
			}
			sum[0]=q[0];
			sum[1]=q[0]+q[1];
			sum[2]=q[0]+q[1]+q[2];
			total=((r/3)*sum[2] + sum[r%3-1])-(((l-1)/3)*sum[2] + sum[(l-1)%3-1]);
			cout<<total<<"\n";
		}
         if(d%9==0)
		{
				if(a<10)
		        {   
			     q[0]=a;
		        }
		        
		        else
		     {
			     while(a>=10)
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[0]=a;
						break;  
					}
					else continue;
                }
		     }
			total=q[0]*(r-l+1);
			cout<<total<<"\n";
	    }
	}
	return 0;
}



In this code i have used the idea that the numbers in the A.P. are following a certain pattern because the result F(X) lies between 1 to 9.
in case the common differnce is a mutiple of 3 but not a mutliple of 3 then the numbers repeat after 3 numbers.If the common diff. is a multiple of 9 then the numbers show the same result every time.
else the numbers repeat themselves after every 9 numbers.
cire (8284)
Was there a question you wanted to ask?
samarth123 (53)
My code is showing wrong answer.I wanted to know what is wrong in ths code.
cire (8284)
The algorithm.
samarth123 (53)
What do you mean to say.Can you please point out my mistake
cire (8284)
What do you mean to say.

I mean to say that the algorithm is wrong.

Trace the logic for any small input (such as the two examples you give here that your code gives the wrong answer for).

Write it out on paper if you have to.


samarth123 (53)
@cire

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
#include<iostream> 
#include<math.h>
using namespace std;

int main()
{
	unsigned long long t,a,d,l,r;
    unsigned long long y,total;
	
	cin>>t;
	while(t--)
	{
		cin>>a>>d>>l>>r;
			
		if(d%3!=0 && d%9!=0) 
	    {
	    unsigned long long q[9]={0,0,0,0,0,0,0,0,0};
	unsigned long long sum[9]={0,0,0,0,0,0,0,0,0};
			for(int i=0;i<9;i++)
			{
			
				if(a<10)
		        {    
			     q[i]=a;
		        }
		        
		        else
		     {
			     while(a>=10)       
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[i]=a;
						break;  
					}
					else continue; 
                }
             }
             a=a+d;
			}
			sum[0]=q[0];
			sum[1]=sum[0]+q[1];
			sum[2]=sum[1]+q[2];
			sum[3]=sum[2]+q[3];
			sum[4]=sum[3]+q[4];
			sum[5]=sum[4]+q[5];
			sum[6]=sum[5]+q[6];
			sum[7]=sum[6]+q[7];
			sum[8]=sum[7]+q[8];
			
			if(r%9!=0 && (l-1)%9!=0)
			{
			total=((floor)(r/9)*sum[8] + sum[(r%9)-1])-((floor)((l-1)/9)*sum[8] + sum[((l-1)%9)-1]);
			cout<<total<<"\n";
		    }
		    if(r%9==0 && (l-1)%9!=0)
		    {
		    total=((floor)(r/9)*sum[8] + sum[(r%9)])-((floor)((l-1)/9)*sum[8] + sum[((l-1)%9)-1]);
			cout<<total<<"\n";
			}
		    if(r%9!=0 && (l-1)%9==0 && l!=1)
		    {
		    total=((floor)(r/9)*sum[8] + sum[(r%9)-1])-((floor)((l-1)/9)*sum[8] + sum[((l-1)%9)]);
			cout<<total<<"\n";
			}
			if(r%9==0 && (l-1)%9==0)
		    {
		    total=((floor)(r/9)*sum[8] + sum[(r%9)])-((floor)((l-1)/9)*sum[8] + sum[((l-1)%9)]);
			cout<<total<<"\n";
			}
			if(r%9!=0 && (l-1)%9==0 && l==1)
		    {
		    total=((floor)(r/9)*sum[8] + sum[(r%9)-1]);
			cout<<total<<"\n";
	    	}
	    }
		if(d%3==0 && d%9!=0)
		{
			unsigned long long q[3]={0,0,0};
	unsigned long long sum[3]={0,0,0};
			for(int i=0;i<3;i++)
			{
			
				if(a<10)
		        {   
			     q[i]=a;
		        }
		        
		        else
		     {
			     while(a>=10)
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[i]=a;
						break;  
					}
					else continue;
                }
		     }
		     a=a+d;
			}
			sum[0]=q[0];
			sum[1]=sum[0]+q[1];
			sum[2]=sum[1]+q[2];
			
			if(r%3!=0 && (l-1)%3!=0)
			{
			total=((floor)(r/3)*sum[2] + sum[(r%3)-1])-((floor)((l-1)/3)*sum[2] + sum[((l-1)%3)-1]);
			cout<<total<<"\n";
		    }
		    if(r%3==0 && (l-1)%3!=0)
		    {
		    total=((floor)(r/3)*sum[2] + sum[(r%3)])-((floor)((l-1)/3)*sum[2] + sum[((l-1)%3)-1]);
			cout<<total<<"\n";
			}
		    if(r%3!=0 && (l-1)%3==0 && l!=1)
		    {
		    total=((floor)(r/3)*sum[2] + sum[(r%3)-1])-((floor)((l-1)/3)*sum[2] + sum[((l-1)%3)]);
			cout<<total<<"\n";
			}
			if(r%3==0 && (l-1)%3==0)
		    {
		    total=((floor)(r/3)*sum[2] + sum[(r%3)])-((floor)((l-1)/3)*sum[2] + sum[((l-1)%3)]);
			cout<<total<<"\n";
			}
			if(r%3!=0 && (l-1)%3==0 && l==1)
		    {
		    total=((floor)(r/3)*sum[2] + sum[(r%3)-1]);
			cout<<total<<"\n";
			}
		}
         if(d%9==0)
		{
		 unsigned long long q[1]={0};
	    unsigned long long sum[1]={0};
				if(a<10)
		        {   
			     q[0]=a;
		        }
		        
		        else
		     {
			     while(a>=10)
				{
					unsigned long long sum1=0;
					while(a!=0)
					{
						y=a%10;
						sum1=sum1+y;
						a=a/10;
					}
					a=sum1;
						if(a<10)
					{
						q[0]=a;
						break;  
					}
					else continue;
                }
		     }
			total=q[0]*(r-l+1);
			cout<<total<<"\n";
	    }
	}
	return 0;
}



I have re writeen my code..MAde changes in it.Please have a look at it.Now also it is showing wrong answer..what can be the reason
cire (8284)
Rewriting code while using the same algorithm that doesn't work.. not so good. Trace through the logic of your code and make changes according to what you find isn't working. Do not guess what is wrong and make random arbitrary changes to your code. That is no way to make progress.
samarth123 (53)
I have tried every possible step still i cant find my mistake in the problem.can you please help me out
samarth123 (53)
Say, a=14, d=7, l=2, r=50.


Let Our repetition array is q (say). Then, 1st term of q is 5 (since 14 = 5).
Now, next term is 21 (= 3). Since 3 is not equal to 5, we continue.
We find all terms till we get 5 again. So, q will be like this in this example:

q[] = {5,3,1,8,6,4,2,9,7} ... and then we have 5 again, so stop.
So, our repetitive pattern has 9 members. Now, find a cumulative sum array with this, which will be like:

sum[] = {5,8,9,17,23,27,29,38,45}
Now, since r=50, find sum of r terms, which will be:

(floor)(50/9) * 45 + sum[50%9]
= 5 * 45 + 23
= 248
Now, similarly, find sum of l-1 terms, (since you have to find sum in range l..r inclusive.

Sum of 1st (2-1) = 1 terms will be:

(floor)(1/9) * 45 + sum[1 % 9]
= 0 + 5
= 5
So, the answer is, 248 - 5 = 243.

This is the logic which i have used in my code.
Is it correct??
Last edited on
cire (8284)
The logic looks correct, however it is not reflected in your code.

Where, in that jumbled mess above, is a variable representing the number of terms contained in q?

[Edit: A straightforward, encoding of your logic took about 25 lines just going off your description as pseudo-code.]
Last edited on
Topic archived. No new replies allowed.