Big Search Trees
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There are all kinds of trees in Chef's garden. There are black sapote trees. There are big santol trees. And of course, there are binary search trees.
Chef's binary search trees are grown in a very specific way. Binary search trees are grown by inserting nodes into it. The first inserted node is called the root. Unlike most of Chef's other trees, binary search trees are grown downwards, and the root is at the top of the tree.
Each node is connected by edges to at most two other nodes below it, called its left child and right child. These can be "null", meaning there are no such children. Finally, each node also has a number on it, called its label.
To grow a binary search tree, you insert a new node to it. The exact rules for inserting a new node are specified by the following pseudocode:
def insert(x, y) if x == null return y if y.label < x.label x.left = insert(x.left, y) else x.right = insert(x.right, y) return x
To insert a new node y to the tree with root x, simply call insert(x, y). The value returned is the root of the new tree.
The following is an example of a binary search tree:
3 / \ 1 5 \ 7
The root of this tree has label 3.
After inserting a new node with a label of 3, the binary search tree becomes:
3 / \ 1 5 / \ 3 7
The depth of a node is the number of edges in the path from that node to the root. For example, the node with label 7 above has a depth of 2, while the node with label 1 has a depth of 1.
Chef has a total of T binary search trees in his garden. Each tree has four numbers associated with it: a, b, m and N. This means that the tree has a total of N nodes, and the kth inserted node has label (a + bk) mod m. So the root, being the first inserted node, has label (a + b) mod m.
For each of Chef's binary search trees, can you determine the depth of the node that was inserted last?
The first line of the input contains an integer T denoting the number of trees. The description of T trees follows.
Each test case consists of a single line containing four space separated integers a, b, m and N.
For each test case, output a single line containing a single integer, denoting the depth of the node that was inserted last in the binary search tree.
- 1 ≤ T ≤ 5×104
- 1 ≤ N ≤ 1016
- 0 ≤ a, b < m ≤ 108
Input: 5 1 2 8 1 1 2 8 2 1 2 8 3 1 2 8 4 1 2 8 5 Output: 0 1 2 1 2
The sample input is illustrated by the image above.
|Time Limit:||2 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
If you are still having problems, see a sample solution here.