Инструменты пользователя

Инструменты сайта


подготовка_к_олимпиаде._тур_5

Это старая версия документа.


1. Шарики

В разных частях парка «Страна чудес Гудвина» стоят клоуны и раздают детям воздушные шары. У каждого клона шары своего цвета. Клоун дает ребенку только один шар и только один раз, но можно взять несколько шариков разного цвета у нескольких клоунов. Собирание шариков является своеобразным аттракционом, так как парк настолько большой, что не каждый ребенок может найти всех клоунов, чтобы получить воздушные шары всех возможных цветов. Известно, сколько пришло в парк детей и сколько шариков раздал каждый клоун. Нужно определить количество детей, собравших шарики всех цветов.

В первой строке ввода содержатся два целых числа – количество детей N (1 ≤ N ≤ 100), пришедших в парк, и количество клоунов K (1 ≤ K ≤ 100). Во второй строке K целых чисел в диапазоне от 0 до N – количество шариков, розданных клоунами.

Вывести два целых числа, разделенных пробелом – минимальное и максимальное возможное количество детей, собравших шарики всех цветов.

Пример вводаПример вывода
10 2
9 9
8 9

2. Список аттракционов

В парке развлечений «Страна чудес Гудвина» много замечательных аттракционов. Учительница, которая возила детей в парк, решила выяснить насколько их много, и опросила детей, в каких аттракционах они были. Результаты опроса она записала, обозначая каждый названный аттракцион одной из букв латинского алфавита. Некоторые аттракционы дети назвали несколько раз, а про какие-то они, возможно, забыли, но учительнице достаточно определить, сколько различных аттракционов среди названных.

Напишите программу, которая анализирует результаты опроса и определяет количество аттракционов в парке. В первой строке ввода содержится одна строка длиной от 1 до 250 символов, состоящая из прописных латинских букв.

Вывести одно целое число – количество аттракционов в парке по результатам опроса.

Пример вводаПример вывода
ABRACADABRA5

3. Арена

В «Стране чудес Гудвина» есть цирк-шапито, где показывают представление с дрессированными животными. Перед номером с хищными животными на круглую арену устанавливают клетку в форме многоугольника. Для безопасности зрителей после установки клетки необходимо определить, насколько близко хищник в клетке может приблизиться к краю арены.

Напишите программу, которая вычисляет минимальное расстояние от края арены до клетки. В первой строке ввода содержится два целых числа R (10 ≤ R ≤ 10000) и N (3 ≤ N ≤ 50) – радиус арены и количество вершин в многоугольнике, задающим клетку. Далее следует N строк, в каждой строке содержатся два целых числа, разделенных пробелом – координаты вершин многоугольника. Вершины перечисляются в порядке обхода по или против часовой стрелки. Центр координат соответствует центру арены. Многоугольник полностью находится внутри арены и может быть невыпуклым.

Вывести одно вещественное число – минимальное расстояние от края арены до клетки с точностью 10−4.

Пример вводаПример вывода
21 4
0 10
10 0
0 -10
-10 0
11.0000

4. Поиск детей

Родители отправили детей в «Страну чудес Гудвина», а сами отправились в кафе у входа пить кофе. Дети посмотрели на указатели у входа в парк, выбрали один из аттракционов и отправились в него. Выйдя из аттракциона, они посмотрели на указатели рядом с выходом и снова выбрали один из аттракционов. И так далее. Дети делают выбор совершенно случайно и могут снова посещать те аттракционы, где уже бывали. На каждый аттракцион дети тратят 10 минут. Временем на перемещение между аттракционами можно пренебречь. Выпив несколько чашек кофе, родители решили найти детей. Известно, что родители выпивают чашку кофе за 10 минут. Известно, какие указатели размещены у входа в парк и у выхода каждого из аттракционов. Напишите программу, которая поможет родителям быстрее найти детей, определив список аттракционов, где дети могут находиться.

В первой строке ввода содержатся два целых числа, разделенных пробелом – количество аттракционов в парке N (1 ≤ N ≤ 100) и количество выпитых чашек кофе K (1 ≤ K ≤ 100). Далее следует строка, содержащая сначала одно целое число m (1 ≤ m ≤ N) – количество указателей у входа в парк, затем m целых чисел в диапазоне от 1 до N – номера аттракционов на указателях. Далее следует N строк, содержащих аналогичную информацию об указателях у выхода каждого аттракциона.

В первой строке вывести в порядке возрастания номера аттракционов, где могут находиться дети.

Пример вводаПример вывода
5 2
4 1 2 3 4
1 2
1 3
1 4
1 5
1 1
1 3 4 5
/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/attic/подготовка_к_олимпиаде._тур_5.1382986381.txt.gz · Последние изменения: 2013/10/28 22:53 — Пронин Роман