Description
Story
(The following story is irrelevant to the problem description.)
Red Cape Flying Cat is currently a teaching assistant for "Introduction to Programming (II)." As a dedicated TA, he needs to keep track of the students' learning progress and academic performance.
To do this, Red Cape Flying Cat wants to figure out exactly how many different score combinations can result in a student's average score hitting a specific target value.
However, he is currently in Antarctica, busy playing and belly-sliding with baby penguins. He's having too much fun to pull himself away, so he needs your help to write the program!
Problem Statement
This is a partial judge problem.
In a single test case, the total number of function calls will not exceed 10.
You need to implement the following four functions:
1. Sort an Array
Goal
Your goal is to implement a function that sorts an array:
void sort_array(const int len, int arr[]);
You are given an array of length len. You need to sort the array in ascending order and place the sorted result back into arr.
Constraint
1 <= len <= 30001 <= arr[i] <= 5000
Example
code:
int arr[5] = {4, 8, 7, 6, 3};
sort_array(5, arr);
printf("Sorted arr = [%d, %d, %d, %d, %d]\n", arr[0], arr[1], arr[2], arr[3], arr[4]);
output:
Sorted arr = [3, 4, 6, 7, 8]
2. Count Pairs with Sum Strictly Less Than k
Goal
Your goal is to implement a function that counts how many pairs have a sum strictly less than k:
Please note that the answer may exceed the range of int.
long long number_of_pairs_less_than_k(const int len, const int* arr[2], const int k);
You are given two already sorted (non-decreasing) arrays arr[0] (A) and arr[1] (B), both of length len. Count the number of index pairs (i, j) such that 0 <= i, j < len and A[i] + B[j] < k.
Constraint
1 <= len <= 5 * 10^51 <= k <= 2*10^41 <= arr[0][i], arr[1][j] <= 5000- Both
(A)and(B)are non-decreasing.
Example
code:
int A[5] = {3, 4, 6, 7, 100};
int B[5] = {1, 2, 3, 4, 5};
const int* arr[2] = {A, B};
long long result = number_of_pairs_less_than_k(5, arr, 10);
printf("Number of pairs less than k = %lld\n", result);
output:
Number of pairs less than k = 15
3. Count Pairs with Sum Less Than or Equal to k
Goal
Your goal is to implement a function that counts how many pairs have a sum less than or equal to k:
Please note that the answer may exceed the range of int.
long long number_of_pairs_less_than_or_equal_to_k(const int len, const int* arr[2], const int k);
You are given two already sorted (non-decreasing) arrays arr[0] (A) and arr[1] (B), both of length len. Count the number of index pairs (i, j) such that 0 <= i, j < len and A[i] + B[j] <= k.
Constraint
1 <= len <= 5 * 10^51 <= k <= 2*10^41 <= arr[0][i], arr[1][j] <= 5000- Both
(A)and(B)are non-decreasing.
Example
code:
int A[5] = {3, 4, 6, 7, 100};
int B[5] = {1, 2, 3, 4, 5};
const int* arr[2] = {A, B};
long long result = number_of_pairs_less_than_or_equal_to_k(5, arr, 10);
printf("Number of pairs less than or equal to k = %lld\n", result);
output:
Number of pairs less than or equal to k = 17
4. Count Valid Average Triplets
Goal
Your goal is to implement a function that counts how many triplets (i, j, l) satisfy the condition that C[l] is the average of A[i] and B[j]:
Please note that the answer may exceed the range of int.
long long number_of_valid_average_scores(const int len, const int* arr[3]);
You are given three already sorted (non-decreasing) arrays arr[0] (A), arr[1] (B), and arr[2] (C), all of length len. Count the number of triplets (i, j, l) such that 0 <= i, j, l < len and average of A[i] and B[j] is C[l].
Constraint
1 <= len <= 5 * 10^51 <= arr[0][i], arr[1][j], arr[2][l] <= 5000- All three arrays are non-decreasing.
Example
code:
int A[3] = {1, 2, 5};
int B[3] = {1, 3, 5};
int C[3] = {1, 3, 5};
const int* arr[3] = {A, B, C};
long long result = number_of_valid_average_scores(3, arr);
printf("Number of valid average scores = %lld\n", result);
output:
Number of valid average scores = 4
explanation:
The average of 2 and 5 is not 3, the definition of average does not round the result.
Subtask
Input
The first line contains a single integer Q (1 <= Q <= 10), representing the total number of function calls.
Each of the following Q operations is formatted as follows:
sort_array
1
<len>
<arr[0]> <arr[1]> ... <arr[len-1]>
number_of_pairs_less_than_k
2
<len> <k>
<arr[0][0]> <arr[0][1]> ... <arr[0][len-1]>
<arr[1][0]> <arr[1][1]> ... <arr[1][len-1]>
number_of_pairs_less_than_or_equal_to_k
3
<len> <k>
<arr[0][0]> <arr[0][1]> ... <arr[0][len-1]>
<arr[1][0]> <arr[1][1]> ... <arr[1][len-1]>
number_of_valid_average_scores
4
<len>
<arr[0][0]> <arr[0][1]> ... <arr[0][len-1]>
<arr[1][0]> <arr[1][1]> ... <arr[1][len-1]>
<arr[2][0]> <arr[2][1]> ... <arr[2][len-1]>
Output
The output contains Q lines, one per function call, in order.
sort_array
Sorted arr = [<arr[0]>, <arr[1]>, ..., <arr[len-1]>]
number_of_pairs_less_than_k
Number of pairs less than k = <result>
number_of_pairs_less_than_or_equal_to_k
Number of pairs less than or equal to k = <result>
number_of_valid_average_scores
Number of valid average scores = <result>