Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2014. november 30.

November 30, 2014 10:30 AM – November 30, 2014 3:30 PM

Gold Rush

Alice and Bob are on an adventure trip. Deep in the woods, they discover a mysterious deep cave, which they enter flutteringly. They find an old console with a giant bar of gold in it. On the bar, there is a number n. Both try to carry the gold out of the cave, but it is too heavy for one of them.

Suddenly, a little fairy appears in the corner of the cave and approaches Alice and Bob: “This gold is heavy. It weighs 2n femtograms (10–15 grams) and n can reach 62.”

Bob answered: “What luck! Alice's knapsack can carry up to a femtograms and mine b femtograms with a + b = 2n.” Alice interjected: “But how can we divide the gold?”

Fairy: “I can help you with a spell that can burst one piece of gold into two equally weighted ones. But for each single spell, the cave will be locked one additional day.”

Alice consults with Bob to use the help of the fairy and take all of the gold. How long will they be trapped if they are clever?

Input Specification

The input starts with the number t ≤ 1000 of test cases. Then t lines follow, each describing a single test case consisting of three numbers n, a, and b with ab ≥ 1, a + b = 2n, and 1 ≤ n ≤ 62.

Output Specification

Output one line for every test case with the minimum number of days that Alice and Bob are locked in the cave.

Sample Input

  1. 3
  2. 2 2 2
  3. 2 1 3
  4. 10 1000 24
download as text file

Output for Sample Input

  1. 1
  2. 2
  3. 7
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019