ICLFIN01 - Editorial

PROBLEM LINK:

Contest link: ICLFIN01

AUTHOR:

Rishabh Joshi

TESTER:

Shubham Gupta

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

None

PROBLEM:

GamerBOT is playing Counter Strike on BITS Pilani LAN. It is a modified game(LAST MAN STANDING type plus

maximum number of players connected to the server at one time is 10^18 ), also only two players play at a time (one

on one).

Every player plays atleast one round. The loser of a round is knocked out and the winner has one more win on the

leaderboard. He then plays another match and so on, till the LAST MAN STANDING is decided.

It is known that N players start playing the game. Two players can play against each other only if the absolute

difference of the number of wins of one player to another is at most 1. As GamerBOT always wins, help him figure out

the maximum number of games he can play.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases

follows."

The first line of each test case contains a single integer N denoting the number of total players playing

Output

For each test case, output a single line containing the maximum possible number of games GamerBOT can play.

Constraints

1 ≤ T ≤ 25

2 ≤ N ≤ 10^18

QUICK EXPLANANTION:

This is a classical question of making and understanding patterns.

If we start with N=1 we get the output as 1.

 N=2 output=1

 N=3 output=2

 N=4 output=2

 N=5 output=3

 N=6 output=3

 N=7 output=3

 N=8 output=4

And so on.

We can easily see that the output increments as every Fibonacci term. (2,3,5,8,13,21…)

DETAILED EXPLANATION:

We start by drawing these on a piece of paper. N=8 is a bit tricky. At first it seems that this is classical

binary tree and that the output changes at every power of 2. But if we draw the sequence for N=8, and

understand that the output will be 4, it becomes fairly straight-forward.

The only trick now is to realize that the output changes for every Fibonacci number N.

So for N=2, Output=1; for N=3, Output=2; for N=5, Output=3; for N=8, Output=4; for N=13, Output=5;

for N=21, Output=6…. And so on.

SOLUTION OF THE PROBLEM SETTER:

http://ideone.com/xAklrg