Выбор по одному элементу из нескольких множеств

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. Описание входных и выходных данных. В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 5 34 12 51 52 51 Пример выходных данных для приведённого выше примера входных данных: 51 51 Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды. Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения. Максимальная оценка за правильную программу – 2 балла. Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя). НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ. Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4). Входные данные Для варианта А на вход программе подаётся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 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

На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел была нечётна и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Каждый элемент в паре целый, неотрицательный. Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов. Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе. А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла. Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм. Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ. Задача А. Количество пар известно заранее и равно 6. Числа не превышают 100 000. Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 100 000. На вход подается сначала количество пар, затем сами пары. Числа не превышают 10 000. Пример входных данных: 6 5 4 3 2 1 1 18 3 11 12 2 5 Пример выходных данных: 43

На вход программе подается последовательность целых чисел. В первой строке сообщается количество чисел N, во второй строке идут сами числа. Требуется написать программу, которая будет выводить на экран числа в следующем порядке: сначала отрицательные числа, потом положительные. При этом должно сохраняться исходное взаимное положение, как среди отрицательных, так и среди положительных чисел Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется набор данных, состоящий из N = 20 пар целых чисел. Напишите программу для решения такой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения. Максимальная оценка за правильную программу – 2 балла. Задание Б. Имеется набор данных, состоящий из почти произвольного количества N целых чисел, чисел не может быть больше ста, N N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Автомобиль, участвующий в гонке, может быть оснащен двумя разными типами колес (A и B). Вдоль трассы расположены станции, на которых можно выполнить замену колес A на B, эта операция занимает t секунд. Замена колес B на A в ходе гонки технически невозможна. На старт можно выйти с любым комплектом. Для каждого участка между станциями известно, за какое время можно пройти этот участок с каждым из комплектов колес. Необходимо определить, за какое минимальное время можно пройти всю трассу. Напишите программу для решения этой задачи. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеются данные о времени прохождения участков трассы с различными типами колёс. Всего пунктов 10 штук. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения. Максимальная оценка за правильную программу – 2 балла. Задание Б. Имеются данные о времени прохождения участков трассы с различными типами колёс. Пунктов может быть очень много. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Входные данные В первой строке задается количество участков трассы N. Во второй строке задается целое число t — время (в секундах) на замену колес A на B. В каждой из последующих N строк записано два целых числа ai и bi, задающих время (в секундах) прохождения очередного участка с каждым из комплектов. В первой из этих строк указывается время прохождения участка от старта до первой станции, во второй – от первой станции до второй и т. д. Пример входных данных 3 10 130 210 320 140 100 120 Выходные данные Программа должна напечатать одно целое число: минимально возможное время прохождения трассы (в секундах). Пример выходных данных для приведённого выше примера входных данных 400

[рис.] Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую. На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги A на дорогу B. Гонщик стартует в точке A0 и должен финишировать в точке BN. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A0A1, A1A2, …, AN-1AN, B0B1, B1B2, …, BN-1BN. Время прохождения всех переездов A0B0, A1B1, …, ANBN одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется 10 пунктов Аi и 10 пунктов Вi, время прохождения всех переездов известно. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения. Максимальная оценка за правильную программу – 2 балла. Задание Б. Имеется набор данных о пунктах Ai и Bi. Напишите программу для решения этой задачи. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию. Входные данные В первой строке задаётся количество участков трассы N. Во второй строке задаётся целое число t — время (в секундах) прохождения каждого из переездов A0B0, A1B1, …, ANBN. В каждой из последующих N строк записано два целых числа ai и bi, задающих время (в секундах) прохождения очередного участка на каждой из дорог. В первой из этих строк указывается время прохождения участков A0A1 и B0B1, во второй — A1A2 и B1B2 и т. д. Пример входных данных 3 20 320 150 200 440 300 210 Выходные данные Программа должна напечатать одно целое число: минимально возможное время прохождения трассы (в секундах). Пример выходных данных для приведённого выше примера входных данных 750