ACM_0090 - COUNT YOUR COUSINS
A tree is formed from a strictly increasing sequence of integers as follows:
- The first integer in the sequence is the root of the tree
- The next set of consecutive integers in the sequence describes the children of the root. The first of these will be greater than root+1.
- From there, each set of consecutive integers describes the children of the lowest numbered node which does not yet have children.
- Non-consecutive integers mark a break between one set of children and the next.
For example, the sequence:
1 3 4 5 8 9 15 30 31 32
Would produce the following tree:
Two nodes are considered to be Cousins if they have different parents, but their parents are siblings. Given a tree and a particular node of that tree, count the number of Cousins of the node.
Input
There will be several test cases in the input. Each test case will begin with a line with two integers, n (1≤n≤1,000) and k (1≤k≤1,000,000), where n is the number of nodes in the tree, and k is the particular node of interest. On the following line will be n integers, all in the range from 1 to 1,000,000, and guaranteed to be strictly increasing. These describe the tree, in the manner described above. The integers will be separated with a single space. There will be no extra spaces. The value k is guaranteed to be one of the integers on the second line. Input will end with a line with two 0s.
Output
For each test case, output a single integer, indicating the number of cousins of node k. Output no spaces, and do not separate answers with blank lines.
Examples
№ |
stdin |
stdout |
1 |
10 15 1 3 4 5 8 9 15 30 31 32 12 9 3 5 6 8 9 10 13 15 16 22 23 25 10 4 1 3 4 5 8 9 15 30 31 32 0 0 |
5 1 0 |
Added by: | Հրանտ Հովհաննիսյան |
Date: | 2014-01-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | NA Southeast Div II 2013.E |