10487. Ближайшие суммы

Дано множество чисел и последовательность запросов. В каждом запросе требуется найти такую сумму двух разных чисел из множества, которая будет ближайшей к заданному числу.

Вход. Состоит из нескольких тестов. Каждый тест начинается с количества n (1 < n £ 100) чисел во множестве, за которым следуют эти n чисел. Следующая строка содержит число запросов m (0 < m < 25). Каждая из следующих m строк содержат числа-запросы. Концом входных данных служит тест, для которого n = 0. Каждое число находится в отдельной строке.

Выход. Для каждого теста вывести его номер, а также для каждого числа-запроса s вывести в соответствии с форматом вывода сумму двух разных чисел из множества, ближайшую к s.

Пример входа

5

3
12
17
33
34
3
1
51
30
3
1
2
3
3
1
2
3

3

1
2
3
3
4
5
6
0
 

Пример выхода

Case 1:
Closest sum to 1 is 15.
Closest sum to 51 is 51.
Closest sum to 30 is 29.
Case 2:
Closest sum to 1 is 3.
Closest sum to 2 is 3.
Closest sum to 3 is 3.
Case 3:
Closest sum to 4 is 4.
Closest sum to 5 is 5.
Closest sum to 6 is 5.

РЕШЕНИЕ

перебор

Анализ алгоритма

Занесем множество чисел в массив mas. Для каждого запроса s перебираем все пары чисел из этого множества, находим их сумму. Среди всех сумм ищем ту, которая ближе всего лежит к s.

Пример

В первом тесте входное множество содержит 5 чисел: 3, 12, 17, 33, 34. Попарные суммы элементов этого множества равны: 15, 20, 29, 36, 37, 45, 46, 50, 51, 67. Следующие три теста содержат числа 1, 51, 30. Ближайшей суммой к 1 будет 15, к 51 – 51, к 30 – 29.

Реализация алгоритма

Читаем входные данные пока n ¹ 0. Для каждого теста заносим числа множества в массив mas. Номер теста храним в переменной cs.

cs = 1;

while(scanf("%d",&n),n)

{

for(i = 0; i < n; i++) scanf("%d",&mas[i]);

Читаем количество запросов m к текущему множеству, выводим номер теста cs.

scanf("%d",&m);

printf("Case %d:\n",cs++);

Читаем число-запрос s. Изначально положим искомую сумму res двух чисел из текущего множества равной INT_MAX / 2 (если положить ее равной INT_MAX, то в дальнейших вычислениях возможно переполнение). Константа INT_MAX определена в библиотеке <limits.h>. Перебираем пары чисел mas[i] и mas[j] (i < j). Если они разные, то вычисляем абсолютное значение разницы их суммы и числа s. Если оно меньше текущего значения res, то присваиваем res значение суммы mas[i] и mas[j].

while(m--)

{

scanf("%d",&s);

res = INT_MAX / 2;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

{

if (mas[i] == mas[j]) continue;

if (abs(mas[i] + mas[j] - s) <abs(res - s)) res = mas[i] + mas[j];

}

printf("Closest sum to %d is %d.\n",s,res);

}

}