--->
22 задач
<---
Источники
#1131
Темы:
[Перебор с отсечением]
[Двумерные массивы]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
«Что за свинья прошла здесь - корова, что ли?»
Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.
К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.
Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).
Напишите программу, вычисляющую это минимальное число разрезов.
Входные данные
Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.
Выходные данные
В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
Примеры
Входные данные
1 10 1 1 1 1 1 0 0 0 0 0
Выходные данные
0
Входные данные
2 2 1 0 0 0
Выходные данные
1
#1152
Темы:
[Перебор с отсечением]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Окружная олимпиада,
2008 (четвертый интернет-этап),
запад,
Задача C
]
Дачный участок Степана Петровича имеет форму прямоугольника размером a × b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.
Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.
Степан Петрович хочет расположить грядки таким образом, чтобы их суммарная площадь была максимальной. Грядки не должны пересекаться, но могут касаться друг друга.
| грядка №1 |
|
| |
| дом | |||
| сарай | грядка №2 | ||
|
| |||
Требуется написать программу, которая по заданным размерам участка и координатам построек определяет оптимальное расположение планируемых грядок.
Входные данные
В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2).
Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000).
Далее следуют n строк, каждая из которых содержит четыре целых числа xi,1 , yi,1, xi,2, yi,2 –координаты двух противоположных углов постройки (0 xi,1 < xi,2 a, 0 yi,1 < yi,2 b). Различные постройки не могут пересекаться, но могут касаться друг друга.
Выходные данные
В выходной файл необходимо вывести m строк, каждая из которых содержит координаты двух противоположных углов предполагаемой грядки. Координаты должны быть целыми (всегда можно добиться максимальной суммарной площади грядок, располагая их в прямоугольниках с целыми координатами).
В случае, если в вашем решении Степану Петровичу следует расположить менее m грядок, необходимо вывести для грядок, которые не следует сажать, строку «0 0 0 0» (см. второй пример ниже).
Примеры
Входные данные
2 2 7 5 4 2 6 4 0 1 2 2
Выходные данные
0 2 4 5 2 0 7 2
Входные данные
3 2 4 4 0 0 4 1 0 1 1 4 3 1 4 4
Выходные данные
1 1 3 4 0 0 0 0
#1340
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2009,
Задача D
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
В стране Флатландия решили построить легкоатлетический манеж с M одинаковыми прямолинейными беговыми дорожками. Они будут покрыты полосами из синтетического материала пружинкин. На складе имеются N полос пружинкина, длины которых равны 1, 2, …, N метров соответственно (i-я полоса имеет длину i метров).
Было решено использовать все полосы со склада, что определило длину дорожек манежа. Полосы пружинкина должны быть уложены без перекрытий и промежутков. Разрезать полосы на части нельзя. Полосы укладываются вдоль дорожек, ширина полосы пружинкина совпадает с шириной беговой дорожки.
Требуется написать программу, которая определяет, можно ли покрыть всем имеющимся материалом M дорожек, и если это возможно, то распределяет полосы пружинкина по дорожкам.
Входные данные
Во входном файле содержатся два целых числа, разделенных пробелом: M — количество дорожек и N — количество полос пружинкина (1 ≤ M ≤ 1000, 1 ≤ N ≤ 30000).
Выходные данные
В случае, если распределить имеющиеся полосы пружинкина на M дорожек одинаковой длины невозможно, то в выходной файл выведите слово «NO».
В противном случае, в первую строку выведите слово «YES». В последующих M строках дайте описание использованных полос для каждой дорожки в следующем формате: сначала целое число t — количество полос на дорожке, затем t целых чисел — длины полос, которые составят эту дорожку. Если решений несколько, можно вывести любое из них.
В задаче есть группа на первые 17 тестов и она оценивается в 20 баллов. затем идёт потестовая оценка по 2 балла за пройденный тест.
Примеры входных и выходных данных
| Ввод | Вывод |
| 2 4 | YES 2 1 4 2 3 2 |
| 3 4 | NO |
#2530
Темы:
[Перебор с отсечением]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2010,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Задано множество из \(n\) станций и \(m\) трубопроводов, соединяющих некоторые пары станций. Требуется выбрать множество из \(k\) станций, чтобы один из двух концов каждого трубопровода лежал в выбранном множестве. Если построить граф, в котором станции будут служить вершинами, а трубопроводы — рёбрами, то искомое множество будет являться вершинным покрытием в этом графе.
Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн т в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.
Система транспортировки нефти представляет собой совокупность \(n\) распределительных станций и \(m\) трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.
Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания «ЮграНефтеТранс», в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.
Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить \(k\) датчиков (\(k\le40\)) и выбрать \(k\) различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.
Напишите программу, которая проверяет, существует ли требуемое расположение датчиков, и в случае положительного ответа находит это расположение.
Входные данные
В первой строке входного файла записаны три натуральных числа — \(n\), \(m\) и \(k\) (\(k\le n\le2000\), \(1\le m\le10^5\), \(1\le k\le40\)). Далее следуют \(m\) строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до \(n\). Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.
Выходные данные
В первую строку выходного файла выведите слово «Yes», если требуемое расположение датчиков существует, в противном случае — слово «No». В случае положительного ответа выведите во вторую строку выходного файла \(k\) различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.
Система оценивания
Решения, корректно работающие при \(n\le100\) и \(k\le10\), будут оцениваться из 60 баллов.
Примеры
Входные данные
9 12 4 1 2 2 3 1 4 4 5 1 6 6 7 1 8 8 9 2 5 4 7 6 9 8 3
Выходные данные
Yes 2 4 6 8
Входные данные
8 12 4 7 4 7 5 3 1 2 8 4 3 3 2 6 1 1 2 1 4 6 5 8 6 8 7
Выходные данные
No
Входные данные
4 3 1 3 1 3 2 3 4
Выходные данные
Yes 3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Магическим квадратом будем называть квадрат с одинаковой суммой чисел по всем вертикалям и горизонталям; никаких требований на суммы по диагоналям накладывать не будем. Составьте такой квадрат из заданного набора чисел.
Входные данные
Во входном файле записаны 16 различных целых чисел в интервале от 0 до 32768
Выходные данные
В выходной файл необходимо вывести искомое расположение чисел, составляющее магический квадрат 4*4 (каждое число должно встречаться ровно один раз), в четырех строках по четыре числа, или строку NO SOLUTION, если квадрат составить нельзя.
Примеры
Входные данные
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Выходные данные
1 6 13 14
2 11 12 9
15 7 4 8
16 10 5 3
Выбрано
:
|