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.


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

hide comments
2020-11-09 02:44:40 Rafail Loizou
Tips to not waste time:
1) Reset your dp arrays that you will use
2) This problem requires 10% dp 90% particular observation, it should have been tagged with combinatorics as well
3) For me it worked with float, double and long double the same
4) Doesn't matter if you print endline in the last test case or not. Better not printing to avoid potential time limit.
5) If possibility is P then printing floor(P*100) will work

*SPOILER TEST CASE*
6) For n = 545 and k = 1906, 1907, 1908, 1909 ans is 0 , 1, 1, 0 respectively
2020-03-30 21:21:56
DP is easy but trick used is worth remembering
2019-05-09 16:53:26
Solved


Last edit: 2019-05-09 17:09:20
2019-04-17 18:33:54
Repeat Comment But needs to be on top :
A pip is simply one of those marks on the face of a die. So "exactly k pips in total" should be interpreted as "a sum of k".
2019-03-18 15:52:24
Great Problem >>
2019-03-08 11:45:17
Worst platform , with worst explanation of problems.
2018-09-04 09:59:12
For i throws, the probability of getting (i + 6i) / 2 pips is maximum. Find the value of i for which this maximum is zero because for i+1 throws the probability of getting any number of pips is smaller than the maximum probability for the case of i throws. I found the desired i to be 546.
2018-02-27 13:50:02
explain more plz
2018-01-06 08:11:07
@Shubham Matta, how did you get these bounds? Some mathematical formula?
2017-12-10 15:09:07
poorly explained!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.