А. Две коробки. Условие Алексей купил две коробки конфет и хочет раздать конфеты друзьям. Из первой коробки он раздает конфеты девочкам, из другой - мальчикам. При этом Алексей хочет раздать все конфеты так, чтобы любой мальчик получил столько же конфет, что и девочка, при этом каждому должно достаться как можно больше конфет. Напишите программу, определяющую, какое максимальное количество конфет может получить каждый из друзей. Формат входных данных: В единственной строке входных данных содержится два целых положительных числа, не превышающих 100 - количество конфет в каждой из коробок. Формат выходных данных: В единственной строке выходных данных необходимо вывести единственное целое число - искомое максимальное количество конфет. Пример входных данных: 2 4 Пример выходных данных: 2 Решение Необходимо было вывести наибольший общий делитель двух чисел (используя алгоритм Евклида) Б. Жребий Крижановского Условие Жребий Крижановского - это игра, придуманная математиком Олегом Феликсовичем Крижановским. Каждый игрок независимо от других называет натуральное число. Затем среди названных определяют числа, названные только одним из игроков. Выигрывает тот, кто назвал наименьшее их этих чисел, причем количество выигранных им очков равно названному числу. Напишите программу, определяющую количество очков, набранных выигравшим игроком. Формат входных данных: В первой строке входных данных содержится единственное число 1<=N<=100 - количество игроков. Во второй строке содержится N целых положительных чисел, не превышающих 1000000, разделенных одним пробелом. Формат выходных данных: В единственной строке выходных данных содержится единственное число - количество очков, набранных выигравшим игроком. Если никто не выиграл, необходимо вывести 0. Пример входных данных: 7 5 1 1 3 1 2 2 Пример выходных данных: 3 Решение Заведём массив размером 10^6, где для каждого числа будем хранить, сколько всего раз оно было названо игроками. Далее бежим по массиву с начала и, если значение элемента в массиве равно 1, то выводим его и завершаем программу. Если мы прошли по массиву и так и не нашли элемент в массиве, который равен 1, выводим 0. В. Большой треугольник Условие На день рождения Малышу приготовили торт в форме выпуклого многоугольника. Малыш может угостить Карлсона любым треугольным фрагментом торта, если вершины треугольника совпадают с вершинами многоугольника. Малыш хочет отнести Карлсону как можно больший кусок торта. Напишите программу, определяющую минимальную сумму номеров вершин, которые являются вершинами треугольного фрагмента торта. Формат входных данных: В первой строке находится единственное целое положительное число N<=100 - количество вершин многоугольника. В следующей строке находится 2N целых положительных чисел, не превышающих 1000 - координаты вершин многоугольника в порядке нумерации, начинающейся с 1 и идущей по часовой стрелке. Формат выходных данных: В единственной строке необходимо вывести единственное число - минимальную сумму номеров вершин треугольника максимальной площади. Пример входных данных: 4 1 1 1 2 2 2 2 1 Пример выходных данных: 6 Решение Тремя циклами перебираем вершины треугольника. Храним текущий ответ: текущую максимальную площадь и сумму номеров вершин для нее. Для каждой тройки вершин пытаемся улучшить ответ: Вычисляем площадь треугольника, например, при помощи косого произведения векторов. Можно вычислять удвоенную площадь. Это удобнее, поскольку удвоенная площадь решётчатого многоугольника всегда является целым числом (это следует из теоремы Пика), и не будет необходимости сравнивать нецелые числа. Если площадь строго больше или площадь равна, а сумма номеров вершин меньше, то обновляем ответ. Асимптотика - О(N^3) Г. Прогулка по лесу Условие Григорий и Галина гуляют по дорожкам дендропарка, проходя мимо определенных деревьев. Вместо названий деревьев на табличках были указаны номера, поэтому после прогулки дети решили выяснить, сколько различных маршрутов соответствуют той последовательности номеров, которую они наблюдали в ходе прогулки. Напишите программу, определяющую количество указанных выше маршрутов. Формат входных данных: В первой строке данных задается целое положительное число N<=100 - количество деревьев. Во второй строке входных данных приводится N целых положительных чисел M[i]<=100 - номера видов деревьев. В третьей строке входных данных задается целое положительное число K<=100 - количество деревьев, встреченных Галиной и Григорием. В четвертой строке указано К чисел L[i] - номера видов деревьев в том порядке, в котором дети встречали их в дендропарке. В следующих N строках содержится информация о дорожках. В строке с номером j перечисляются номера деревьев, с которыми дерево с номером j-4 соединено дорожками. Все числа в этих строках разделены пробелом. Формат выходных данных: В единственной строке выходных данных необходимо вывести единственное целое положительное число - количество различных маршрутов, соответствующих последовательности, отмеченной Галиной и Григорием. Пример входных данных: 5 1 2 3 1 2 4 1 2 3 1 2 3 5 1 3 4 1 2 4 5 2 3 5 1 3 5 Пример выходных данных: 8 Решение Пусть деревья и дорожки - это граф. Для удобства будем хранить его матрицей смежности. Решаем задачу при помощи двумерного динамического программирования. Храним массив d размерами N * K. 1) Что считаем? Каждая клетка массива d[i][j] хранит ответ на задачу, если Григорий и Галина встретили j первых деревьев из этих K, при том последнее было дерево с номером i (номер порядковый - от 1 до N, а не номер вида). 2) Как считаем (формула перехода)? Считаем динамику назад. Научимся вычислять значение в клетке d[i][j]. Если M[i] != L[j], то d[i][j] = 0 (так как дерево с номером i было последним, которое видели Галина и Григорий, а номер его вида не равен номеру вида j-ого дерева из массива L. То есть таких путей не существует) Иначе d[i][j] - это сумма всех таких d[k][j - 1], что в графе есть ребро (k, i). 3) База динамики - первый столбец обрабатываем отдельно: если номер вида дерева равен номеру вида дерева, которое первым встретилось Галине и Григорию, то в эту клетку ставим 1. То есть если M[i] = L[0], то d[i][0] = 1 4) Как считаем (в каком порядке)? Поскольку мы делаем динамику назад и нам всегда необходимо знать ответы в предыдущем столбце, необходимо по очереди обрабатывать столбцы, а потом в каждом столбце каждую клетку. 5) Где хранится ответ? Ответ на задачу - это сумма всех чисел в последнем столбце массива d.
Асимптотика - О(LKN^2), где L - длина числа, являющегося ответом. Стоит заметить, что существуют такие входные данные, что ответом для них будет число, равное N*(N - 1)^(K-1). А если N = K = 100, то это 100*99^99, что явно не влезает ни в один целочисленный тип. Поэтому в этой задаче также необходимо написать сложение длинных чисел. Автор разбора - Александр Цаплин |
| |||||||||