Имеется набор данных, состоящий из пар целых положительных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 7 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. Описание входных и выходных данных.
На вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.
Пример входных данных:
6
1 2
7 9
8 3
5 16
19 4
7 7
Пример выходных данных для приведённого выше примера входных данных:
56
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чисел N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,— 4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание алгоритма: создадим три одномерных массива, состоящих из 7 элементов—два вспомогательных и один основной. В каждом массиве индекс соответствует остатку от деления на 7 сумм элементов, найденных на предыдущем шаге. Элементами массива являются суммы просмотренных пар элементов, распределённые по соответствующим индексам. К каждой из сумм основного массива добавляем первый элемент из пары и результат сохраняем в первом вспомогательном массиве под номером, соответствующем остатку от деления суммы на 7. К каждой из сумм основного массива добавляем второй элемент из пары и результат сохраняем во втором вспомогательном массиве под номером, соответствующем остатку от деления суммы на 7. Пробегая в цикле от 0 до 6 записываем в каждую ячейку основного массива наибольший из элементов вспомогательных массивов с соответствующим индексом. В результате в основном массиве будут находиться суммы уже просмотренных элементов, распределённых по ячейкам, соответствующих остатку от их деления на 7.
Если после ввода всех пар в ячейке основного массива значение элемента с индексом 0 не равно 0, то он и является искомой суммой. Если значение элемента с индексом 0 равно 0, то не существует искомой суммы, кратной 7.
Программа, C++, gcc 4.9.2.Программа эффективна по времени и по памяти.
#include
using namespace std;
int a, b, n;
int max_div[7];
int div1[7], div2[7];
int main() {
cin >> n;
for (int i = 0; i < 7; i++)
max_div[i] = 0;
for (int i = 0; i < n; i++) {
cin >> a >> b;
for (int j = 0; j < 7; j++) {
int k = max_div[j] + a;
int x = k % 7;
div1[x] = k;
for (int j = 0; j < 7; j++) {
int k = max_div[j] + b;
int x = k % 7;
div2[x] = k;
for (int j = 0; j < 7; j++)
max_div[j] = max(div1[j], div2[j]);
cout << max_div[0];
return 0;