Description

著名的zjb学长不曾说过：“邂逅一个心仪的女孩子比在二叉树上找一个节点要容易的多。”现在给你 n 个节点编号和一个完全二叉树（如图），请你求出这些节点的层数。设定根节点为第一层，其子节点为第二层，依此类推。

Input

输入的第一行为一个整数 n ，代表有 n 个节点。从第 2 行到第 n+1 行各有一个整数ai，表示待求的节点编号

Output

输出为n行，每行有一个整数，表示第 i 个节点的层数 Ci

Sample Input

5
3
5
1
8
2

Sample Output

2
3
1
4
2

Hint

1 ≤ n ≤ 106 1 ≤ ai ≤ 231-1 在输入输出时使用cin/cout可能会超时，请尽量使用scanf/printf输入输出或采用其他快读方式

Source

SZTU Monthly 2020 Oct.

Author

DOGGOD_Q

题目解析

这道题只考察了二叉树最基本的性质，就是二叉。换句话说。在完全二叉树上，编号为k的节点的子节点编号分别为 2k 和 2k+1 我们根据每个数可以除2几次来判断他所在的层数，代码实现没有太大难度

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int num;
        scanf("%d", &num);
        int ans = 1;
        while(num >>= 1)ans++;
        printf("%d\n", ans);
    }
    return 0;
}

SZTUOJ 1024.在二叉树寻求邂逅是否搞错了什么