ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.

   Решение

Задачи

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 33]      



Задача 98837

Темы:   [ Нерекурсивная генерация объектов ]
[ Синтаксический разбор ]
[ Числа Каталана ]
Сложность: 4

Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. Например, для n=4 есть 5 расстановок:

((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).

Прислать комментарий     Решение

Задача 98838

Темы:   [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4

На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.
Прислать комментарий     Решение


Задача 98839

Темы:   [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4

Перечислить все способы разрезать n-угольник на треугольники, проведя n-2 его диагонали.
Прислать комментарий     Решение


Задача 98842

Темы:   [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4

Доказать, что nчисло Каталана (количество последовательностей длины  2n из n единиц и n минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно   

Прислать комментарий     Решение

Задача 102943

 [Блиц-тур по комбинаторике ]
Темы:   [ Генерация объектов любым методом ]
[ Генерация объектов по номеру и номера по объекту ]
[ Построение перечислителя ]
[ Длинная арифметика как инструмент ]
[ Динамическое программирование (прочее) ]
Сложность: 5

Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:
    1) перестановки N-элементного множества (лексикографический порядок);
    2) K-элементные подмножества N-элементного множества (лексикографический порядок);
    3) разбиения N-элементного множества на K непустых подмножеств (лексикографический, т.е. алфавитный, порядок);
    4) разбиения числа N на слагаемые;
    5) правильные скобочные последовательности из 2N скобок;
    6) двоичные деревья с N вершинами;
    7) цепочки из нулей и единиц длины N без двух единиц подряд;
    8) перестановки N-элементного множества (порядок, в котором соседние перестановки отличаются транспозицией соседних элементов);
    9) K-элементные подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются двумя элементами);
    10) все подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются добавлением или удалением одного элемента);
    11) подвешенные деревья с N вершинами;
решить следующие две подзадачи:
    найти общее количество объектов и породить M объектов, начиная с L-го;
    по заданным объектам получить их номера.
В качестве N-элементного множества везде подразумевается множество {1, ..., N}. Там, где порядок порождения комбинаторных объектов не указан, Вы можете выбрать его по своему усмотрению. Нумерация объектов начинается с нуля.

Таким образом, Вам предстоит написать 11 программ. Задача засчитывается, если Ваша программа прошла все тесты, в противном случае
Вам начисляются штрафные баллы за неверный подход (20% от стоимости задачи), и Вы имеете возможность исправить решение.
В зависимости от того, какую из подзадач требуется решить, входной и выходной файлы имеют один из следующих двух форматов (тем самым, Ваша программа должна сама определять номер решаемой подзадачи).

Входные данные для подзадачи 1

N K L M

Выходные данные для подзадачи 1

<Число объектов>
<Объект номер L>
...
<Объект номер L+M-1>
Каждый объект должен выводиться с новой строки. Формат вывода объектов
остается на Ваше усмотрение с условием, что он должен быть читабельным.

Входные данные для подзадачи 2

N K
<Объект 1>
...
<Объект M>
Формат записи объектов будет соответствовать выходному формату, используемому Вашей программой при решении подзадачи 1.

Выходные данные для подзадачи 2

<Номер объекта 1>
...
<Номер объекта M>
Каждый номер должен быть выведен с новой строки.

Технические ограничения

Если в данной задаче число K не используется, то вместо него будет указан нуль. Числа N и K во всех задачах не превосходят 100, число L не превышает 2·109 , число M – 10 000. Номера объектов в подзадаче 2 не будут превышать 2.1·109. Все входные данные корректны.
Прислать комментарий     Решение


Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 33]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .