Algorithm

 problem Link :  https://www.codechef.com/problems/DOLL 

Problem

“You won’t get caught if you hide behind someone.”

Sang-Woo advises Gi-Hun to hide behind someone to avoid getting shot.

Gi-Hun follows Sang-Woo's advice and hides behind Ali, who saved his life earlier. Gi-Hun and Ali both have the same height, �. Many players saw this trick and also started hiding behind Ali.

Now, there are � players standing between Gi-Hun and Ali in a straight line, with the �th player having height ��. Gi-Hun wants to know the minimum number of players who need to get shot so that Ali is visible in his line of sight.

Note:

  • Line of sight is a straight line drawn between the topmost point of two objects. Ali is visible to Gi-Hun if nobody between them crosses this line.
  • Even if there are some players who have the same height as that of Gi-Hun and Ali, Ali will be visible in Gi-Hun's line of sight.
  • Gi-Hun and Ali have the same height.

Input Format

  • The first line of input contains a single integer �, denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains two space-separated integers � and �, denoting the total number of players between Gi-Hun and Ali and the height of both of them respectively.
  • The second line of each test case contains � space-separated integers, denoting the heights of the players between Gi-Hun and Ali.

Output Format

For each test case, output in a single line the minimum number of players who need to get shot so that Ali is visible in Gi-Hun's line of sight.

Constraints

  • 1≤�≤105
  • 1≤�≤105
  • 1≤�≤106
  • 1≤��≤106 for every 1≤�≤�.
  • The sum of � across all test cases does not exceed 5⋅105.

Sample 1:

Input
 
Output
 
3
4 10
2 13 4 16
5 8
9 3 8 8 4
4 6
1 2 3 4
2
1
0

Explanation:

Test Case 1: Gi-Hun and Ali have height 10. For Ali to be visible to Gi-Hun, the second person (with height 13) and the fourth person (with height 16) need to get shot. Hence, the minimum number of players who need to get shot is 2.

Test Case 2: Gi-Hun and Ali have height 8. For Ali to be visible to Gi-Hun, the first person (with height 9) needs to get shot. Hence, the minimum number of players who need to get shot is 1.

Test Case 3: Nobody needs to get shot because everyone is shorter than Gi-Hun and Ali.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming

 #include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,h,count=0;
        scanf("%d %d",&n,&k);
        for(int i=0;i < n;i++)
        {
            scanf("%d",&h);
            if(h>k) count++;
        }
        printf("%d\n",count);
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
4 10 2 13 4 16
5 8
9 3 8 8 4
4 6
1 2 3 4

Output

x
–
+
cmd
2
1
0
Advertisements

Demonstration

CodeChef solution DOLL  - Red Light, Green Light Codechef solution in C,C++

Previous
CodeChef solution NUM239 - Counting Pretty Numbers Codechef solution in C,C++
Next
CodeChef solution CNDY - Candies Codechef solution in C,C++