XXIV Городская олимпиада школьников г. Петрозаводска по информатике. 9-11 классы. 16 декабря 2012 - Условия

A. Лес

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

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

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

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

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

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

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

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

Пример:

forest.inforest.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. Скобки

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

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

Даётся строка, состоящая из маленьких английских букв и символов `(' и `)' (ASCII коды 40 и 41, соответственно). Необходимо с помощью операции \textbf{удаления} избавиться от всех скобок. При этом оставшаяся строка должна иметь наибольшую возможную длину.

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

Рассмотрим пример: s = abac(a)ba(mn(o)go)eda.

  1. Выберем подстроку (a) и удалим. Останется abacba(mn(o)go)eda.
  2. Выберем подстроку (o) и удалим. Останется abacba(mngo)eda.
  3. Выберем подстроку (mngo) и удалим. Останется abacbaeda.

Также Вася в это примере мог бы удалить например подстроку (a)ba(mn(o), но в таком случае оставшуюся закрывающую скобку было бы невозможно удалить. Ещё, Вася мог бы сразу удалить подстроку (a)ba(mn(o)go), но в таком случае осталось бы abaceda, что менее оптимально.

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

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

В единственной строке файла содержится строка s длиной не более 100000 символов, которая состоит из маленьких букв английского алфавита и символов `(' и `)'. Гарантируется, что всегда существует способ удаления, при котором остается только строка, состоящая только из символов английского алфавита.

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

Выведите в единственной строке файла исходную строку, в которой символы, которые будут удалены, заменены на символы `*'. В данной задаче допускается несколько решений, проверяющая программа жюри проверит ваше решение в соответствии с условием. Пусть в Вашем ответе осталось a букв после удаления скобок, в ответе жюри – b букв, а тест стоит c баллов. Тогда если a = b, Вы получите за этот тест c баллов. В противном случае вы получите 0.5 * c * a / b баллов. Обратите внимание, что если Ваша программа завершится на тесте с ошибкой, превысит ограничения по времени или памяти, или вовсе не выведет ответ, Вы получите 0 баллов за этот тест.

Пример:

parentheses.inparentheses.out
(i)nt) ******
zanknvn()(t()l zanknvn******l

Решения, работающие для строк длины ≤ 300, будут оцениваться из 40 баллов.

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


Источник: XXIV Городская олимпиада школьников по информатике

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


C. Парковка

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

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

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

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

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

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

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

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

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

Пример:

parking.inparking.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 баллов.

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


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

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


D. Грабли

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

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

Петя помнит, что грабель i-го вида у деда имеется bi штук. Если наступить на грабли i-го вида ai раз, то можно наконец получить необходмый опыт для преодоления таких грабель в следующий раз и более ни разу ими по лбу не получать. Помимо этого Петя умеет перепрыгивать грабли, но может это сделать не более чем K раз. При этом перепрыгивание грабель хоть и позволяет избежать удара по лбу, но не даёт опыта в обхождении таких грабель. Следовательно, чтобы научиться обходить грабли i-го вида, Пете придётся обязательно получить такими граблями ai раз по лбу.

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

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

В первой строке входного файла находятся два числа N и K – количество видов грабель, разложенных заботливым дедом и количество прыжков, которое может совершить Петя (1 ≤ N ≤ 104, 1 ≤ K ≤ 103).

Далее следует N строк, по два числа в каждой – ai и bi, количество раз, которое требуется получить граблями i-го вида по лбу, чтобы научиться их обходить и количество грабель i-го вида, лежащих на пути до дачи (1 ≤ ai ≤ bi ≤ 103).

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

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

Пример:

rake.inrake.out
2 5 3 5 1 5 1
3 3 5 10 5 10 5 10 15

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

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

Если Ваше решение работает для случая ai = 1, оно будет оцениваться из 40 баллов. Не забудьте в таком случае добавить в программу заглушки для тестов из условия, чтобы программа была принята тестирующей системой на проверку.


Источник: XXIV Городская олимпиада школьников по информатике

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


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.intrails.out
5 7
6 9

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


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

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






Версия для печати