All Tracks Algorithms Searching Ternary Search Problem

The exam
Tag(s):

Easy

Problem
Editorial
Analytics

Kate is wizard. Now she should pass the exam.

During the exam she have to go into the magic room $$N$$ times. Initially there are $$X$$ magic items in the room. Before each visit she can use magic to decrease the number of magic items in the room. For each item she spends $$1$$ mana point to destroy it. After each visit the number of magic items increases by $$2$$ times. She can't go into room if there are more than $$L$$ magic items in it. What minimum mana points does Kate need to pass the exam?

You need to solve this problem for several test cases.

$$INPUT$$

The first line of input contains single integer $$T$$ $$(1 \leq T \leq 10^{5})$$ - a number of test cases.

Then follow $$T$$ lines. The i-th of these lines contains three integers $$X_i$$, $$L_i$$ and $$N_i$$ $$(0 \leq X_i, L_i, N_i \leq 10^{18})$$.

$$OUTPUT$$

Print $$T$$ lines.

The i-th of them should contain single integer - minimum number of mana points needed to pass the exam in the i-th test case.

SAMPLE INPUT
2
2 5 3
6 5 0
SAMPLE OUTPUT
1
0
Explanation

In the first case test Kate should destroy 1 item before the first visit.

In the second test case Kate has already passed exam.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications