Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.


By ridzz007 · Limits 1s, 512 MB

You might be familiar with marbles from childhood having beautiful memories playing with them. For those of you don’t know about marbles, they are a small ball of colored glass or similar material used as a toy. See the picture below for better understanding.

Now, you’re given some queries to answer. On each query, you’ll be given the number of marbles you have and the radius of the marbles (all the marbles have same radius). You need to find a box with volume l·w·h, where l is the length, w is the width and h is the height of the box. You have to find a box where maximum of (l,w,h) is minimum possible and you can place all the marbles inside it. Consider the thickness of the box negligible.

Note that you can put the marbles inside the box at any position and they don’t move on their own. Also you can’t merge the marbles into each other.


Input starts with an integer T, the number of queries you have to answer. The next line of each query consists of an integer N and a floating-point number R, denoting the number of marbles you have and the radius of each marble.

1 ≤ T ≤ 105 10^{5}

1 ≤ N ≤ 1018 10^{18}

1 ≤ R ≤ 109 10^{9}


For each query, print the minimum possible value of maximum of(l,r,h) of the box that can contain all the marbles inside it. Also you should print exactly four numbers after the decimal point.

For every output number, if the absolute difference between your and judge’s output are less than 104 10^{-4} , your output will be considered correct. That means, if one of your output is A and the judge has B as its output, your output would be considered correct if ∣A−B∣< 104 10^{-4} is satisfied.


12 1.5
100000 5
1 1

For the first test case,

  1. We can use a box with l = 9.0, w = 8.0, h = 6.0, where max(l,w,h) = 9.0.

  2. We can use a box with l = 12.0, w = 6.0, h = 6.0, where max(l,w,h) = 12.0.

We should choose the first one from the above two as the minimum value of max(l,w,h) is of the first one. Also note that there can be infinitely many configurations, but you should choose the one where max(l,w,h) is minimum possible.



    25% Solution Ratio

    riyad000Earliest, 6M ago

    riyad000Fastest, 0.2s

    riyad000Lightest, 2.2 MB

    riyad000Shortest, 3078B


    Login to submit