из 3
Текущий вид
II (муниципальный) этап Всероссийской олимпиады школьников
20
1
2
/201
3
уч. год. Новосибирская область
Предмет
Кл
асс
Дата
Время начала
Время окончания
Информатика
7
-
11
2
2
.11.201
2
10
:00
1
5
:00
Максимальное кол
ичест
во баллов:
Лист
из
Для всех задач:
Имя входного файла:
input
.
txt
Имя выходного файла:
output
.
txt
Ограничение по времени:
1 секунда на тест
Ограничение по памяти:
256 Мб
Задача 1.
Ч
ёрный квадрат
Имеется
квадрат
со стороной 4000,
закрашенный в
черн
ый
цвет
.
Одна из вершин квадрата
расположена в начале координат.
О
си О
X
и
OY
направлены вдоль его сторон.
Требуе
т
ся
обрабатывать запросы следующего вида: выбрать
внутри квадрата
прямоугольник с
параллельными
осям координат
сторонами и закрасить его белым
цветом
.
В
качестве ответа
на
запрос следует вывести площадь той части
квадрата
, цвет которой изменится после такого
закрашивания.
Входные данные
В
первой строке входного файла содержится количество запросов
N
, не превосходящее 100.
Каждая из следующих
N
строк содержит запрос, представленный в виде че
т
ырёх целых
чисел
x
1
,
y
1
,
x
2
,
y
2
,
лежащих в пределах от 0 до 4000,
которые определяют координаты д
вух
противоположных углов закрашиваемого прямоугольника
.
Выходные данные
Для каждого запроса
в
выходной фай
л
следует вывести строку, содержащую одно целое
число
ответ на этот запрос.
Примеры
input.txt
output.txt
1
2 0 1 2
2
4
3 3 2 2
2 2 4 4
3 5 2 6
1 3 5 7
1
3
1
13
Задача
2
.
Четыр
ё
хугольник
Дан выпуклый четырехугольник.
Найти радиус наибольше
го
круга, который можно
по
местить внутри четырехугольника, и
радиус наименьшего,
в
который
помещается данный четырехугольник
.
Входные данные
Входно
й
файл
состоит
из четырех строк.
В
каждой
строке
записаны
через пробел
по два
целых числа
координаты
вершин четырёхугольника в порядке обхода по часовой стрелке.
Все
числа по модулю не превосходят
10
4
.
Выходные данные
В первую строк
у выходного файла необходимо выдать одно
вещественное
число
радиус
максимального
круга,
кот
о
рый поме
щае
тся внутрь четырехугольника
, во вторую строку
радиус
минимального
круга, в который помещается четырехугольник
.
Ч
исла выдавать с точностью
до
10
5
.
Примеры
input.txt
output.txt
0 0
0 2
2 2
2 0
1
1
.
41421
II (муниципальный) этап Всероссийской олимпиады школьников
20
1
2
/201
3
уч. год. Новосибирская область
Предмет
Кл
асс
Дата
Время начала
Время окончания
Информатика
7
-
11
2
2
.11.201
2
10
:00
1
5
:00
Максимальное кол
ичест
во баллов:
Лист
из
Задача
3
.
Шоколада, пожалуйста!
Директор сети супермаркетов
решил установить автоматы для продажи шоколадок.
Стоимость шоколадки в автомате предполагается установить равной пяти рублям. Автоматы
будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда клиенту
надо выдавать сдачу
с десятирублево
й
монет
ы
или 10
-
, 50
-
или 100
-
рублёв
ой
купюр
ы
, автомат
выдаёт сдачу пятирублёвыми монетами
.
Е
сли же клиент бросил в автомат пятирублёвую монету,
то автомат её сохраняет и может использовать для сдачи следующим кли
ентам.
Для того
чтобы обеспечить возможность выдачи сдачи всем покупателям, может
потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас
в супермаркетах проходят испытания с целью определ
ения
минимально
го
количеств
а
мо
нет,
которые надо загрузить в автомат в начале рабочего дня. Вам дан протокол одного из таких
испытаний: известен порядок, в котором клиенты оплачивали свои покупки различными монетами
и купюрами.
Помогите определить
директору
, какое минимальное количест
во пятирублёвых
монет должно
находиться в автомате
перед началом рабочего дня
, чтобы всем клиентам хватило
сдачи.
Входные да
нные
В первой строке входного файла находится одно натуральное число
N
количество
покупок в автомате, которые были совершены в ходе и
спытани
й
(1
N
50000). Во второй строке
находятся
N
натуральных чисел
, записанных через пробел
, каждое из которых равно номиналу
монеты или купюры, которую
использовал очередной покупатель для оплаты
.
Каждый
номинал
может принимать одно из четырёх значений: 5, 10, 50 или 100.
Выходные данные
В выходной файл
необходимо вывести
одно
целое
число
минимальное количество
пятирублёвых монет, которые надо
было
загрузить в автомат
в начале рабочего дня
, чтобы всем
покупателям хватило сдачи.
Пример
ы
input.txt
output.txt
3
5 5 10
0
4
50 5 5 5
9
II (муниципальный) этап Всероссийской олимпиады школьников
20
1
2
/201
3
уч. год. Новосибирская область
Предмет
Кл
асс
Дата
Время начала
Время окончания
Информатика
7
-
11
2
2
.11.201
2
10
:00
1
5
:00
Максимальное кол
ичест
во баллов:
Лист
из
Задача 4.
Тарификация
В микрорайоне А города
Нска проложены кабели между некоторыми домами.
Интернет
-
провайдер хочет
установить тариф предоставления услуг Интернета жителям
этого
микрорайона.
Тариф начис
ляется на группу домов.
Д
ома объединяются в группу, если между любыми
домами этой группы существует
соединение по проводам через другие дома
той
же
группы или
напрямую.
Дома в группы могут объединяться по
-
разному.
Кабели, участвующие в обеспечении
связи между домами, счита
ются принадлежащими этой групп
е.
В
еличина тарифа определяется как
отношение суммы длин кабелей,
принадлежащих
групп
е
,
к
количеству домов, включенных в нее.
Провайдер хочет определить миним
альный тариф
из
всех возможных тарифов, которые
можно начислить на все возможные группы.
Входные данные
Первая строка
входного файла
содержит
два
цел
ых
числ
а
, записанных через пробел,
N
и
М
количество
домов в микрорайоне
и количество кабелей, соединяющих их
(1 ≤
N
≤ 10
0,
1
M
10
0
0
)
.
Следующие
M
строк
описывают
проложенные
кабели
.
К
аждая строка содержит по три
натуральных
числа, п
ервые два из которых
это номера домов, между котор
ы
ми про
ложен
кабель, а третье
его длина.
Длина
не превосходит 100. Дома нумеруются числ
ами от 1 до
N
.
Выходные данны
е
В выходной файл необходимо вывести одно вещественное число
с точностью до
10
2
минимальный тариф.
Примеры
input.txt
output.txt
3 3
1 2 1
2 3 2
1 3 3
0.5
Задача 5.
Числомания
Пете нравится изучать с
войства чисел.
В последнее время
он увлекся
десятичными
числами
, в которых нет одинаковых рядом стоящих цифр.
Он их называет красивыми.
Петя
хочет посчитать, сколько существуе
т красивых чисел
длины
N
,
полученных
умножением
натурального
числа
K
на какое
-
то другое на
туральное число.
Входные данные
Входно
й
файл
содержит
два
натуральных
числа
,
записанных через пробел,
N
и
K
(
1
N
18
,
1
K
10
00
).
Выходные данные
В
единственной
строке
выходного
файла должно содержаться одно целое число
ко
личество всех
красивых чисел
, удовлетворяющих условию
.
Пример
input
.
txt
output
.
txt
2 1
8
1
3 133
3