You are not logged in. Please login at www.codechef.com to post your questions!

×

PINS - Editorial

0
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.

This question is marked "community wiki".

asked 16 Jul '18, 03:29

melfice's gravatar image

4★melfice
811837
accept rate: 0%

edited 16 Jul '18, 23:14

admin's gravatar image

0★admin ♦♦
19.8k350498541


include<studio.h>

link

answered 19 Jul '18, 11:08

shahapurf's gravatar image

0★shahapurf
1
accept rate: 0%

share soln link in case you have a doubt

(19 Jul '18, 14:00) l_returns5★

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

link

answered 19 Jul '18, 22:11

atom9006's gravatar image

2★atom9006
11
accept rate: 0%

edited 19 Jul '18, 22:12

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

(20 Jul '18, 01:09) melfice4★

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

(17 Aug '18, 18:57) atom90062★

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);

    }

}

}

link

answered 21 Jul '18, 19:29

tush38's gravatar image

0★tush38
1
accept rate: 0%

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); } }

link

answered 22 Jul '18, 17:51

enseitankado's gravatar image

3★enseitankado
1
accept rate: 0%

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); }

link

answered 25 Jul '18, 00:37

rasheduzzaman's gravatar image

0★rasheduzzaman
1
accept rate: 0%

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.

link

answered 31 Jul '18, 00:18

umangahuja1's gravatar image

4★umangahuja1
202
accept rate: 0%

@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

link

answered 12 Feb, 15:17

chaudhary_19's gravatar image

4★chaudhary_19
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×1,652
×120

question asked: 16 Jul '18, 03:29

question was seen: 3,330 times

last updated: 12 Feb, 15:17