Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

[Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Тренировка №6 для подготовки к региональному этапу"

Задача A. Миша и негатив

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив бинарного черно-белого изображения.

Бинарное черно-белое изображение – это прямоугольник, состоящий из пикселей, каждый из которых может быть либо черным, либо белым. Негатив такого изображения получается путем замены каждого черного пикселя на белый, а каждого белого пикселя – на черный.

Миша, как начинающий программист, написал свою программу с ошибкой, поэтому в результате ее исполнения мог получаться некорректный негатив. Для того чтобы оценить уровень несоответствия получаемого негатива исходному изображению, Миша начал тестировать свою программу.

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

Требуется написать программу, которая в качестве входных данных использует исходное бинарное черно-белое изображение и полученный Мишиной программой негатив, и на основе этого определяет количество пикселей, в которых допущена ошибка.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n, m ≤ 100) – высоту и ширину исходного изображения (в пикселях). Последующие n строк содержат описание исходного изображения. Каждая строка состоит из m символов «B» и «W». Символ «B» соответствует черному пикселю, а символ «W» – белому. Далее следует пустая строка, а после нее – описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Примеры

INPUT.TXTOUTPUT.TXT
13 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB
2
22 2
BW
BB

WW
BW
2

Задача B. Список школ

(Время: 1 сек. Память: 16 Мб Баллы: 100)

При регистрации на портале интернет-олимпиады все участники заполняют регистрационную форму, где они указывают название школы, в которой они учатся. Разные участники могут по-разному писать название школы, например, «Физико-математическая школа №18», «ФМШ №18».

Организаторам олимпиады предоставлена информация о названиях школ, которые написали регистрируемые участники олимпиады. Точно известно, что цифры в названии школы встречаются только в номере школы, а число в записи названия школы встречается ровно один раз и оно однозначно определяет номер школы. Номер школы является положительным целым числом и не может начинаться с нуля.

Требуется написать программу для сайта интернет-олимпиады, которая поможет организаторам олимпиады получить следующую информацию: количество школ и номера школ, из которых зарегистрировалось не более пяти участников.

Входные данные

Первая строка входного файла INPUT.TXT содержит одно целое число n (1 ≤ n ≤ 1000) – количество названий школ, указанных всеми участниками при регистрации.

Последующие n строк содержат названия школ, указанные участниками. Название школы содержит только заглавные и строчные буквы английского алфавита, цифры и пробелы, длина названия не превышает 100 символов.

Выходные данные

Первая строка выходного файла OUTPUT.TXT должна содержать одно число m – количество школ, от которых на олимпиаду зарегистрировалось от одного до пяти участников. Последующие m строк должны содержать только номера таких школ, при этом номера должны располагаться по одному в строке в произвольном порядке.

Пример

INPUT.TXTOUTPUT.TXT
19
Physics and Mathematics School 18
9ya shkola imeni Pushkina
Lyceum 9
PaMS 18
Gymnasium 42
School 9
Shkola nomer 9
High school 9
School N 9
2
42
18

Пояснение к примеру

Для участия в интернет-олимпиаде зарегистрировались: два ученика из школы с номером 18, один ученик из школы с номером 42 и шесть учеников из школы с номером 9. Таким образом, от 1 до 5 участников зарегистрировано от школ с номерами 18 и 42.


Задача C. Силовые поля

(Время: 2 сек. Память: 16 Мб Баллы: 100)

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером 109 × 109, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (xi , yi).

В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.

Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000) – общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.

Последующие n строк содержат по два целых числа xi , yi (1 ≤ xi, yi ≤ 109) – координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число: максимальную площадь искомого участка.

Пример

INPUT.TXTOUTPUT.TXT
15 3
3 5
2 2
2 5
4 4
5 3
9

Пояснение к примеру

На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.


Рис 1. Силовые поля в примере описания входных данных.

Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.

Задача D. Кольцевая автодорога

(Время: 1 сек. Память: 16 Мб Баллы: 100)

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой – иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от нее. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

Кольцевая автодорога

Дирекция по строительству города Флэтбурга, ответственная за постройку кольцевой автодороги, решила привлечь передовых программистов для выбора оптимального плана постройки дороги.

Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдет такой план, для которого длина дороги будет минимальной.

Входные данные

Входной файл INPUT.TXT содержит четыре строки. Каждая из них содержит по два целых числа: xi и yi – координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая – вторую, третья – третью, четвертая – четвертую. Никакие две достопримечательности не находятся в одной точке. Все числа во входном файле не превосходят 100 по абсолютной величине.

Выходные данные

В первой строке выходного файла OUTPUT.TXT требуется вывести число возможных планов постройки кольцевой автомобильной дороги. Если таких планов бесконечно много, необходимо вывести в первой строке выходного файла слово Infinity.

На второй строке требуется вывести координаты центра дороги минимальной длины и ее радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Входные данные таковы, что существует хотя бы один вариант дороги. Координаты центра и радиус дороги должны быть выведены с точностью не хуже 10-5.

Примеры

INPUT.TXTOUTPUT.TXT
10 0
0 1
1 0
2 2
7
1.5 0.5 1.14412281
20 0
0 1
1 0
1 1
Infinity
0.5 0.5 0.0


 
     
Югорский НИИ ИТ, Югорский ФМЛ