Задача 1.

Вершины и стороны N-угольника помечены натуральными числами от 1 до 2*N. Если суммы трех чисел, соответствующие каждой стороне, равны, то N-угольник называется магическим.

Задание:

Написать программу, которая:

1) для каждого натурального N формирует хотя бы один магический N-угольник;

2) для заданного N формирует возможно большее число магических N-угольников.

Задача 2.

По каналу связи передаются закодированные сообщения в виде последовательности байтов. В исходном тексте сообщения используются только прописные латинские буквы A-Z и восемь знаков (. :, + - / ? !).

Цель:

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

Задание:

Написать программу, которая:

1) обеспечивает кодирование и декодирование заданного текста сообщения с учетом только вышеупомянутых требований;

2) обеспечивает кодирование и декодирование заданного текста сообщения таким образом, чтобы наряду с названными требованиями выполнялось требование минимизации количества битов в передаваемом сообщении.

Требование к вводу-выводу:

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

Задача 3.

Вводится целое число K>=1. Бумажная полоса разбита на N клеток (K <= N <= 40). Играют двое, по очереди выбирая и зачеркивая K пустых смежных клетки. Выигрывает сделавший последний ход.

1 2 N

+-------------------- ---------+

¦ ¦ ¦ ¦ ¦...¦ ¦

+-------------------- ---------+

1)Ввести N и определить, имеет ли игрок 1 выигрышную стратегию ( т. е. может ли игрок 1 выиграть при наилучших последующих ходах игрока

2). Сообщение вида 'У игрока 1 (не) существует выигрышная стратегия'.

3)Для N определить, имеет ли игрок 1, сделав заданный первый ход, выигрышную стратегию.

4)Провести игру для N и первого хода игрока 1. За второго игрока играет программа. Ходы первого вводятся с клавиатуры. Цель второго игрока -победа. Ход задается индекcoм ячейки L (1<=L<=N-K+1). При этом вычеркиваются клетки с индексами от L до L+K-1. После каждого хода выводится текущая позиция в виде

1, 2, 3, ..., N

* *

Сверху печатается номер позиции. Зачеркнутые клетки помечаются символом '*'. В конце игры выдать сообщение 'Победа игрока 1(2)'. При вводе N и K выдать подсказывающие сообщения 'N>'и 'K>', при вводе хода - 'Ход игрока 1>'. Предусмотреть контроль корректности входных данных.

Задача 4.

Между N пунктами (N<=50) заданы дороги длиной A(i, j), где I, J-номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M=2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте.

Скорость I-ого робота может быть равна 1 или 2. Остановка роботов запрещена.

Задание:

Написать программу, которая:

1) при заданных N, M и сети дорог единичной длины (все имеющиеся A(i, j)=1) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны.

2) Выполнить те же действия, что и в п. 1, но только для различных значений A(i, j).

Примечание: В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.

Требование к вводу-выводу:

1) Все входные данные - целые неотрицательные числа;

2) при задании сети дорог должно быть указано количество дорог-K и пункты их начала и конца в виде пар (i, j).

Задача 5.

Имеется N книг и два читателя, А и В, желающих прочитать эти книги. Заданы неотрицательные целые числа A[I] и B[I] такие, что читателю А (или В) потребуется A[I] (соответственно, B[I]) часов для прочтения книги I, 1 <=I <=N. Процесс чтения начинается в момент времени 0. В любой момент времени каждый читатель не может читать более одной книги и каждую книгу не могут читать оба читателя.

Для каждого читателя порядок чтения книг не имеет значения и может быть произвольным. В процессе чтения любой книги любым читателем допускаются прерывания. Это означает, что этот процесс может быть прерван в любой целочисленный момент времени и возобновлен позднее с прерванного места. В промежутке между прерыванием и последующим возобновлением процесса чтения книги читатель может читать любую не до конца прочитанную книгу.

Задано целое число К, 2<=K <=N, и книги пронумерованы таким образом, что ни один читатель не имеет права начать читать книгу J, 2 <= J <= K, прежде чем книга J-1 не будет прочитана обоими читателями.

ТРЕБУЕТСЯ:

1. Организовать ввод исходных данных в форме:

<ввести N -->>

<ввести K -->>

<ввести:>

<A[1] -->> <B[1] -->>

<A[2] -->> <B[2] -->>

. . . . . . . . . . . . . . . . . . . . . . . . . .

<A[N] -->> <B[N] -->>

2. Вычислить наименьший момент времени Т, раньше которого все книги не могут быть прочитаны всеми читателями. Вывести вычисленное значение Т.

3. Построить расписание чтения книг каждым читателем, при котором не нарушается ни одно из перечисленных выше условий и процесс чтения всех книг завершается в момент времени Т. Расписание для каждого читателя вывести в виде:

<РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В)>

<Номер книги> <Начало> <Конец>

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .