Решение номера 8298 ФИПИ

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

 

Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число, так чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

 

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.

 

Максимальная оценка за правильную программу – 2 балла.

 

Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число, так чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

 

Напишите программу для решения этой задачи.

 

Постарайтесь сделать программу эффективной по времени и по используемой памяти (или хотя бы по одной из этих характеристик).

 

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

 

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

 

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

 

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

 

Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

 

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

 

 

Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).

 

Входные данные

 

Для варианта А на вход программе подаётся 6 строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.

 

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

1 3

5 12

6 9

5 4

3 3

1 1

 

Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

 

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

6

1 3

5 12

6 9

5 4

3 3

1 1

 

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

32

 

Решение задания A:

Объяснение

Для решения задания А просто создадим двумерный массив 6 на 2 и переберем все возможные варианты.

 

Решение на языке Pascal

Показать решение

 

Решение на языке Python

Показать решение
 

 

 

Решение задания Б:

Объяснение

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

 

Решение на языке Pascal

Показать решение

 

Решение на языке Python

Показать решение
 

 

Оставить комментарий