All submissions for this problem are available.
Superman needs to be more fast. He asked Flash to give him problems which he can practice. Flash thinks of a problem. He gives Superman a complete binary tree http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html containing N nodes. Nodes are numbered as follows:
Root node is numbered 1.
In the lower level nodes are numbered from left to right with consecutive numbers.
For example at second level nodes are numbered 2 and 3, at third level nodes are numbered 4 5 6 7 and so on.
Then he gives him Q queries.
Each query will contain number between 1 and N. Superman needs to tell him the number of leaves(nodes which do not have any child) in the tree rooted at that number very fast.
First line contains an integer T, denoting the number of test cases. For each test case:
- First line contains two space separated integer n, q denoting the number of nodes in the binary tree and number of queries to be asked
- Next q lines would contain an integer x
For each test case
- Output q lines, answer to each query in a different line.
- 1 <= T <= 100
- 1 <= Q <= 10000
- 1 <= N <= 1e18
- 1 <= x <= N
Input: 2 1 1 1 12 2 1 2 Output: 1 6 4
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions