B. Stairs SOLUTION CODEFORCES

Stairs SOLUTION CODEFORCES

Jett is tired after destroying the town and she wants to have a rest. She likes high places, that’s why for having a rest she wants to get high and she decided to craft staircases.

A staircase is a squared figure that consists of square cells. Each staircase consists of an arbitrary number of stairs. If a staircase has nn stairs, then it is made of nn columns, the first column is 11 cell high, the second column is 22 cells high, ……, the nn-th column if nn cells high. The lowest cells of all stairs must be in the same row.

A staircase with nn stairs is called nice, if it may be covered by nn disjoint squares made of cells. All squares should fully consist of cells of a staircase.This is how a nice covered staircase with 77 stairs looks like:B. Stairs SOLUTION CODEFORCES

Find out the maximal number of different nice staircases, that can be built, using no more than xx cells, in total. No cell can be used more than once.Input

The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000)  — the number of test cases.

The description of each test case contains a single integer xx (1≤x≤1018)(1≤x≤1018)  — the number of cells for building staircases.Output

For each test case output a single integer  — the number of different nice staircases, that can be built, using not more than xx cells, in total.

Example

input

4
1
8
6
1000000000000000000

output

1
2
1
30

Note

In the first test case, it is possible to build only one staircase, that consists of 11 stair. It’s nice. That’s why the answer is 11.

In the second test case, it is possible to build two different nice staircases: one consists of 11 stair, and another consists of 33 stairs. This will cost 77 cells. In this case, there is one cell left, but it is not possible to use it for building any nice staircases, that have not been built yet. That’s why the answer is 22.

In the third test case, it is possible to build only one of two nice staircases: with 11 stair or with 33 stairs. In the first case, there will be 55 cells left, that may be used only to build a staircase with 22 stairs. This staircase is not nice, and Jett only builds nice staircases. That’s why in this case the answer is 11. If Jett builds a staircase with 33 stairs, then there are no more cells left, so the answer is 11 again.

Solution:

Program C++:

#include<bits/stdc++.h>
using namespace std;
int T;long long x;
int main(){
	cin>>T;
	while(T--)
	{
		long long pw=1,ans=0;
		cin>>x;
		while(x>=(pw+1)*pw/2){
			x-=(pw+1)*pw/2;
			pw=pw*2+1;ans++;
		}cout<<ans<<endl;
	}
}

Program Java:


import java.util.*;

public class Main {

	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(); 
		for(int i=0;i<t;i++) {
			long x = sc.nextLong();
			findans(x);
			System.out.println();
		}
		sc.close();
	}
	public static void findans(long n) {
		int count = 0; long sum = 1,prev=1;
		while(sum<=n) {
			count++;
			prev = 1+2*prev;
			sum+= ((prev)*(prev+1))/2;
		}
		System.out.print(count);
	}
}

Program Python:

for s in[*open(0)][1:]:
 x=int(s);i=0
 while x>=0:i+=1;x-=(2**i-1)*2**(i-1)
 print(i-1)

Related : 

Leave a Comment