мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Это старая версия документа!


Задачи на октябрь 2019

Задача №1

Имеется набор данных, состоящий из пар положительных целых чисел.

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

Задача №2

На вход программы поступает последовательность из N целых положительных чисел. Все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен).

Необходимо определить количество пар, для которых произведение элементов делится на 26.

Задача №3

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

Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Задача №4

На вход программы поступают целое число К (0 < К < 10) и последовательность из N целых положительных чисел. Все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен).

Необходимо определить такую пару элементов, что их сумма делится на К и она максимальна среди таких сумм.

З.Ы.

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

Задачи на Ноябрь-Декабрь 2019

Если не указано иное, графы считаются простыми, невзвешенными и неориентированными.

Задача №1

Ввести граф по диаграме (картинке).

Написать программу, определяющую путь между указанными вершинами взвешенного графа, либо его отсутствие.

Оценивание

30 баллов – иногда ошибается

40 баллов – находит путь, но не кратчайший

50 баллов – всегда находит кратчайший путь.

Задача №2

Ввести граф по диаграмме (картинке).

Написать программу, определяющую путь между указанными вершинами орграфа, либо его отсутствие.

Оценивание

30 баллов – иногда ошибается

40 баллов – находит путь, но не кратчайший

50 баллов – всегда находит кратчайший путь.

Задача №3

Программа получает граф в виде файла со списком смежности в формате:

Буква вершины по порядку <пробел> список инцендентных вершин через пробелы <конец строки>.

Данные могут быть повреждены –

Оценивание

30 баллов – может определить число компонент связности в корректноом списке

40 баллов – может определить число компонент связности или некорректность данных

50 баллов – выводит в виде списка все компоненты связности

Задача №4

Программа получает взвешенный граф в виде файла с матрицей смежности.

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

Оценивание

30 баллов – иногда ошибается

40 баллов – строит, но не минимальное

50 баллов – строит минимальное.