1. Простые числа. Загадано простое число x, где 1 < x < N (N < 1000). Его можно отгадать, получив ответы на некоторое число k вопросов вида “x меньше чем...?”. Написать программу, находящую минимальное, заведомо достаточное, k для данного N.
2. “Гвозди”.
В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются веревочками так, чтобы выполнялись следующие условия:
1) к каждому гвоздю была привязана хотя бы одна веревочка;
2) суммарная длина веревочек была бы минимально возможной.
Задание
Написать программу, которая связывает пары гвоздей веревочками как описано выше.
Технические требования
Входными данными являются число гвоздей и их координаты, выходными — минимальная суммарная длина и пары номеров соединяемых гвоздей.
| Пример входных данных | Пример выходных данных |
| 5 11 12 13 16 17 |
3 1 2 2 3 4 5 |
3. “Борьба задач”. Компьютер производительностью 1 миллион операций в секунду работает в многозадачном режиме. Каждая выполняемая в нем программа имеет приоритет, который выражается целым числом и определяет очередность выполнения задачи. При старте любая задача получает нулевой приоритет, а после каждой выполненной в ней команды приоритет возрастает на единицу.
Перед каждой командой компьютер выбирает задачу с НАИМЕНЬШИМ приоритетом, после чего выполняет из нее одну команду и описанный процесс повторяется вновь с учетом изменившегося приоритета.
Смоделировать работу компьютера с учетом следующих условий:
1) все команды компьютера выполняются за одинаковое время;
2) в случае, когда две задачи имеют одинаковый приоритет, то предпочтение отдается той, которая стартовала позднее (считать, что задачи не стартуют одновременно);
3) возможны ситуации, когда в машине нет ни одной задачи, причем эти временные интервалы могут быть значительными;
4) моделируемый промежуток времени не превышает 120 минут; считать, что за это время все введенные задачи закончатся;
5) для удобства ввода исходных данных считать, что время старта любой задачи от начала моделируемого промежутка равно целому числу миллисекунд (1 мс=0.001 с).
Входные данные являются списком задач: указывается количество задач в списке (не более 8), затем время ввода каждой задачи в МИЛЛИСЕКУНДАХ от начала моделируемого промежутка и длина программы в командах.
Выходные данные: номер задачи и время ее окончания в МИКРОСЕКУНДАХ от начала моделируемого промежутка (1 мкс=0.000001 с).
4. Полимино. Полимино — это связная фигура из N клеток. Под связной фигурой здесь понимается фигура, все клетки которой можно обойти ходом шахматной ладьи. Для заданного N в общем случае можно составить несколько различных полимино. Фигуры, совпадающие при переносах и (или) поворотах, различными не считаются.
Задание
Написать программу, которая находит все различные полимино из N клеток для двух случаев:
1) 1 <= N <= 5;
2) 6 <= N <= 8.
Технические требования
Число N вводится с клавиатуры. Программа должна вывести в первом случае список всех найденных полимино и их общее количество (соседние фигуры должны быть разделены ровно одной пустой строкой), а во втором случае необходимо вывести лишь общее количество различных полимино, содержащих N клеток.
| Пример входных данных: | Пример выходных данных: |
| 3 | *** | ** * 2 |