PROBLEM LINK: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 coprime 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 $(N1)/2$ digits and the middle digit ($10^{(N+1)/2}$ ways) and then duplicate them in similar manner: $$a_1,a_2,\dots,a_{(N1)/2},a_{(N+1)/2},a_{(N1)/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.
This question is marked "community wiki".
asked 16 Jul '18, 03:29

include<studio.h>answered 19 Jul '18, 11:08

public class pins {
} answered 21 Jul '18, 19:29

why is this showing wrong? include<iostream>include<cmath>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); } } answered 22 Jul '18, 17:51

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); } answered 25 Jul '18, 00:37

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. answered 31 Jul '18, 00:18
