NOTE
This editorial is aimed at people new to competitive programming , making it quite verbose.
PROBLEM LINK:
Author: Pulkit Sharma
Tester: Satyam Gupta
Editorialists: Pulkit Sharma , Satyam Gupta
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
consider an N digit number A (not having any leading zeroes) . We have to find the number of possible A s such that , A + Rev(A) = 10^N - 1 , where Rev(A) is the number
formed by reversing the order of digits of A.
EXPLANATION:
Lets represent A as d_1d_2d_3d_4...d_n
So, for N = 3 and A = 312
d_1 = 3
d_2 = 1
d_3 = 2
Now B = Rev(A) = d_nd_{n-1}...d_3d_2d_1
In our case , the target is 10^N-1 , therefore all elements of the target will be 9
So, what we need to do
(d_1 d_2 d_3d_4...d_n) + (d_n d_{n-1}...d_3d_2d_1) = 99...
We can have two cases
Case 1 : N is odd
Consider N = 3
A = d_1d_2d_3
Therefore,
B = d_3d_2d_1
We need to satisfy the following equations :
d1+d3 =9 , d2+d2 = 9 , d3+d1 =9
The first and the last equations are identical, So we can discard any one of them.
After discarding we are only left with 2 equations
d1+d3 =9 , d2+d2 = 9
Consider the second equation , ( d2+d2=9)
2*d2 = 9
d2 = 9/2
d2 = 4.5
But , since d2 is a digit of a number, it can never be a floating value.
Therefore , whenever N is odd , we cannot have any solution as the middle element comes out to be 4.5 to satisfy the problem’s requirements,but that is not possible.
Case 2 : N is even
Consider N = 4
A = d_1d_2d_3d_4
Therefore,
B = d_4d_3d_2d_1
We need to satisfy the following equations:
d1+d4=9,d2+d3 = 9,d3+d2 = 9, d4+d1 = 9
As before, 2 equations are identical.
After eliminating them , we have
d1+d4 = 9 , d2+d3 = 9
Consider d1+d4=9
It can be easily seen , that the above equation has 10 solutions.
Namely,(0,9), (1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (9,0)
But according to the question d1 cannot be zero. Therfore there are 9 solutions in total
Now,lets see the next equation (d2+d3=9)
Similar as above , this equation has 10 solutions and all of them are valid.
As the two equations are independent of each other, Therefore we have a total of 90 solutions in total for the case where N=4
DERIVING THE FINAL FORMULA
Now we are quite close to the solution. Whenever N is odd, the answer will be 0
And Whenever N is even we will have , 9 solutions for the first equation(made of first digits of A and B)
and 10 solutions for each of the remaining equations.
The number of remaining equations = (N/2 - 1) (As half of them are same, and we already considered the equation made of the first digits)
Final formula = 9*10^{N/2-1}
But there is a minor twist .
As N can go up to 10^5 therefore the resultant number from the formula will be very large.Therefore, instead of storing the number somewhere , we have to just print the result, digit by digit.
So print 9 and N/2-1 number of zeroes.
AUTHOR’S SOLUTION:
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int t,n;
cin>>t;
while(t--)
{
scanf("%ld",&n);
if(n&1 || n<2)
{
printf("0\n");
continue;
}
n=(n/2) - 1;
printf("9");
while(n--)
printf("0");
printf("\n");
}
return 0;
}