Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
problems (25).rtf
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆
  1. 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

()()()

()(())

(())()

(()())

((()))

  1. 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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]