Перейти к содержанию

Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел при делении на 5 давала остаток 1 и при этом была максимально возможной

Имеется набор данных, состоящий из пар целых положительных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел при делении на 5 давала остаток 1 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать −1. Напишите программу для решения этой задачи.

Описание входных и выходных данных.

На вход программе в первой строке подается количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.

Пример входных данных для варианта Б:

6

1 2

7 9

8 3

5 16

19 4

7 7

Пример выходных данных для приведённых выше примеров входных данных:

61

Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.

Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла.

Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.

Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.


Описание алгоритма: создадим три одномерных массива, состоящих из 5 элементов — двух вспомогательных и одного основного. В каждом массиве индекс соответствует остатку от деления на 5 сумм элементов, найденных на предыдущем шаге. Элементами массива являются суммы просмотренных пар элементов, распределённые по соответствующим индексам. К каждой из сумм основного массива добавляем первый элемент из пары и результат сохраняем в первом вспомогательном массиве под номером, соответствующем остатку от деления суммы на 5. К каждой из сумм основного массива добавляем второй элемент из пары и результат сохраняем во втором вспомогательном массиве под номером, соответствующем остатку от деления суммы на 5. Пробегая в цикле от 0 до 4, записываем в каждую ячейку основного массива наибольший из элементов вспомогательных массивов с соответствующим индексом. В результате в основном массиве будут находиться суммы уже просмотренных элементов, распределённых по ячейкам, соответствующих остатку от их деления на 5. Если после ввода всех пар в ячейке основного массива значение элемента с индексом 1 не равно 0, то он и является искомой суммой. Если значение элемента с индексом 1 равно 0, то не существует искомой суммы, которая при делении на 5 даёт в остатке 1.

Программа, C++, gcc 4.9.2.Программа эффективна по времени и по памяти.

#include

using namespace std;

int a, b;

int max_div[5];

int n;

int div1[5], div2[5];

int main() {

cin >> n;

for (int i = 0; i <5; i++)

max_div[i] = 0;

for (int i = 0; i < n; i++) {

cin >> a >> b;

for (int j = 0; j < 5; j++) {

int k = max_div[j] + a;

int x = k % 5;

div1[x] = k;

for (int j = 0; j < 5; j++) {

int k = max_div[j] + b;

int x = k % 5;

div2[x] = k;

for (int j = 0; j < 5; j++)

max_div[j] = max(div1[j], div2[j]);

if (max_div[1] != 0)

cout<

else

cout << -1;

return 0;