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

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

HotLog

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

Задачи олимпиады "Тренировка №10 для опытных программистов"

Задача A. Кастинг

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

В театре работает n актеров. Известно, что среди них a – высоких, b – голубоглазых и с – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам n, a, b и с определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

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

Первая строка входного файла INPUT.TXT содержит одно число, которое задает: минимальное или максимальное количество актеров необходимо найти. Это число может принимать следующие значения:

1, если в данном тесте требуется определить минимальное количество актеров;

2, если в данном тесте требуется определить максимальное количество актеров.

Вторая строка входного файла содержит разделенные пробелами четыре целых числа: n, a, b, с (1 ≤ n ≤ 10 000, 0 ≤ a ≤ n, 0 ≤ b ≤ n, 0 ≤ c ≤ n).

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

В выходной файл OUTPUT.TXT выведите одно число – минимальное или максимальное (в зависимости от входных данных) количество актеров, которые могут претендовать на главную роль в новом спектакле.

Примеры

INPUT.TXTOUTPUT.TXT
12
5 3 4 5
3
21
5 3 4 5
2

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

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

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


Задача B. Призы

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

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n/3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

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

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: n – общее количество призов и k – количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n/3). Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба (1 ≤ ai ≤ 109).

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

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

Пример

INPUT.TXTOUTPUT.TXT
110 2
1 2 4 5 2 4 2 2 1 6
7

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

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.


Задача C. Форматирование текста

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

Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: «,», «.», «?», «!», «-», «:» и «’» (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из заглавных и прописных букв английского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк.

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

Требуется написать программу, которая по заданным числам w и b и заданному тексту выводит текст, отформатированный описанным выше образом.

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

Первая строка входного файла INPUT.TXT содержит два целых числа: w и b (5 ≤ w ≤ 100, 1 ≤ b ≤ 8, b < w). Затем следует одна или более строк, содержащих заданный текст. Длина слова в тексте вместе со следующими за ними знаками препинания не превышает w, а длина первого слова любого абзаца вместе со следующими за ним знаками препинания не превышает (w – b). Текст содержит хотя бы одну букву. Перед первой буквой каждого абзаца знаков препинания нет.

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

Выходной файл OUTPUT.TXT должен содержать заданный текст, отформатированный в соответствии с приведенными в условии задачи правилами. Размер входного файла не превышает 100 Кбайт. Длина каждой строки во входном файле не превышает 250.

Пример

INPUT.TXTOUTPUT.TXT
1
20 4
Yesterday, 
All my troubles seemed so far away, 
Now it looks as though they're here to stay, 
Oh, I believe in yesterday. 

Suddenly, 
I'm not half the man I used to be, 
There's a shadow hanging over me, 
Oh, yesterday  came suddenly...
    Yesterday, All
my troubles seemed
so far away, Now it
looks as though
they' re here to
stay, Oh, I believe
in yesterday. 
    Suddenly, I' m
not half the man I
used to be, There' s
a shadow hanging
over me, Oh,
yesterday came
suddenly...

Задача D. Поиск в сети Меганет

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

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

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв английского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных английских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e».

Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S», где S – имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ФильтрПримеры подходящих адресов
ab.c/d/eab.c/d/e
*.aa; ax.a; efg.a
*.a/b/ca/b/c; ax.a/b/c; efg.a/b/c
x.yz/a/*x.yz/a; x.yz/a/b/c; x.yz/a/xyz
*.a/*a; x.a; e.fg.a; a/b/c; x.a/ddd/c; e.fg.a/b/c/g/haha/i
*.a/b/c/*a/b/c; x.a/b/c; e.fg.a/b/c; a/b/c/xxx; e.fg.a/b/c/d/e/f

Требуется написать программу, которая по заданному набору фильтров и списку адресов определяет для каждого адреса, какому числу фильтров соответствует этот адрес.

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество фильтров (1 ≤ n ≤ 50 000). Последующие n строк содержат фильтры, по одному на строке. Каждый фильтр удовлетворяет ограничениям, описанным выше. Следующая строка содержит одно целое число k – количество адресов, которые необходимо проверить на соответствие фильтрам (1 ≤ k ≤ 50 000). Последующие k строк содержат адреса, по одному на строке. Каждый адрес удовлетворяет ограничениям, описанным выше. Длина каждой строки входного файла не превышает 50 символов. Общий размер входного файла не превышает 4 мегабайт.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c
0
1
0
0
24
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
Bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d
0
4
3
0
2
1

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

В первом примере в фильтрах не встречается символ «*», поэтому адрес соответствует фильтру только в случае полного совпадения.

Во втором примере следует обратить внимание на то, что фильтры могут повторяться, а также, что фильтрам вида «*./…» соответствуют также адреса, в которых часть имени сервера полностью совпадает с соответствующей частью фильтра. Аналогично фильтрам «…//*» соответствуют также адреса, в которых часть имени раздела полностью совпадает с соответствующей частью фильтра.



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