Текст районной/городской олимпиады по информатике

2011–2012 учебного года

 

 

1.      «Акция» – 100 баллов

ЗАО «Титан» выпустила первую опытную партию новых катеров. В рамках рекламной компании решено организовать водно-моторный переход Н.Новгород-Астрахань. В походе запланировано участие n (n≤100) катеров. На место сбора прибыли катера, на которых находились соответственно a1, a2, …, an участников похода (ai≤32).

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

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

Например:  

Число катеров         3

Число участников похода по катерам      1, 2, 4

Минимальное число пересадок     1  (соответствующее распределение 2, 2, 3).

 

2.      «Квадрат» – 100 баллов

На координатной плоскости задан квадрат. Одна из его диагоналей соединяет точки (0, 0) и
(1000, 1000). На периметре квадрата заданы целочисленными координатами две точки
 
A(x1, y1) и B(x2, y2). Найти длину наименьшего пути от точки A до B, если перемещение возможно только по периметру.

Ваша программа должна по введенным исходным данным сообщать единственное число, длину минимального пути от A до B по периметру.

Пример:      

         Координаты точки A            300, 0

         Координаты точки B             500, 1000

         Длина наименьшего пути     1800

 

3. «Декодирование» – 100 баллов

Агент 0013 (позывной Вася) придумал такой способ кодирования пересылаемых сообщений:

1. Определяется длина пересылаемого сообщения (например, для сообщения «Груз готов» это 10).

2. Заготавливается квадратная таблица минимального размера, но содержащая ячеек не менее чем длина сообщения (в примере это 4×4).

3. Ячейки таблицы последовательно заполняются символами сообщения слева направо сверху вниз, а оставшиеся пустыми – пробелами (смотри рисунок).

4. Кодированное сообщение  читается по направлению параллельному вспомогательной диагонали в соответствии со стрелками на рисунке. Возможные последние незначащие пробелы игнорируются. Таким образом, кодированное сообщение будет «Г˽рогу˽воз˽˽т» (для предупреждения ошибок здесь пробелы обозначены символом «˽»).

Вам необходимо составить программу раскодирования сообщений агента, содержащих до 127 символов.

Еще один пример:  

            Кодированная строка                       Пцрсеооср

                                    Сообщение                            Процессор

 

4. «Делители» – 100 баллов

Составьте программу, которая по натуральному n (n≤100) находит и сообщает число различных натуральных делителей (включая 1 и само число) числа n! (n!=1×2×3×…×n).

Например:

Число n                                  8

Число делителей                   96

 

Примечание. Для всех программ ограничение по времени прохождения одного теста — 1 секунда.