Версия для печати
Убрать все задачи

---

Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:
    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·10⁹ , число M – 10 000. Номера объектов в подзадаче 2 не будут превышать 2.1·10⁹. Все входные данные корректны.

   Решение

---

При каком отношении оснований трапеции существует прямая, на которой шесть точек пересечения с диагоналями, боковыми сторонами и продолжениями оснований трапеции высекают пять равных отрезков?

   Решение

Страница: 1 2 >> [Всего задач: 6]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 108029  (#1)

Темы:   [ Две пары подобных треугольников ] [ Трапеции (прочее) ]

Сложность: 3 Классы: 8,9

При каком отношении оснований трапеции существует прямая, на которой шесть точек пересечения с диагоналями, боковыми сторонами и продолжениями оснований трапеции высекают пять равных отрезков?

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

Решение

---

Задача 97969  (#2)

Темы:   [ Числовые таблицы и их свойства ] [ Примеры и контрпримеры. Конструкции ] [ Индукция (прочее) ] [ Теория групп (прочее) ]

Сложность: 4+ Классы: 8,9,10

Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (вертикальные и горизонтальные ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?

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

Решение

---

Задача 97973  (#3)

Темы:   [ Свойства коэффициентов многочлена ] [ Целочисленные и целозначные многочлены ] [ Двоичная система счисления ]

Сложность: 4 Классы: 8,9,10

P(х) – многочлен с целыми коэффициентами. Известно, что числа 1 и 2 являются его корнями. Докажите, что найдётся коэффициент, который меньше –1.

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

Решение

---

Задача 97974  (#4)

Темы:   [ Двоичная система счисления ] [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 8,9,10

Имеется множество билетов с номерами от 1 до 30 (номера могут повторяться). Каждый из учеников вытянул один билет. Учитель может произвести следующую операцию: прочитать список из нескольких (возможно – одного) номеров и попросить их владельцев поднять руки. Сколько раз он должен проделать такую операцию, чтобы узнать номер каждого ученика? (Учеников не обязательно 30.)

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

Решение

---

Задача 97975  (#5)

Темы:   [ Наглядная геометрия в пространстве ] [ Куб ] [ Четность и нечетность ] [ Принцип Дирихле (прочее) ] [ Доказательство от противного ]

Сложность: 3+ Классы: 8,9,10,11

Куб 20×20×20 составлен из 2000 кирпичей размером 2×2×1.
Докажите, что его можно проткнуть иглой так, чтобы игла прошла через две противоположные грани и не уткнулась в кирпич.

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

Решение

---

Страница: 1 2 >> [Всего задач: 6]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями