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: