Cousins
Time limit3sMemory limit128 MB
Reconstruct the tree defined by consecutive-number groups and count the cousins of node k.
- Level
Medium4 of 10
- Topics
- Tree, Simulation
- Solved
- No attempts yet
Problem
A tree is built from an increasing sequence of integers by the rules below.
- The first integer of the sequence is the root of the tree.
- The sequence is cut into groups of consecutive numbers. A group ends wherever two neighboring numbers are not consecutive.
- The group right after the root contains the children of the root. The first number of that group is always at least 2 larger than the root, so the root forms a group by itself.
- Each remaining group, in order, becomes the children of a node that has no children yet. When several such nodes exist, the group goes to the node with the smallest number.
For example, the sequence 1 3 4 5 8 9 15 30 31 32 is cut into {1}, {3, 4, 5}, {8, 9}, {15}, {30, 31, 32}. The root is 1, and 3, 4, 5 are the children of 1. Then {8, 9} becomes the children of 3, {15} becomes the child of 4, and {30, 31, 32} becomes the children of 5.
Two nodes are cousins when their parents differ and those two parents are siblings.
Given the sequence and a node number k, write a program that counts the cousins of k.
Input
The input has several test cases. The first line of each test case has the number of nodes n and the number k of the node whose cousins must be counted. (, ) The second line has the n numbers of the sequence. Every number is at least 1 and at most 1,000,000, and the sequence always increases. k always appears in the sequence.
The last line of the input has two zeros.
Output
For each test case, print the number of cousins of k on one line.