PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: tabr, yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
N students took a test, the i-th of them scored A_i marks. All the A_i are distinct.
It is known that exactly X children passed the test.
A student is said to have passed if their score is strictly more than the passing mark.
Find the highest possible passing mark.
EXPLANATION:
The constraints are small, so it is possible to simply brute force the answer.
Clearly, the pass mark is between 0 and 100.
Simply try each one, and then iterate across the entire array to count the number of children who passed if this were to be the pass mark.
Among them, print the maximum value such that exactly X students passed.
This has a complexity of \mathcal{O}(100\cdot N), which is good enough.
It is possible (but unnecessary) to solve the problem with a better complexity.
TIME COMPLEXITY
Between \mathcal{O}(N) and \mathcal{O}(100\cdot N) per test case, depending on implementation.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(101):
passed = 0
for y in a: passed += y > i
if passed >= x: ans = i
print(ans)