Student Who Raises Both Averages
InterviewTime limit1sMemory limit128 MB
Given two groups' IQ lists, count students in the first group whose IQ is below that group's average but above the second group's average.
- Level
Easy3 of 10
- Topics
- Array, Math, Implementation
- Solved
- No attempts yet
Problem
Suppose one C Language student drops that course and joins Introductory Economics. The student is valid if removing them raises the average IQ of the remaining C Language students, and adding them raises the average IQ of the Introductory Economics students.
Given every student's IQ, count how many C Language students satisfy both conditions.
Input
The first line contains the number of test cases T. Test cases may be separated by blank lines.
For each test case, the first line contains N, the number of C Language students, and M, the number of Introductory Economics students. Then N+M integers are given, separated by spaces.
The first N integers are the IQs of the C Language students, and the next M integers are the IQs of the Introductory Economics students.
N and M are positive integers at most 200,000, and N is at least 2. Every IQ is a positive integer at most 100,000.
Output
For each test case, print one line containing the number of C Language students who satisfy both conditions.
Hint
For the C Language average to increase after a student leaves, that student's IQ must be lower than the original C Language average. For the Introductory Economics average to increase after the same student joins, that student's IQ must be higher than the original Introductory Economics average.