Муниципальный этап Всероссийской олимпиады школьников
По информатике в 2009-2010 учебном году
Класс
Задача 1. Диапазон (10 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Мальчик Петя каждый день производил замеры температуры на улице. Теперь он хочет определить как сильно колебалась температура на всём протяжении его эксперимента. Помогите ему в решении задачи.
Задача
По заданной последовательности чисел найти разницу между максимальным и минимальным её элементом
Входные данные
В первой строке одно целое число N (0<N<=100). Далее следуют N строк (элементы последовательности), каждая из которых содержит по одному целому числу в диапазоне от 0 до 100 включительно.
Выходные данные
Одна строка - разница между максимальным и минимальным элементами последовательности.
Пример входных данных
Пример выходных данных
--------------------------------------------------------------------------------
Задача 2. Выход из лабиринта (30 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Исследование лабиринта - очень опасное занятие. Можно зайти в лабиринт и ходить по нему безконечно, так и не найдя выход обратно. Хорошо что у Пети есть карта лабиринта и с вашей помощью он сможет сразу определить, существует выход из лабиринта или нет.
Задача
По заданной карте прямоугольного лабиринта определить, есть ли из него выход. Карта задаётся прямоугольником вида:
#.####
#....#
###.##
#...##
#.##X#
#....#
######
Где символ ` # ` обозначает стену, `. ` - свободное пространство (по которому можно перемещаться). Символом ` X ` (заглавная латинская `икс`) обозначается клетка, в которой участник начинает своё путешествие по лабиринту. Передвигаться по лабиринту можно только по клеткам обозначенным `. ` (по свободному пространству) в горизонтальном или вертикальном направлении. Для того, чтобы выйти из лабиринта достаточно дойти до свободной клетки, расположенной на границе лабиринта. Например, так можно выйти из лабиринта, приведённого в примере:
#.####
#....#
###.##
#...##
#.##X#
#....#
######
Входные данные
В первой строке даны 2 целых числа N и M (3<N,M<=100). Следующие M строк состоят из N символов и задают карту лабиринта. В карте лабиринта ровно одна клетка с пометкой `X`.
Выходные данные
Строка `YES` (без кавычек) если можно выйти из лабиринта, или строка `NO` если из лабиринта выйти нельзя.
Пример входных данных
6 7
#.####
#....#
###.##
#...##
#.##X#
#....#
######
Пример выходных данных
YES
--------------------------------------------------------------------------------
Задача 3. Двоичный код (20 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Петя изучает системы счисления. Он с лёгкостью проводит вычисления в различных системах счисления: сначала переводит числа в десятичную систему счисления, затем производит вычисления, а после, переводит результат вычисления обратно в исходную систему счисления. Но одну задачу Петя так и не смог решить. Помогите ему.
Задача
Перевести число из двоичной системы счисления в 16-тиричную.
Входные данные
В первой и единственной строке - число в двоичной системе счисления (не более 250 цифр) без ведущих нулей.
Выходные данные
Вывести то же число, но в 16-тиричной системе счисления.
Пример входных данных
Пример выходных данных
7D9
--------------------------------------------------------------------------------
Задача 4. Города и государства (30 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
На прошлых выходных Петя придумал страну Придумляндию. Она состоит из нескольких городов, соединённых дорогами. Причём всю страну можно разделить на маленькие государства, разделённые по простому принципу: любые два города одного государства соединены дорогами (которая, возможно проходит через другие города этого государства).
Петя быстро зарисовал карту городов и дорог Придумляндии. Помогите ему подсчитать количество государств выдуманного мира.
Например:
содержит 3 государства.
Задача
Зная общее количество городов Придумляндии и схему дорог, соединяющих эти города, вычислить количество государств.
Входные данные
В первой строке два целых числа N и M (0<N, M<=100). N - количество городов Придумляндии (города пронумерованы цифрами 1,2,...,N соответственно). Далее следуют M строк, состоящих из пары целых чисел, разделённых пробелами - задающих дорогу, соединяющих соответствующую пару городов.
Выходные данные
Одно целое число - количество государств в Придумляндии.
Пример входных данных
9 7
1 2
1 3
2 4
3 4
4 5
6 7
7 8
Пример выходных данных
--------------------------------------------------------------------------------
Задача 5. Шар и точка (10 б.)
Ограничение по времени: 1 сек.
Ограничение по памяти: 1 Мб.
Описание
Выдумщик Петя один раз задумался над одной насущной проблемой: как определить, находится ли точка внутри шара? Поскольку Петя уже знает, что именно вы являетесь экспертами по решению сложных задач, он решил сразу же обратиться к вам за помощью.
Задача
Зная координаты точки и координаты центра шара и его радиус, определить, лежит ли точка внутри шара. Точка не лежит внутри шара, если расстояние от неё до центра шара больше либо равно радиусу шара.
Входные данные
В первой строке 3 целых числа - координаты точки. Во второй строке 4 целых числа - координаты центра шара и его радиус. (Все числа из диапазона от 0 до 100 включительно).
Выходные данные
Строка `YES` (без кавычек) если точка лежит внутри шара, или строка `NO` в противном случае.
Пример входных данных
1 1 1
0 0 0 3
Пример выходных данных
YES
Пример входных данных (2)
1 1 1
0 0 0 1