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 TA, he must understand how the students are performing.
Red Cape Flying Cat wants to know how many ways a student can achieve a failing grade. However, he is currently on his way flying to Antarctica to see penguins, so he asks you to help him write a program to calculate it.
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 two 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 <= 80000 <= arr[i] <= 10^8
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. Calculate the Number of Pairs with Sum Less Than k
Goal
Your goal is to implement a function that calculates how many pairs have a sum less than k:
Please note that the answer may exceed the range of int.
long long number_of_pair_less_than_k(const int len, const int* arr[2], const int k)
You will be given two already sorted arrays, located at arr[0] and arr[1]. The length of both arrays is len. You need to calculate how many pairs have a sum less than k.
Formally, you need to calculate the number of pairs (i, j) such that 0 <= i, j < len and arr[0][i] + arr[1][j] < k.
Constraint
1 <= len <= 5 * 10^50 <= arr[i][j] <= 10^8- Both
arr[0]andarr[1]are increasing.
Example
code:
int a1[3] = {1, 2, 3};
int a2[3] = {4, 5, 6};
const int* arr[2] = {a1, a2};
int result = number_of_pair_less_than_k(3, arr, 8);
printf("Number of pairs less than k = %d\n", result);
output:
Number of pairs less than k = 6
Input
The first line contains a single integer Q (1 <= Q <= 10), representing the total number of operations.
The above two operations are input in the following format:
sort_array:
1
<len>
<arr[0]> <arr[1]> ... <arr[len-1]>
number_of_pair_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]>
Output
The output should have Q lines, corresponding to the output of each operation.
sort_array:
Sorted arr = [<arr[0]>, <arr[1]>, ..., <arr[len-1]>]
number_of_pair_less_than_k:
Number of pairs less than k = <result>