Подтемы:
-
Динамическое программирование
(46 задач)
Алгоритмы на графах
(28 задач)
Вычислительная геометрия
(16 задач)
Комбинаторика
(33 задачи)
Перебор
(14 задач)
Синтаксический разбор
(8 задач)
Структуры данных
(3 задачи)
Длинная арифметика
(7 задач)
Прочие задачи на сообразительность
(7 задач)
Прочие задачи на аккуратную реализацию
(3 задачи)
Сортировка
(15 задач)
Двоичный поиск
(3 задачи)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
В деревне живут N девушек и столько же юношей. Каждый юноша оценивает всех девушек числами от 1 до N (разных девушек – разными числами), а каждая из девушек аналогичным образом оценивает юношей. Устойчивым паросочетанием называется такое взаимно-однозначное соответствие между юношами и девушками, что для любых двух юношей Ю1 и Ю2 и соответствующих им девушек Д1 и Д2 выполняются следующие два условия:
1) либо Ю1 оценивает Д1 выше, чем Д2 , либо Д2 оценивает Ю2 выше, чем Ю1 ;
2) либо Ю2 оценивает Д2 выше, чем Д1 , либо Д1 оценивает Ю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
Решение
Убрать все задачи
В деревне живут N девушек и столько же юношей. Каждый юноша оценивает всех девушек числами от 1 до N (разных девушек – разными числами), а каждая из девушек аналогичным образом оценивает юношей. Устойчивым паросочетанием называется такое взаимно-однозначное соответствие между юношами и девушками, что для любых двух юношей Ю1 и Ю2 и соответствующих им девушек Д1 и Д2 выполняются следующие два условия:
1) либо Ю1 оценивает Д1 выше, чем Д2 , либо Д2 оценивает Ю2 выше, чем Ю1 ;
2) либо Ю2 оценивает Д2 выше, чем Д1 , либо Д1 оценивает Ю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
Решение
Задачи
Страница: << 22 23 24 25 26 27 28 >> [Всего задач: 155]
Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и ?. Требуется так расставить в этом
выражении скобки, чтобы его значение стало максимально возможным.
Входные данные
Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 106 . Пробелы внутри чисел не допускаются.
Выходные данные
Выведите в первую строку выходного файла максимально возможное после расстановки скобок значение выражения, а во вторую строку – само это выражение (если вариантов несколько, нужно выдать любой из них).
Пример входного файла
1+2 - 3.0*4
Пример выходного файла
0
((1+2)-3)*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
В некоторой стране протянута сеть железных дорог. Требуется наладить
сообщение между двумя различными городами 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
В деревне живут N девушек и столько же юношей. Каждый юноша оценивает
всех девушек числами от 1 до N (разных девушек – разными числами), а
каждая из девушек аналогичным образом оценивает юношей. Устойчивым
паросочетанием называется такое взаимно-однозначное соответствие между
юношами и девушками, что для любых двух юношей Ю1
и Ю2
и соответствующих им девушек Д1
и Д2
выполняются следующие два условия:
1) либо Ю1 оценивает Д1 выше, чем Д2 , либо Д2 оценивает Ю2 выше, чем Ю1 ;
2) либо Ю2 оценивает Д2 выше, чем Д1 , либо Д1 оценивает Ю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
Страница: << 22 23 24 25 26 27 28 >> [Всего задач: 155]
Задача 102787[Жадный калькулятор ] |
|
|
Входные данные
Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 106 . Пробелы внутри чисел не допускаются.
Выходные данные
Выведите в первую строку выходного файла максимально возможное после расстановки скобок значение выражения, а во вторую строку – само это выражение (если вариантов несколько, нужно выдать любой из них).
Пример входного файла
1+2 - 3.0*4
Пример выходного файла
0
((1+2)-3)*4
|
|
Решение |
Задача 102888[Золотая лихорадка ] |
|
|
Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота.
Требуется написать программу, определяющую по заданному описанию
алхимических реакций, выполняемых философским камнем, наибольшее
количество золота, которое может получить Петя.
Входные данные
В первой строке входного файла записано целое число K – количество
различных веществ, участвующих и образующихся в алхимических реакциях
(2 ≤ K ≤ 100). Вторая строка содержит названия этих веществ, разделенные
пробелом (в списке обязательно есть свинец и золото). Названия веществ не
длиннее 10 букв.
В третьей строке записано целое число L – количество типов реакций,
выполняемых философским камнем (1 ≤ L ≤ 100). Далее идут L описаний этих
реакций. Каждое описание реакции состоит из двух строк: первая строка
содержит название вещества, которое подвергается превращению, вторая –
названия веществ, получающихся в результате реакции.
Выходные данные
Ваша программа должна вывести в выходной файл либо одно целое число –
искомое количество граммов золота, либо сообщение «QUANTUM SATIS»
(лат. "Сколько нужно"), если Петя может получить любое наперед заданное количество золота.
Пример входного файла
4
свинец золото рога копыта
3
свинец
золото рога копыта
рога
золото копыта
копыта
золото
Пример выходного файла
4
|
|
|
Решение |
Задача 102896[Открытки и конверты ] |
|
|
Входные данные
В первой строке входного файла записаны числа 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[Поможем МПС ] |
|
|
конечно, городов 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[Девушки и юноши ] |
|
|
1) либо Ю1 оценивает Д1 выше, чем Д2 , либо Д2 оценивает Ю2 выше, чем Ю1 ;
2) либо Ю2 оценивает Д2 выше, чем Д1 , либо Д1 оценивает Ю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
|
|
|
Решение |
Страница: << 22 23 24 25 26 27 28 >> [Всего задач: 155]
