1. “Сдвиги” (идея — из материалов методической комиссии 2000-2001 уч.г., составитель — Еремин Е.А., оппонент — Гладков В.П.). 10 баллов.
Дано целое десятичное число N (1 <= N <= 65535). Некто записал это число в двоичном формате и стал циклически сдвигать влево, т.е. брать первую цифру числа и переносить ее в конец. Например, если N = 11, то в двоичном формате оно будет представлено как 1011. После первого сдвига получится 0111, после второго — 1110, после третьего — 1101, после четвертого — исходное число 1011. Легко видеть, что максимальное значение из всех полученных таким образом чисел будет иметь число 1110, и это значение в десятичной системе равно 14.
Требуется написать программу, которая для заданного числа N определяет максимальное значение среди чисел, которые могут получаться в результате вышеописанных сдвигов.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
Входной файл INPUT.TXT содержит единственную строку с целым десятичным числом N.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно десятичное число — искомое максимальное значение.
Пример файла входных данных:
11
Пример файла выходных данных:
14
2. Последовательность (автор-составитель — Брызгалов Е.В., оппонент — Гладков В.П.). 15 баллов.
Дана последовательность целых чисел. Члены последовательности не превосходят по модулю 2 миллиардов.
Требуется написать программу, которая определит число различных членов в заданной последовательности.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 3 секунды.
Формат входных данных:
В первой строке указано N (1 <= N <= 10000) — число членов последовательности.
Далее следует N строк, каждая из которых содержит одно число — член последовательности.
Формат выходных данных:
Одна строка, содержащая число различных членов.
Пример файла входных данных:
4 13 16 13 17
Пример файла выходных данных:
3
3. Один день из жизни сервера (автор-составитель — Брызгалов Е.В., оппонент — Деменев А.Г.). 20 баллов.
Корпорация Moon производит низкоскоростные однозадачные сервера, один из которых установлен в Вашей компании. Руководство компании засомневалось в эффективности подобной системы и предложило Вам как ведущему инженеру произвести тестирование и определить задержку выполнения запросов к серверу. В течение 24 часов Вы старательно посылали запросы и создавали лог-файл, в котором фиксировалось время отправления запроса и время его выполнения на сервере. При поступлении запроса на свободный Moon-сервер он начинает выполняться, если же сервер занят (обрабатывает другой запрос), то новый запрос ожидает окончания работы (так и возникает задержка). Возможны случаи, когда в состоянии ожидания находятся несколько запросов, тогда при освобождении сервера начинает обрабатываться тот, который поступил раньше.
Требуется написать программу, которая по полученному лог-файлу определит среднюю задержку.
Примечания:
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 10 секунд.
Формат входных данных:
В первой строке содержится N (N <= 20000) — число запросов.
Далее следует N строк, каждая из которых содержит время отправления запроса на сервер и
(через пробел) время выполнения его на сервере (формат представления времени см. выше).
Запросы представлены в хронологическом порядке.
Формат выходных данных:
Среднее время задержки обработки запроса в указанном выше формате (при необходимости выполнить округление).
Пример файла входных данных:
3 00:00:00.100 00:00:01.000 00:00:00.200 00:00:01.000 12:34:00.000 00:00:00.050
Пример файла выходных данных:
00:00:00.300
4. Делители произведения (идея — из материалов методической комиссии 2000-2001 уч.г., составитель — Южаков М.А., оппонент — Брызгалов Е.В.). 25 баллов.
Задано N натуральных чисел a1, a2, …, aN (1 <= N <= 20), каждое из которых находится в интервале от 1 до 10000. Необходимо определить количество натуральных делителей произведения a1 * a2 * … * aN .
Требуется написать программу, которая вычисляет количество натуральных делителей произведения вышеназванного числа.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
Входной файл INPUT.TXT состоит из двух строк. В первой строке содержится натуральное число N.
Во второй — числа a1, a2, …, aN , записанные через пробел.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно искомое число.
Пример файла входных данных:
4 3 5 7 720
Пример файла выходных данных: (для приведённого выше входного файла)
120
5. Свинья-копилка (идея — из материалов методической комиссии 2000-2001 уч.г., составитель — Брызгалов Е.В., оппонент — Каганов И.В.). 30 баллов.
Для того чтобы начать бизнес, юный коммерсант решил накопить немного денег. С этой целью он отыскал свинью-копилку и начал собирать деньги.
Известно, что определить накопленную сумму в копилке можно, только разбив эту копилку. Однако юному коммерсанту не хотелось делать это раньше времени, то есть до тех пор, пока там не накопилась бы требуемая сумма. Избежать этого ему помог его напарник, который посоветовал, как можно оценить минимальное количество денег внутри копилки, зная её вес без монет, вес с монетами и вес монет каждого типа.
Требуется написать программу, которая определяла бы минимальную сумму денег, которая может находиться в копилке, по известным исходным данным.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 10 секунд.
Формат входных данных:
В первой строке содержатся два целых числа:
E — вес пустой копилки (1 <= E <= 10000);
F — вес копилки, заполненной монетами (1 <= E <= F <= 10000).
Вторая срока содержит целое число N (1 <= N <= 500) — количество типов монет.
Далее следует N строк описания монет различных типов. Каждая строка содержит
два целых числа — Pi и Wi (1 <= Pi <= 50000,
1 <= Wi <= 10000, 1 <= i <= N),
где Pi — достоинство монеты i-го типа, а Wi — её вес.
Формат выходных данных:
Одно целое число — значение минимальной суммы денег, которая может находится в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то выходной файл должен содержать сообщение “NO SOLUTION”.
Пример 1 файла входных данных:
10 110 2 1 1 30 50
Пример 1 файла выходных данных:
60
Пример 2 файла входных данных:
10 110 2 1 1 50 30
Пример 2 файла выходных данных:
100
Пример 3 файла входных данных:
1 6 2 10 3 20 4
Пример 3 файла выходных данных:
NO SOLUTION
© Пермский областной Оргкомитет олимпиад школьников по информатике, 2001; А.Г. Деменев