#1243

Распаковка строчки

Темы: [Алгоритмы на строках]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача G ]

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

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

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

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

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

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

Примеры

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

ABC

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

ABC

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

O2A3O2AO

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

OAAOOOAAO

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

A2B3C4D5E6F7G

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

ABBCCCDDDDEEEEEFFFFFFGGGGGGG

#1244

Дремучий лес

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача H ]

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

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

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

Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

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

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

Примеры

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

3
      0.00      30.00      25.00
      0.00     -30.00      25.00
     40.00       0.00      16.00

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

NO
     -833.3333340000      -552.7707973875
      833.3333340000       552.7707973875

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

3
      0.00      30.00      29.00
      0.00     -30.00      29.00
     40.00       0.00      19.00

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

YES

#1252

Тестирование

Темы: [Цикл for]

Источники: [ Личные олимпиады, Индивидуальная олимпиада по информатике и программированию (ИОИП), Заключительный этап 2009, Задача A ]

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

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

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

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

Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) вопросов в тесте. Вторая строка входного файла содержит n целых чисел a1, a_{2, . . . , an} — номера правильных вариантов ответов на каждый из вопросов. Третья строка входного файла содержит n целых чисел b₁, b₂, . . . , b_n — номера вариантов, выбранных тестируемым. Для чисел a_{i и b_i верны неравенства 1 ≤ a_{i, b_i ≤ 10.}}

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

В выходной файл выведите число вопросов, на которые тестируемый дал правильный ответ.

Примеры

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

4
1 2 3 4
1 2 4 3

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

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

4
1 2 3 4
4 3 2 1

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

#1254

Монотонная последовательность

Темы: [Динамическое программирование: один параметр]

Источники: [ Личные олимпиады, Индивидуальная олимпиада по информатике и программированию (ИОИП), Заключительный этап 2009, Задача C ]

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

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c₁, . . . , c_n называется строго возрастающей, если выполняются неравенства c₁< c₂ < … < c_n, и строго убывающей, если выполняются неравенства c₁> c₂ > … > c_n.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100000). Каждая из последующих n строк описывает одну карточку и содержит два числа — ai написано на ее лицевой стороне, а b_i— на оборотной. Все числа a_i и b_{i находятся в диапазоне от 1 до 10⁹.}

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

В первой строке выходного файла выведите минимальное число действий, которое должен совершить Петя. Если Петина цель недостижима, то выведите в выходной файл число -1.

Комментарий к примеру тестов

В первом примере для достижения цели Петя может перевернуть карточки со второй по третью.

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

Примеры

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

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

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

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

-1

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

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

#1272

Олимпиада-2010

Темы: [Обход в глубину] [Обход в ширину]

Команда Москвы на Всероссийской олимпиаде по информатике 2017 года оказалась настолько велика, что помещается только в 2 вагона. Некоторые школьники испытывают друг к другу такую личную неприязнь, что не могут есть, находясь в одном вагоне. Поскольку не есть в поезде нельзя (это противоречит СанПиНам), то участников олимпиады надо рассадить так, чтобы школьники, испытывающие взаимную неприязнь, ехали в разных вагонах. Если это невозможно, никто никуда не поедет.

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

Первая строка входного файла содержит количество школьников N (1 ≤ N ≤ 10000) и количество взаимных неприязней M (1 ≤ M ≤ 100000). Следующие M строк содержат пары чисел, задающих номера участников, испытывающих взаимную неприязнь. Участники нумеруются с единицы.

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

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

Примеры

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

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

1 3 4 
2