VII Сетевая районная олимпиада Республики Карелия по информатике. 16 декабря 2012 г. - Условия

A. Лес

Имя входного файла:	forest.in
Имя выходного файла:	forest.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

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

Вам предложена карта (вид на лес сверху), на которой изображены все деревья. Зная координаты деревьев, требуется построить максимально широкую горизонтальную полосу ненулевой ширины с границами, параллельными оси OX, проходящую через лес таким образом, чтобы и сверху, и снизу от неё находилось хотя бы одно дерево. При этом вычищенная дорога не должна содержать внутри себя деревьев, но может касаться их своей границей.

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

Формат входного файла

В первой строке файла содержится натуральное число n – число деревьев в лесу (1 ≤ n ≤ 100000). В следующих n строках содержатся координаты деревьев – целые числа x_i, y_i (0 ≤ x_i, y_i ≤ 10⁸).

Формат выходного файла

Выведите максимальную ширину полосы, либо -1, если вам не удалось определить дорогу, удовлетворяющую описанным выше требованиям.

Пример:

forest.in	forest.out
3 5 5 3 6 6 6	1
4 6 4 10 6 8 0 6 6	4

Примечание:

Решения, работающие при n ≤ 10000 будут оцениваться из 70 баллов.

Источник: VII сетевая районная олимпиада Республики Карелия по информатике, XXIV Городская олимпиада школьников по информатике

Обсудить Отправить решение

B. Парковка

Имя входного файла:	parking.in
Имя выходного файла:	parking.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

В центре города П. построили большой и красивый торговый центр. Его парковка состоит из N уровней. На i-м уровне есть a_i парковочных мест. При въезде на парковку водителю выдаётся талон, в котором указан минимальный номер уровня, на котором есть свободные места. Получив подобный талон, водитель отправляется на указанный уровень и занимает там место. По окончании визита в торговый центр, покупатель уезжает, освобождая парковочное место.

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

Формат входного файла

В первой строке входного файла находится единственное число N – количество уровней на парковке (1 ≤ N ≤ 10⁵). Во второй строке находится N чисел a_i – количество парковочных мест на каждом уровне (1 ≤ a_i ≤ 1000).

В третьей строке входного файла находится число M – количество событий, произошедших на парковке за день (1 ≤ M ≤ 10⁵). В четвёртой строке находится M чисел b_i, описывающих события. Если b_i = 0, значит на парковку приехал очередной автомобиль. Если же b_i = x > 0, значит, с уровня номер x уехал один из автомобилей, расположенных там. Конечно, во втором случае гарантируется, что x ≤ N и что в этот момент на уровне x находится хотя бы один автомобиль.

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

Формат выходного файла

Выведите столько чисел, сколько раз событие <<приехал автомобиль>> встретилось во входном файле. Для каждого такого события выведите единственное число – номер на талоне, выдаваемом водителю этого автомобиля. Напоминаем, что этот номер должен быть равен минимальному номеру уровня, на котором есть свободные парковочные места.

Пример:

parking.in	parking.out
4 2 2 2 2 6 0 0 0 0 1 0	1 1 2 2 1
5 1 1 1 1 1 11 0 0 0 0 0 5 1 3 0 0 0	1 2 3 4 5 1 3 5

Решения, работающие при 1 ≤ N, M ≤ 1000 будут оцениваться из 60 баллов.

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

C. Арифметическая прогрессия

Имя входного файла:	progression.in
Имя выходного файла:	progression.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

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

a₁, a₂, …, a_n – элементы прогрессии,
a_i - a_i-1 = d для всех 1 < i ≤ n,
d, a₁, a₂, …, a_n – целые числа.
d называется разностью арифметической прогрессии.

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

Помогите Васе посчитать число способов выбрать разность целочисленной арифметической прогрессии, в которой известны только два её члена.

Формат входного файла

В единственной строке файла содержатся два целых числа a, b (1 ≤ a, b ≤ 10⁹).

Формат выходного файла

Выведите число способов выбрать разность прогрессии.

Пример:

progression.in	progression.out
2 4	2
1 5	3

В первом примере на доске изначально могли быть написаны прогрессии с разностями 1 и 2. Например, это могла быть последовательность 1, 2, 3, 4, 5, в которой Вася стёр 1, 3, 5 или 0, 2, 4, 6, в которой, удалили 0 и 6. Следует отметить, что разность -2 использована быть не может, так как в оставшейся последовательности известен относительный порядок чисел, то есть 2 идет в прогрессии раньше чем 4.

Во втором примере разностью прогрессии могло быть число 1, 2 или 4.

Источник: VII сетевая районная олимпиада Республики Карелия по информатике

Обсудить Отправить решение

D. Поиск строки

Имя входного файла:	string.in
Имя выходного файла:	string.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

Коротким декабрьским субботним днём сидел прогульщик Вася дома и скучал, так как на улице было много снега, а его друзья еще не вернулись из школ. "Нет, никаких игр за компьютером, пусть глаза отдыхают" — заботилась о его здоровье мама.

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

Формат входного файла

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

Формат выходного файла

В единственной строке файла выведите "YES", если из первой строки можно составить вторую, и – "NO" иначе.

Пример:

string.in	string.out
abacaba bcba	YES
abacaba dabaduba	NO

Источник: VII сетевая районная олимпиада Республики Карелия по информатике

Обсудить Отправить решение

E. Следы

Имя входного файла:	trails.in
Имя выходного файла:	trails.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

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

Петя решил не портить такую красивую картину и кататься аккуратно по следам. Он может съезжать вниз на лыжах, используя два соседних следа, или на снегокате, используя три подряд идущих следа, поскольку у его снегоката три полоза.

Например, если на горке всего четыре следа, то Петя может съехать вниз на снегокате либо, используя следы 1, 2, 3, либо используя следы 2, 3, 4. На лыжах в таком случае он сможет использовать либо следы 1, 2, либо 2, 3, либо 3, 4.

Петя покатался некоторое время, потом окончательно вымотался, сел на снегокат и задумался о том, а сколько разных вариантов спуска с горки у него есть. Помогите ему найти это количество. Два варианта считаются разными, если они используют разные наборы следов. Например варианты 1, 2 и 1, 2, 3 – разные.

Формат входного файла

В первой строке входного файла находится единственное число N – количество следов на горке (1 ≤ N ≤ 1000).

Формат выходного файла

Выведите единственное число – количество различных вариантов спуска с горки, которые есть у Пети.

Пример:

trails.in	trails.out
5	7
6	9

В первом примере у Пети есть следующие варианты: (1, 2), (2, 3), (3, 4), (4, 5) для спуска на лыжах и (1, 2, 3), (2, 3, 4), (3, 4, 5) для спуска на снегокате. Всего семь вариантов.