APPROX - Editorial

editorial
, ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given a numerator and a denominator of a fraction. You have to calculate the decimal expansion to arbitrary precision - up to 1 million decimal places.

QUICK EXPLANATION

You can precalculate the decimal expansion till 1 million decimals and print the first K digits respectively for each test case.

Thus the problem just breaks down to how you can calculate the decimal to arbitrary precision.

EXPLANATION

For the uninitiated, arbitrary precision math is all about doing in code, all that we’ve been taught to do on paper in elementary. Lets look at how you can divide 103993 with 33102 on paper.

Step 1
       ________
33102 / 103993 \ 3
         99306
       --------
          4687

Step 2
       ________
33102 / 103993 \ 3.1
         99306
       --------
          46870
          33102
         -------
          13768

Step 3
       ________
33102 / 103993 \ 3.14
         99306
       --------
          46870
          33102
         -------
          137680
          132408
         --------
            5272

As you can see, from adding the decimal point onwards, the process is repetitive.

  • Multiply the remainder by 10.
  • Find the next digit in the quotient.
  • Generate the next remainder.

If the remainder were ever to become 0, naturally, the rest of the digits of the quotient would be 0. The following pseudo code implements the above idea.

Given numerator and denominator (assuming numerator < denominator, since we know the first digit is 3)
Let decimal_digits = array of integers /* meaning digits */
Let remainder = numerator

for i = 1 to K
    remainder = remainder * 10
    decimal_digits[i] = remainder / denominator
    remainder = remainder % denominator

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

5 Likes
2

I tried the same approach here but i was getting WA. I don’t know why :frowning: but then I discovered that number is actually repeating decimal so I took the reapeating decimal in array and then printed till desired precision via repeating ove a loop.

#include<cstdio>
using namespace std;
char s[]="415926530119026040722614947737296840070086399613316";
int main()
{
    int k,y;
    scanf("%d",&y);
    while(y--)
    {
        scanf("%d",&k);
        putchar('3');
        if(k!=0)
        {
            putchar('.');
                putchar('1');
                int j=0;
                for(int i=0;i<k-1;++i)
                {
                    putchar(s[j++]);
                    if(j>50) j=0;
                }
 
        }
        printf("\n");
    }
    return 0;
}

3.1(415926530119026040722614947737296840070086399613316) The part in bracket was repeating

10 Likes
3

Nice trick!

4 Likes
4

@anton_lunyov thanks :slight_smile:

2 Likes
5

Why can’t I see Setter’s and Tester’s solutions.