- •Лабораторная №3 Динамическое программирование
- •Взрывоопасность
- •C. Палиндромы
- •Индивидуальные задания
- •1. Вычеркивание цифр
- •2. Задача о рюкзаке
- •3. Очередь
- •4. Восстановление скобок
- •5. Космический мусорщик
- •7. Покупка билетов
- •11. Две стены
- •13. Роботы
- •14. День рождения Иванова
- •16. Копилка
- •17. Возрастающая последовательность
- •18. Взрывоопасность
- •19. Максимальны квадрат
- •22. Лесопилка
11. Две стены
У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет размер 1´1´Li.
Петя знает, что он может построить из кирпичиков прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй – второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.
Формат входных данных
На первой строке входного файла находятся числа N и K (1 £ N £ 5000, 1 £ K £ 100). Следующие N строк содержат описание Петиных кирпичиков: сначала длина Li, затем номер цвета Ci (1 £ Li £ 100, 1 £ Ci £ K). Известно, что у Пети не более 50 кирпичиков каждого цвета.
Формат выходных данных
Выведите на первой строке выходного файла YES, если Петя сможет построить из своих кирпичиков две прямоугольные стены высоты K, j-й слой кирпичиков в каждой из которых будет j-го цвета, и NO в противном случае. В случае положительного ответа, выведите на второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входном файле, начиная с 1). Если решений несколько, можно выдать любое из них.
Примеры
input.txt |
output.txt |
5 2 2 1 2 1 2 1 3 2 3 2 |
NO |
2 1 1 1 3 1 |
YES 1 |
9 3 7 3 1 1 3 2 2 1 3 2 3 1 4 2 4 1 3 3 |
YES 2 3 4 9 |
12. Скобки. Перечислить все правильные скобочные последовательности из 2n скобок в лексикографическом порядке.
Входные данные. Задано одно число – n (n≤10).
Выходные данные. Перечислены все правильные скобочные последователь-ности в лексикографическом порядке.
Пример
Input.txt |
Output.txt |
3 |
()()() ()(()) (())() (()()) ((())) |
13. Роботы
Кафедра ТМОИ создает роботов, которые могут находить и собирать мины с полей. Прежде чем робот начнет работу, поле фотографируется с воздуха и на фотографию наносится сетка. Каждая клетка сетки, содержащая мину, помечается. Все роботы начинают свою работу с верхнего левого угла и заканчивают движение в нижнем правом углу. Робот может двигаться только в двух направлениях: вправо и вниз. После того, как робот достигнет правого нижнего угла, он не может быть перенаправлен или повторно использован. Поэтому заказчик заинтересован в приобретении минимального количества роботов, которые смогут очистить данное поле. Например, рассмотрим карту поля, показанную на рис. 1. Клетки, содержащие мину, помечены буквой ‘M’. По этой схеме роботы будут начинать работу с позиции 1,1 и заканчивать в позиции 8,8.
Рис. 1. Карта поля
Ваша задача – создать программу, которая будет определять минимальное количество роботов, необходимых для уборки всего мусора с поля. В нашем примере требуется три робота.
Формат входного файла
Во входном файле содержится карта поля. В первой строке заданы количество строк и столбцов в карте. Со второй строке заданы координаты расположения мин.
Формат выходного файла
Выходной файл состоит из одной строки, содержащей минимальное количество роботов, необходимых для очистки соответствующего поля.
INPUT.TXT |
OUTPUT.TXT |
8 8 2 2 1 5 3 4 3 8 5 3 5 6 6 5 6 7 8 6 |
3 |
