50031. Pairing

I'm a slow walker, but I never walk backwards.

Problem Description

You have $n$ integers and you want to pair them into $n/2$ pairs. You first sort the numbers, then pair the largest number with the smallest number, then the second largest number with the second smallest number, and so on. Repeat this process then you will get $n/2$ pairs of numbers, then you compute the sums of every pair.

  • If the flag INC is defined then you want to print these sums in increasing order. If two sums are the same then the sum with the smallest index in the original input array is printed first. Within a line you should print the smaller index first.
  • If the flag DEC is defined then you print these sums in decreasing order. If two sums are the same then the sum with the largest index in the original input array is printed first. Within a line you should print the larger index first.
void pairPrint(int numbers[], int n);

For example, if numbers are ${1, 3, 5, 2}$. The output should be as follows if DEC is specified.

6 = numbers[2] + numbers[0]
5 = numbers[3] + numbers[1]

For example, if numbers are ${1, 3, 4, 2}$. The output should be as follows if INC is specified. Note that since both ${1, 4}$ and ${2, 3}$ have sum 5, the pair ${1, 4}$ is printed first because the index of 1 (i.e., 0) is smaller than the index of 3 (i.e., 2).

5 = numbers[0] + numbers[2]
5 = numbers[1] + numbers[3]

Subtasks

  • 10pt. The numbers are 5, 6, 7, and 8, and the flag INC is specified.
  • 10pt. $n = 4$, and the flag INC is specified..
  • 15pt. $n = 6$, and the flag INC is specified.
  • 15pt. $n$ is no more than 30, and the flag INC is specified.
  • 50pt. $n$ is very large so you must use qsort. Either INC or DEC is specified.

main.c

#include "pair.h"
#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int *A = (int *) malloc(sizeof(int)*n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        pairPrint(A, n);
        free(A);
    }
    return 0;
}

pair.h

void pairPrint(int numbers[], int n);

pair.c

#include <stdio.h>
 
void pairPrint(int numbers[], int n){
    // Fill your code here.
}

Sample Input

4
1 3 5 2

Sample Output (if a #define INC is defined)

5 = numbers[1] + numbers[3]
6 = numbers[0] + numbers[2]

Sample Output (if a #define DEC is defined)

6 = numbers[2] + numbers[0]
5 = numbers[3] + numbers[1]

Discussion