PINS - Editorial

editorial
, ,
1

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic combinatorics, rational numbers

PROBLEM:

You’re given number N. You have to find co-prime numbers P \geq 0 and Q > 0 such that P/Q is equal to probability of number composed of N digits to be a palindrome.

QUICK EXPLANATION:

Output 1 and 10^{\lfloor N / 2 \rfloor}.

EXPLANATION:

Since leading zeroes are allowed, you can just pick each digit independently which will give you total of 10^N ways to compose the N-digit number. Now how much palindromes you can obtain? If N is even, you can pick first N/2 digits arbitrarily (it can be done in 10^{N/2} ways) and duplicate them to make a palindrome:

a_1,a_2,\dots,a_{N/2},a_{N/2},\dots,a_2,a_1

For odd N you can pick first (N-1)/2 digits and the middle digit (10^{(N+1)/2} ways) and then duplicate them in similar manner:

a_1,a_2,\dots,a_{(N-1)/2},a_{(N+1)/2},a_{(N-1)/2},\dots,a_2,a_1

You can generalize for arbitrary N that you can compose a palindrome in 10^{\lceil N/2 \rceil} ways. Thus the rational number we seek for is:

10^{\lceil N/2 \rceil} / 10^N=1/10^{N-\lceil N/2\rceil}=1/10^{\lfloor N/2 \rfloor}

Thus we have to output 1 and 10^{\lfloor N / 2 \rfloor}.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

2

#include<studio.h>

3

share soln link in case you have a doubt

4

In 3 digit number there are 100 palindrome number but the above solution give 10 output for 3 digit number why ?

5

Why, there will be 10^{\lceil 3/2 \rceil}=10^2 palindromes.

6

public class pins {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	int nooftestcases = sc.nextInt();
	for(int i=0;i<nooftestcases;i++)
	{
		int p=0;
		int q=0;
		int noofdigits = sc.nextInt();
		p=(int)Math.pow(10, noofdigits);
		if(noofdigits>1)
		{
		q=(int)Math.pow(10, noofdigits/2);
		}
		else{
			q=p;
		}
		System.out.print(q/q+" ");
		System.out.println(p/q);
		
	}

}

}

7

why is this showing wrong?
#include
#include
using namespace std;
int main()
{int t,i;
cin>>t;
for(i=1;i<=t;i++)
{int N;
cin>>N;
cout<<"1 "<<pow(10,N/2);
}
}

8

#include<stdio.h>
#include<math.h>
int main()
{
int test,N,Q,P=1;
scanf("%d",&test);
for(int i=0;i<test;i++)
{
scanf("%d",&N);
Q=pow(10,(N/2));
printf("%d %d\n",P,Q);
}
return(0);
}

9

Do not use pow() to compute 10^N or 10^N/2 etc because for N around 10^5 pow(10,N) will have N zeros (i.e 10^5).

Instead just print out the required number of zeros.

10

I runned authors solution in codechef ide i got 1 10 for the 3 digit number.

11

@melfice and @atom9006…I also want to know why for n=3…solution is showing 10…but according to me It should be 100…correct me if i m wrong