Каталог по темам

Задачи

Страница: << 49 50 51 52 53 54 55 >> [Всего задач: 277]

Задача 102888

[Золотая лихорадка ]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Обход графа в ширину	]

Сложность: 4

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

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

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

Входные данные
В первой строке входного файла записано целое число K – количество различных веществ, участвующих и образующихся в алхимических реакциях (2 ≤ K ≤ 100). Вторая строка содержит названия этих веществ, разделенные пробелом (в списке обязательно есть свинец и золото). Названия веществ не длиннее 10 букв.

В третьей строке записано целое число L – количество типов реакций, выполняемых философским камнем (1 ≤ L ≤ 100). Далее идут L описаний этих реакций. Каждое описание реакции состоит из двух строк: первая строка содержит название вещества, которое подвергается превращению, вторая – названия веществ, получающихся в результате реакции.

Выходные данные
Ваша программа должна вывести в выходной файл либо одно целое число – искомое количество граммов золота, либо сообщение «QUANTUM SATIS» (лат. "Сколько нужно"), если Петя может получить любое наперед заданное количество золота.

Пример входного файла
4
свинец золото рога копыта
3
свинец
золото рога копыта
рога
золото копыта
копыта
золото

Пример выходного файла
4

Прислать комментарий Решение

Задача 102896

[Открытки и конверты ]

Тема:

[

Паросочетания

]

Сложность: 4

Жюри решило поздравить авторов метода Форда-Фалкерсона, алгоритмов Флойда-Беллмана, Кнута-Морриса-Пратта, формы Бэкуса-Науэра, схемы Ривеста-Шамира-Адлемана и других классиков Computer Science с наступающим 4 июля (Днем независимости). Для этого было куплено N открыток и M конвертов. К сожалению, конверты и открытки оказались разных размеров, и некоторые открытки помещаются не во все конверты. Напишите программу, находящую такое распределение открыток по конвертам, при котором поздравления получат наибольшее число классиков Computer Science. В один конверт разрешается вкладывать не более одной открытки.

Входные данные
В первой строке входного файла записаны числа M и N (0 ≤ M, N ≤ 100). Далее записаны высота и ширина каждого из M конвертов, затем – высота и ширина каждой из N открыток. Размеры конвертов и открыток являются натуральными числами, не превосходящими 32767, и разделяются пробелами и/или символами перевода строки.

Выходные данные
Выведите в выходной файл целое число K – максимальное количество открыток, которые можно разложить по конвертам. Далее выведите K пар целых чисел, означающих номер открытки и номер конверта, в который ее необходимо положить.

Пример входного файла
4 4
3 3 141 282 282 141 200 100
3 1 140 280 141 282 201 1

Пример выходного файла
4
1 1 2 3 3 2 4 4

Прислать комментарий Решение

Задача 102898

[Поможем МПС ]

Тема:

[

Потоки

]

Сложность: 4

В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.

Входные данные
В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.

Выходные данные
Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.

Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5

Пример выходного файла
2
2 1 4
2 3 4

Прислать комментарий Решение

Задача 102899

[Девушки и юноши ]

Тема:

[

Паросочетания

]

Сложность: 4

В деревне живут N девушек и столько же юношей. Каждый юноша оценивает всех девушек числами от 1 до N (разных девушек – разными числами), а каждая из девушек аналогичным образом оценивает юношей. Устойчивым паросочетанием называется такое взаимно-однозначное соответствие между юношами и девушками, что для любых двух юношей Ю₁ и Ю₂ и соответствующих им девушек Д₁ и Д₂ выполняются следующие два условия:
    1) либо Ю₁ оценивает Д₁ выше, чем Д₂ , либо Д₂ оценивает Ю₂ выше, чем Ю₁ ;
    2) либо Ю₂ оценивает Д₂ выше, чем Д₁ , либо Д₁ оценивает Ю₁ выше, чем Ю₂.
Напишите программу, которая по заданным оценкам находит некоторое устойчивое паросочетание.

Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 200). В строках с номерами от 2 до N+1 находятся наборы из N чисел, которыми юноши с номерами от 1 до N оценивают девушек. В строках с номерами от N+2 до 2N+1 находятся наборы из N чисел, которыми девушки оценивают юношей. Числа в наборах разделяются пробелами.

Выходные данные
В выходной файл выведите номера девушек, соответствующих юношам с номерами от 1 до N по порядку. Числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла
3
1 2 3
2 3 1
1 2 3
1 2 3
2 3 1
3 1 2

Пример выходного файла
3 2 1

Прислать комментарий     Решение

Задача 102928

[Ограда сада ]

Темы:	[	Перебор с отсечениями	]
Темы:	[	Выпуклая оболочка	]

Сложность: 4

Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал небольшое собрание редких и весьма ценных деревьев. Для того, чтобы обезопасить свою коллекцию от злоумышленников, король приказал возвести вокруг нее высокий забор. Главный королевский колдун был назначен ответственным за исполнение этого поручения.

Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение.

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

Входные данные
В первой строке входного файла записано целое число N – количество деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N строк содержит четыре целых числа x_i, y_i, v_i, l_i, описывающих очередное дерево. (x_i, y_i) – это координаты дерева на плоскости, v_i – его стоимость, а l_i – длина забора, который может быть построен из этого дерева. Все числа v_i, l_i, а также абсолютные величины x_i и y_i – целые числа из диапазона [0, 10000]. Считается, что деревья имеют нулевой радиус.

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

Пример входного файла
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8

Пример выходного файла
2 4 5
3.16

Прислать комментарий Решение

Страница: << 49 50 51 52 53 54 55 >> [Всего задач: 277]