Муниципальный этап Всероссийской олимпиады школьников
По информатике в 2009-2010 учебном году
Класс
Задача 1. Фундамент (20 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Довольные жители страны Придумляндии, которую выдумал Петя, захотели воздвигнуть в честь своего создателя (то есть Пети) памятник. Памятник было решено установить в столичном парке на максимально возможную площадку квадратной формы. Поскольку придумляндцы очень любят природу, то они не могут позволить себе вырубить хотя бы одно дерево в парке, поэтому выбор места для будущего монумента стал по настоящему сложной задачей.
Задача
По карте парка, с указанным размещением деревьев, определить максимальную площадь квадратного фундамента для памятника, который может быть размещён на территории парка, который бы сохранил все находящиеся в парке деревья.
Входные данные
В первой строке даны 2 целых числа N и M (3<N,M<=100). Следующие M строк состоят из N символов и задают карту парка. Символом `0` (ноль) обозначается свободный для строительства участок парка, а символом `1` - участок, на котором растёт дерево.
Выходные данные
Одно число - максимальная площадь квадратного фундамента, который можно установить в парке, исходя из условий задачи. Площадь выдать в квадратных метрах. Размер каждой ячейки карты - 1 метр в длину и 1 метр в ширину.
Пример входных данных
5 5
Пример выходных данных
--------------------------------------------------------------------------------
Задача 2. Телефонные линии (10 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
В стране Придумляндия, которую выдумал Петя, есть очень хитрая система телефонной связи. Вместо централизованных линий, соединяющих абонентов с центром связи, используется следующая схема: каждого абонента соединяют со всеми другими при помощи отдельной линии связи. А при подключении нового абонента - его соединяют с каждым уже существующим отдельной линией связи. Петя даже не может представить, сколько придётся проложить проводов для некоторого количества абонентов. Помогите ему с вычислениями.
Задача
Определить количество линий связи по заданному количеству абонентов.
Входные данные
Одно целое число N (1<N<=1000) - количество абонентов.
Выходные данные
Одно целое число - количество линий связи.
Пример входных данных
Пример выходных данных
--------------------------------------------------------------------------------
Задача 3. Перемножатель (20 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя настолько увлёкся системами счисления, что решил, что теперь все вычисления будет производить только в 16-тиричной системе счисления. Единственное, что он пока не освоил в совершенстве - перемножение чисел. Помогите Пете.
Задача
Написать программу, которая перемножает числа в 16-тиричной системе счисления.
Входные данные
В первой строке - X - целое число в 16-тиричной системе счисления (0<=X<=FFFFF). Во второй строке - Y - целое число в 16-тиричной системе счисления (0<=X<=FFFFF).
Выходные данные
Результат перемножения X и Y, также представленный в 16-тиричной системе счисления.
Пример входных данных
AB
CD
Пример выходных данных
88EF
--------------------------------------------------------------------------------
Задача 4. Экономная экономика (30 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Государство в Придумляндии представляет собой некоторое количество городов, соединённых между собой дорогами, так, чтобы из каждого города можно было попасть в другой, пройдя по некоторому количеству дорог.
Недавно король издал указ, в котором предложил закрыть часть дорог, но при этом оставив возможность добраться из каждого города в каждый. Поскольку каждая дорога обладает такой характеристикой как пропускная способность, король требует закрыть максимальное количество дорог, но при этом, чтобы сумма пропускных способностей оставшихся дорог была максимальной.
Задача
По заданной схеме дорог определить сумму пропускных способностей дорог, их количество после того, как в соответствии с указом будет закрыта часть дорог. ( Между двумя городами может быть не более одной дороги, которая непосредственно их соединяет).
Входные данные
В первой строке два целых числа N и M (0<N, M<=100). N - количество городов Придумляндии (города пронумерованы цифрами 1,2,...,N соответственно). Далее следуют M строк, состоящих из тройки целых чисел, разделённых пробелами - задающих пару городов (которые соединяет эта дорога) и пропускную способность дороги соответственно. Известно, что входные данные задают сеть дорог, позволяющую добраться из любого города в любой другой (возможно пройдя через некоторое количество промежуточных городов).
Выходные данные
В первой строке - количество дорог после введения указа в силу.
Во второй строке - суммарная пропускная способность дорог после введения указа в силу.
Пример входных данных (см. рисунок)
4 5
1 2 1
1 3 7
2 3 3
1 4 4
3 4 2
Пример выходных данных
--------------------------------------------------------------------------------
Задача 5. Квадрат и точка (20 б.)