Муниципальный этап Всероссийской олимпиады школьников
По информатике в 2009-2010 учебном году
Класс
Задача 1. Ребус (20 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя придумал замечательный ребус:
ABA+ABA=BCB
Суть ребуса состоит в следующем: вместо букв нужно подставить цифры: вместо одинаковых букв подставляются одинаковые цифры, одна и та же цифра может быть использована несколько раз, для замены букв.
Теперь Пете необходимо решить этот ребус. Либо указать, что ребус не имеет решения.
Задача
Определить, имеет ли решение ребус, придуманный Петей.
( Нулевое решение (когда вместо всех букв подставляются нули) недопустимо).
Входные данные
Три строки, в каждой из которых записано по одному слову, состоящему из заглавных букв латинского алфавита. Длина каждой строки не превышает 4 символа.
Первая (1), вторая (2) и третья (3) строка задают ребус (1)+(2)=(3).
Выходные данные
Строка `YES` (без кавычек) если ребус имеет решение, или строка `NO` в противном случае.
Пример входных данных
ABA
ABA
BCB
Пример выходных данных
YES
--------------------------------------------------------------------------------
Задача 2. Максимальная подстрока (20 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя записал две строки. Теперь он хочет найти третью строку, чтобы она получалась из первых двух вычеркиванием нескольких символов.
Например:
Для строк RAAARUMBAAAA и AARUMCAAC. Петя нашёл строку: AARUMAA.
Поскольку задача показалась Пете очень простой, он решил её усложнить. Теперь он хочет не просто найти третью строку, а чтобы она была максимальной длины.
Задача
Найдите максимальную подстроку по двум заданным строкам.
Известно, что такая строка находится однозначно (то есть нет нескольких вариантов с одинаковой длиной).
Входные данные
В первой строке - первая строка, во второй - вторая. Строки состоят из заглавных букв латинского алфавита. Длина каждой строки не превышает 255 символов.
Выходные данные
Вывести максимальную (по длине) строку, которая является подстрокой введённых строк.
Пример входных данных
RAAARUMBAAAA
AARUMCAAC
Пример выходных данных
AARUMAA
--------------------------------------------------------------------------------
Задача 3. Простые числа (10 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя просто обожает различные системы счисления. Недавно Петя узнал понятие `простое число`. Более того, Петя научился определять - является ли число простым во всех популярных системах счисления (двоичной, восьмеричной, десятичной, шестнадцатеричной).
Поскольку Петя не уверен в ответе, помогите ему сделать проверку.
Задача
Определить, является ли введённое число простым в двоичной, восьмеричной, десятичной или шестнадцатеричной системах счисления. Если заданное число не может являться числом в какой-либо из систем счисления (например, число 763 не может быть числом двоичной системы счисления), то в этой системе счисления проверку на простоту не проводить.
Входные данные
Одно число, состоящее из цифр 0 – 9, A - F. Количество цифр числа не превышает 6.
Выходные данные
Вывести систему счисления (вывести число `2`, `4`, `8`, `10` или `16`), в которой заданное число является простым. Если таких систем несколько - вывести систему с наименьшим основанием. Если число составное во всех системах счисления - выдать строку `NO` без кавычек.
Пример входных данных
Пример выходных данных
Пояснение: число 11111 в двоичной системе счисления соответствует числу 31 в десятичной, а следовательно - является простым.
--------------------------------------------------------------------------------
Задача 4. Приграничная торговля (30 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя уже давно выдумал страну Придумляндию. Страна долгое время была разделена на отдельные государства, пока Петя не подумал: почему бы разным государствам не торговать между собой через приграничные города. Для этого достаточно построить в каждом приграничном городе таможенный пункт, а также построить несколько дорог между приграничными городами разных государств.
Сказано - сделано. Через месяц на улицах городов появились таможни, а новые дороги связали некогда изолированные государства. Но вот беда, оказалось, что города могут торговать только парами, то есть один город может торговать только с одним, другим городом из другого государства, даже если он связан дорогами со многими другими городами. При этом таможенные пункты обоих городов будут нагружены настолько, что сделают торговлю этих городов с какими либо другими невозможной.
Пример (изначальные дороги между приграничными государствами и загруженные торговые пути после начала торговли (выделены жирным)):
Задача
Найти максимально возможное количество загруженных торговых путей между двумя государствами.
Входные данные
В первой строке три целых числа N, M, K (0<N,M,K<=100) - количество городов в первом государстве, количество городов во втором государстве и общее количество дорог соответственно. В следующих K строках идут пары чисел X, Y (0<X<=N, 0<Y<=M) задающих дорогу между X-м городом первого государства и Y-м городом второго государства. Существует не более одной дороги, напрямую соединяющей 2 города.
Выходные данные
Вывести максимально возможное количество загруженных торговых путей между двумя государствами.
Пример входных данных
4 2 5
1 1
2 1
3 1
3 2
4 2
Пример выходных данных
--------------------------------------------------------------------------------
Задача 5. Круг и треугольник (20 б.)