Каталог по источникам

Задачи

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 145]

Задача 102789

[Параллельные вычисления ]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Синтаксический разбор (прочее)	]

Сложность: 4

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

Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения A^oB, равно времени, затрачиваемому на выполнение операции ^o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.

Выражения называется эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
    x + y → y + x ,                    x * y → y * x                    (коммутативный закон),
    x + (y + z) → (x + y) + z ,    x * (y * z) → (x * y) * z    (ассоциативный закон).

Входные данные
В первой строке входного файла содержатся два целых числа p и q (1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200 символов.

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

Пример входного файла
1 1
((a+(b+(c+d)))*e)*f

Пример выходного файла
5
((a+b)+(c+d))*(e*f)
3

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

Задача 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

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

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 145]