Petya Vasechkin
has transferred to a new school. During his first physical education class, he
needs to determine his position in the lineup.
Input. The first line
contains an integer n – the number of students in the class.
The second line
contains a non-increasing sequence of n positive integers representing the heights of the students in the lineup.
The third line
contains an integer x – Petya’s height.
All integers are
positive and do not exceed 200.
Output. Print the
position number where Petya should stand in the lineup.
If there are
students with the same height as Petya, he must stand immediately after them.
|
Sample
input 1 |
Sample output
1 |
8165 163 160 160 157 157 155 154
162 |
3 |
|
|
|
|
Sample
input 2 |
Sample output
2 |
8165 163 160 160 157 157 155 154 160 |
5 |
binary search
The input sequence is
already sorted in non-increasing order. We’ll find Petya’s position using a binary
search with upper bound.
Positions in the lineup
are numbered starting from 1.
Algorithm implementation
Read the input data. Store
the students’ heights in the array v.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
scanf("%d",&x);
If there are students in the lineup whose height is equal to Petya’s, he
stands after them. To find Petya’s position, use a binary search with upper
bound – this is possible because the array is sorted in non-increasing order.
pos =
upper_bound(v.begin(),v.end(),x,greater<int>())
- v.begin();
Print Petya’s position, taking into account that the student
numbering in the problem starts from 1.
printf("%d\n",pos + 1);
Algorithm implementation – own binary search
Read the input data. Store
the students’ heights in the array v.
scanf("%d",&n);
v.resize(n+1);
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("%d",&x);
Petya can take any position from 1 to n + 1. Initialize the
binary search interval: [Left; Right] = [1; n
+ 1].
int Left = 1, Right = n + 1, Middle;
Start the binary search.
while(Left < Right)
{
Middle = (Left + Right) / 2;
if (x <=
v[Middle]) Left = Middle + 1; else Right =
Middle;
}
Print the result – Petya’s position in the lineup.
printf("%d\n",Left);