AE2A - Dice


Jack claims that he has telekinetic powers. He has made a bet with Mike that he would throw a die n times and would get exactly k pips in total. Jack's die has 6 faces with numbers from 1 to 6 written on them and is perfectly symmetric. Mike does not believe in Jack's telekinetic powers (in general, being a tenacious rationalist, he does not believe in telekinesis), but he is concerned that Jack could win the bet simply by luck. Therefore, he would like to know what is the chance (in percent) of such an unlucky event, and asked you to write a program that would help him solve this problem.

Input

The first line of the standard input contains a single integer t (1 ≤ t ≤ 20) denoting the number of test cases. Each of the following t lines contains a description of one test case in the form of two integers ni and ki (1 ≤ ni, ki ≤ 106) separated by a single space.

Output

To the standard output t lines should be written, containing the answers to respective test cases. The answer to one test case is the probability (in percent) that Jack wins the bet, rounded down to the nearest integer.

Example

For the input data:

1
1 6

the correct result is:

16

Task author: Jakub Onufry Wojtaszczyk.


hide comments
Shubham Jadhav: 2017-05-19 15:23:31

Nice Problem :)

big_o_logn: 2017-05-14 22:04:52

AC first try, use the bounds mentioned in the comments and a memo table of doubles

holmesherlock: 2017-01-22 23:53:08

ya plz explain how you got those bounds..@Shubham Matta

Amrit Raj: 2016-09-29 16:53:33

I don't know whats going wrong with the code, it's giving WA if anyone can help
<snip>

Last edit: 2022-07-04 22:55:17
abobakr_pp: 2016-08-30 12:37:55

@Shubham Matta How did you know these bounds ??

theph0enix: 2016-06-08 17:11:51

Nice question. There are bounds where you can simply output 0. Hint: central limit theorem => normal distribution! ;)

Last edit: 2016-06-09 00:25:19
Saurabh Kr Singh: 2016-04-02 20:48:19

@yashmittal I got acc with solution giving 4 for (3,6)

Shubham Matta: 2016-04-01 01:09:20

SO main problem is the bounds ... they are till 545 (n) and 1908 (k) .. after that the answer is 0 for all n,k.

yashmittal: 2016-03-02 09:44:55

can anyone explain how (3,6) will give 0 probablity percent of getting 6 when dice is rolled 3 times

Last edit: 2016-03-03 08:57:58
sarvesh_19: 2016-02-19 22:55:31

bottom up recursion giving tle iterative top down accepted. please help :( http://ideone.com/9aAgcv.


Added by:Race with time
Date:2009-05-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Algorithmic Engagements 2009