Shreehari and Runtime error
All submissions for this problem are available.
Shreehari has been trying hard to solve a problem. He has managed to pass some testcases but has received runtime error on others.
He suspects that one of the parameters p in his program, is the reason for this error. For small values of inputs he is sure that the program will pass, however for large values it doesn't.
His code is buggy and over 200 lines, so he has decided to find for which values of p it will pass by writing a script and automating the submission process.
Assume the program gives runtime error for values of p >= x and correct answer for p < x.
He will guess a number y, and if p>=y, his program will give up and print nothing, resulting in WA for those testcases. Note that if his guess y>x he will still get runtime error on few cases.
He is tired of Runtime Error, so he doesn't want more than k Runtime Error submissions. He is fine with WA though.
You are given n, Shreehari's upper bound for x (i.e. for p>n he knows his program gives RE), and k, the number of runtime error submissions, he is able to tolerate.
Your task is to find the minimum number of submissions he needs to make in order to find the least value of p for which his program will fail.
The first line contains the number of testcases T
Each of the next T lines contain two space separated integers n and k denoting the maximum value of parameter p and the maximum number of Runtime Error submissions Shreehari is able to tolerate.
Output T lines , in each line the answer to the corresponding testcase,
i.e The minimum number of submissions Shreehari will need to make in order to find the value of P for which his program fails.
Note that it is possible that the program gives RE for p=1 and does not give RE for p=n.
Constraints1 \leq T \leq 10^5 1 \leq n,k \leq 10^5
- 1 ≤ T ≤ 10^5
- 1 ≤ n, k ≤ 10^5
Should contain all the constraints on the input data that you may have. Format it like:
Input: 1 100 1 Output: 100
Example case 1. Shreehari has to make 100 submissions in worst case in order to find the maximum value of p for which his program passes. His guess will be from 1 to 100 in order.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions