Туры:
-
осенний тур, тренировочный вариант, 8-9 класс
(4 задачи)
осенний тур, основной вариант, 8-9 класс
(6 задач)
осенний тур, тренировочный вариант, 10-11 класс
(4 задачи)
осенний тур, основной вариант, 10-11 класс
(6 задач)
весенний тур, тренировочный вариант, 8-9 класс
(4 задачи)
весенний тур, основной вариант, 8-9 класс
(7 задач)
весенний тур, тренировочный вариант, 10-11 класс
(4 задачи)
весенний тур, основной вариант, 10-11 класс
(7 задач)
Фильтр
Выбрана 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
Решение
Задачи
Страница: << 3 4 5 6 7 8 9 [Всего задач: 41]
(Хордой многоугольника называется отрезок, концы которого принадлежат контуру многоугольника, а сам он целиком принадлежит многоугольнику, включая контур).
Страница: << 3 4 5 6 7 8 9 [Всего задач: 41]
Задача 98226 |
|
|
Рассматривается произвольный многоугольник (возможно, невыпуклый).
а) Всегда ли найдётся хорда этого многоугольника, которая делит
его площадь пополам?
б) Докажите, что найдётся такая хорда, что площадь каждой из частей, на которые она разбивает многоугольник, не меньше чем ⅓ площади всего многоугольника.
(Хордой многоугольника называется отрезок, концы которого принадлежат контуру многоугольника, а сам он целиком принадлежит многоугольнику, включая контур).
|
|
Решение |
Страница: << 3 4 5 6 7 8 9 [Всего задач: 41]
