Задача 76253

Темы:    [ Одномерные массивы ] [ Задачи с целыми числами ]

Сложность: 3- Классы:

Условие

Даны два массива x[1]≤...≤x[k] и  y[1]≤...≤y[l] и число q. Найти сумму вида x[i] + y[j], наиболее близкую к числу q. (Число действий порядка k+l, дополнительная память — фиксированное число целых переменных, сами массивы менять не разрешается.)

Подсказка

Надо найти минимальное расстояние между элементами x[1]≤...≤x[k] и  q - y[l]≤...≤q - y[1], что нетрудно сделать в ходе их слияния в один (воображаемый) массив.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.22