Задана функция \(f\), написанная на довольно примитивном языке. Функция принимает целое значение, которое сразу записывается в переменную \(x\). \(x\) — это целочисленная переменная, которая может принимать значения от \(0\) до \(2^{32}-1\). Функция содержит три типа команд:

• for \(n\) — цикл for;
• end — каждая команда между «for \(n\)» и соответствующим «end» выполняется \(n\) раз;
• add — прибавляет 1 к \(x\).

После выполнения команд возвращается значение \(x\).

Каждый «for \(n\)» имеет парный «end», поэтому гарантируется, что функция корректна. За «for \(n\)» может сразу следовать «end». «add» может быть расположен вне циклов for.

Заметили, что команда «add» может переполнить значение \(x\)! Это значит, что значение \(x\) становится больше \(2^{32}-1\) после некоторой команды «add».

Теперь запускается \(f(0)\), а ваша задача — узнать, корректно ли полученное значение \(x\) или переполнение сделает его некорректным.

Если произошло переполнение, то выведите «OVERFLOW!!!», иначе выведите полученное значение \(x\).

В этой задаче речь пойдет о вымышленных языках BHTML и BCSS, которые слегка напоминают HTML и CSS. Внимательно ознакомьтесь с условием задачи, так как схожесть лишь отдаленная, а в задаче используются крайне упрощенные аналоги.

Задан BHTML-документ, который похож на HTML, но значительно проще. Записывается он как последовательность открывающих и закрывающих тегов. Тег вида «<имятега>» называется открывающим, а тег вида «</имятега>» — закрывающим. Кроме того, есть самозакрывающиеся теги, которые записываются в виде «<имятега/>» и в этой задаче полностью эквивалентны «<имятега></имятега>». Все имена тегов в этой задаче — строки из строчных латинских букв, имеющие длину от 1 до 10 символов. Некоторые теги могут иметь одинаковые имена.

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

• удалить любой самозакрывающийся тег «<имятега/>»,
• удалить пару открывающий-закрывающий тег, которые идут подряд (в таком порядке) и имеют одинаковые имена, то есть подстроку «<имятега></имятега>».

Например, вам может быть задан документ «<header><p><a/><b></b></p></header><footer></footer>», но не могут быть заданы документы «<a>», «<a></b>», «</a><a>» или «<a><b></a></b>».

Очевидно, для каждого открывающего тега существует единственный парный закрывающий — каждая такая пара называется элементом. Самозакрывающийся тег — тоже элемент. Говорят, что один элемент вложен в другой, если теги первого находятся между тегами второго. Считается, что никакой элемент не вложен сам в себя. Например, в примере выше элемент «b» вложен в «header» и в «p», но не вложен в «a» и «footer», а также не вложен в самого себя («b»). Элемент «header» имеет три вложенных в него элемента, а «footer» — ноль.

Правила BCSS нужны для назначения стилей при выводе элементов документов BHTML. Каждое правило записывается в виде последовательностей слов «x₁ x₂ ... x_n». Под это правило попадают все такие элементы t, которые удовлетворяют пунктам из списка:

• существует последовательность вложенных элементов с именами тегов «x₁», «x₂», ..., «x_n» (то есть второй элемент вложен в первый, третий во второй и так далее),
• эта последовательность заканчивается элементом t.

Например, правилу «a b» удовлетворяют все такие элементы «b» для которых существует элемент «a», в который они вложены. Правилу «a b b c» удовлетворяют все такие элементы «c» для которых существует три элемента «a», «b», «b», что в цепочке «a»-«b»-«b»-«c» каждый очередной элемент вложен в предыдущий.

Напишите программу, которая по заданному BHTML-документу и набору BCSS-правил определяет количество элементов, которые удовлетворяют каждому из правил.

Вася разрабатывает свой язык программирования VPL (Vasya Programming Language). Сейчас он занят созданием системы исключений. В его представлении система исключений должна функционировать следующим образом.

Для обработки исключений используются try-catch-блоки. Работа с блоками осуществляется при помощи двух операторов:

1. Оператор try. Открывает новый try-catch-блок.
2. Оператор catch(<тип_исключения>, <сообщение>). Закрывает еще не закрытый try-catch-блок, который был начат последним. Данный блок может быть активирован только исключением типа <тип_исключения>. При активации этого блока, на экран выводится <сообщение>. Если в данный момент не открыто ни одного try-catch-блока, то оператор catch использовать нельзя.

Исключения могут возникать в программе только в одном случае: при использовании оператора throw. Оператор throw(<тип_исключения>) создает исключение указанного типа.

Пусть в результате вызова какого-то оператора throw в программе возникло исключение типа a. В этом случае активируется try-catch-блок такой, что оператор try этого блока описан в программе раньше, чем вызванный оператор throw, при этом оператору catch этого блока в качестве параметра передан тип исключения a, и оператор catch этого блока описан позже, чем вызванный оператор throw. Если таких try-catch-блоков несколько, активируется тот блок, описание оператора catch которого встречается раньше всех. Если ни один try-catch-блок не был активирован, то на экран выводится сообщение «Unhandled Exception».

Для тестирования системы, Вася составил программу, в которой содержатся только операторы try, catch и throw, в одной строке находится не более одного оператора, во всей программе присутствует ровно один оператор throw.

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

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

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

Вызов процедуры состоит из имени процедуры и списка переменных-параметров. Назовем процедуру подходящей для данного вызова, если выполняются условия:

• ее имя совпадает с именем вызванной процедуры;
• количество ее параметров совпадает с количеством параметров вызванной процедуры;
• типы ее параметров совпадают с соответствующими типами переменных в вызове процедуры. Тип параметра совпадает с типом переменной, если параметр имеет обобщенный тип T, либо типы переменной и параметра совпадают.

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

Скобочной последовательностью называется строка, состоящая только из символов «(», «)», «[» и «]».

Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()[]», «([])» — правильные (полученные выражения: «(1)+[1]», «([1+1]+1)»), а «](» и «[» — нет. Пустая строка является правильной скобочной последовательностью по определению.

Подстрокой s[l... r] (1 ≤ l ≤ r ≤ |s|) строки s = s₁s₂... s_|s| (где |s| — длина строки s) называется строка s_ls_l + 1... s_r. Пустая подстрока по определению считается подстрокой любой строки.

Вам дана не обязательно правильная скобочная последовательность. Найдите ее подстроку, которая является правильной скобочной последовательностью и при этом содержит как можно больше скобок «[».

Компания «Bersoft» работает над новой версией своего самого известного текстового редактора, Bord 2010. В Bord, как и во многих других текстовых редакторах, должна быть реализована возможность печати многостраничных документов. Пользователь перечисляет через запятую (без пробелов) номера страниц документа, которые он хочет распечатать.

Вам поручено написать часть программы, выполняющую «нормализацию» списка. На вход вашей программе подается список, который ввел пользователь. Ваша программа должна вывести этот список в формате l₁-r₁,l₂-r₂,...,l_k-r_k, где r_i + 1 < l_i + 1 для всех i от 1 до k - 1, и l_i ≤ r_i. Новый список должен содержать все страницы которые ввел пользователь и ничего больше. Повторные появлений одной и той же страницы в списке пользователя следует игнорировать. В случае, если для некоторого элемента i нового списка l_i = r_i, этот элемент необходимо выводить как l_i, а не «l_i - l_i».

Например, список 1,2,3,1,1,2,6,6,2 нужно вывести в виде 1-3,6.

Иногда email-адреса приходится диктовать по телефону. Точку обычно называют словом dot, а собаку at. В результате получается что-то вроде vasyaatgmaildotcom. Ваша задача — преобразовать это в корректный email-адрес ([email protected]).

Известно, что корректный email-адрес содержит только символы . @ и маленькие латинские буквы, не начинается и не заканчивается точкой. Также, корректный email-адрес не начинается и не заканчивается собакой. Более того, email-адрес содержит ровно один символ @ но при этом может содержать любое (возможно, нулевое) количество точек.

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

Всего возможно два варианта замены: dot можно заменить на точку, at можно заменить на собаку.

Ваня делает домашнее задание по математике. У него есть выражение типа , где x₁, x₂, ..., x_n — цифры от 1 до 9, а знаком обозначается либо плюс '+' либо знак умножения '*'. Ване нужно поставить в этом выражении одну пару скобок так, чтобы максимизировать значение полученного выражения.

В данной задаче рассматриваются булевы функции от четырех переменных A, B, С, D. Переменные A, B, C и D являются логическими и могут принимать значения 0 или 1. Будем задавать функцию с помощью следующей грамматики:

<выражение> ::= <переменная> | (<выражение>) <оператор> (<выражение>)

<переменная> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

<оператор> ::= '&' | '|'

Здесь заглавными буквами A, B, C, D обозначаются переменные, а строчными — их отрицания. Например, если A = 1, то символу 'A' соответствует значение 1, а символу 'a' — значение 0. Символ '&' здесь соответствует операции логического И, символ '|' — операции логического ИЛИ.

Вам дано выражение s, задающее функцию f, в котором некоторые операторы и переменные пропущены. Так же вам известны значения функции f(A, B, C, D) для некоторых n различных наборов значений переменных. Посчитайте количество способов восстановить пропущенные в выражении элементы так, чтобы получившееся выражение соответствовало известной информации о функии f в заданных наборах переменных. Так как величина результата может быть большой, выведите её остаток от деления на 10⁹ + 7.

Вам задана строка s, состоящая из открывающих и закрывающих скобок четырех видов <>, {}, [], (). Все скобки делятся на два типа: открывающие и закрывающие. Разрешается заменить любую скобку на любую другую такого же типа. Например, скобку < можно заменить на скобку {, но нельзя заменить на скобку ) или >.

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

Определим правильную скобочную последовательность. Пустая строка считается таковой. Пусть строки s₁ и s₂ являются правильными скобочными последовательностями, тогда строки <s₁>s₂, {s₁}s₂, [s₁]s₂, (s₁)s₂ также являются правильными скобочными последовательностями.

Например, строка "[[(){}]<>]" является правильной скобочной последовательностью, а строки "[)()" и "][()()" — нет.

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

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

Будем считать, что строка определяет имя домена, если она состоит из символов «a»-«z», «0»-«9» и точек. Никакие две точки не должны в имени домена идти подряд. Пусть точками вся строка разделяется на части — тогда последняя часть (самая правая) должна иметь длину 2 или 3. Начинаться и заканчиваться точкой имя домена не может. Определите, является ли заданная строка именем домена.

Большинство программистов на C/C++ знают об отличных возможностях, предоставляемых директивами препроцессора #define, но также многим известны и проблемы, возникающие при их неаккуратном использовании.

В данной задаче мы рассматриваем следующую модель конструкций #define (также называемых макросами). Каждый макрос имеет свои имя и значение. Объявляется он следующим образом:

#define имя_макроса значение_макроса

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

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

Рассмотрим это на следующем примере. Определим такую конструкцию #define:

#define sum x + y

и пусть далее в программе считается выражение "2 * sum". После подстановки макроса получится выражение "2 * x + y", вместо интуитивно ожидаемого "2 * (x + y)".

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

Определим это более формально. Выполним обычную подстановку макросов в заданном выражении. Кроме того, выполним "безопасную" подстановку макросов в выражение: окружив значение каждого макроса скобками; после этого, пользуясь арифметическими правилами раскрытия скобок, можно опустить некоторые скобки. Если при этом можно получить выражение, полностью совпадающее с результатом обычной подстановки (посимвольно, но игнорируя пробелы), то это выражение и система макросов считаются корректными, иначе — подозрительными.

Примечание. В этом критерии операция деления рассматривается с математической точки зрения, а не в смысле языка C++ (в котором под ним подразумевается деление нацело). Например, в выражении "a*(b/c)" мы можем опустить скобки и получить выражение "a*b/c".

Два друга решили создать язык программирования, назвали они его Perse-script.

Важная часть языка — строки. Строки в Perse-script записываются в кавычках (")

Например, "Hello" — константная строка. Но Hello — имя переменной или зарезервированное слово, которые мы не рассматриваем в этой задаче.

Perse-script — функциональный язык, в нем нет операторов. Например, чтобы сложить два числа нужно написать sum(a,b), а не a+b.

В языке есть несколько команд для работы со строками:

• concat(x,y) возвращает конкатенацию («склейку») двух строк x и y. Например, concat("Hello","World") возвращает "HelloWorld".
• reverse(x) возвращает перевернутую строку x. Например, reverse("Hello") возвращает "olleH".
• substr(x,a,b) принимает строку x и два целых числа a и b (1 ≤ a ≤ b ≤ n, где n — длина строки x). Возвращает подстроку x с индекса a по индекс b, включительно. Например, substr("Hello",2,4) возвращает "ell".
• substr(x,a,b,c) — другая версия substr, которая получает подстроку с шагом c. c всегда положительно. Например, substr("HelloWorld",1,10,2) возвращает "Hlool". Более точно: изначально ответ пуст. Эта функция добавляет в ответ a-ый символ, а затем каждый c-ый считая от него, и так до b.

Вы собираетесь реализовать работу со строками в Perse-script. Дано выражение, выведите его результат. Гарантируется, что все функции в качестве аргументов содержат только константные строки, записанные в кавычках, и перечисленные выше строковые функции.

Названия функций Perse-script регистронезависимы. Так, чтобы вызвать substr можно написать SUBsTr(). Но нельзя писать "hElLo" вместо "Hello".

Для дальнейшего разъяснения смотрите примеры.

Василий вышел из магазина и ему стало интересно пересчитать сумму в чеке. Чек представляет собой строку, в которой названия покупок и их цены записаны подряд без пробелов. Чек имеет вид «name₁price₁name₂price₂...name_nprice_n», где name_i (название i-го продукта) — это непустая строка длины не более 10, состоящая из строчных букв латинского алфавита, а price_i (цена i-го продукта) — это непустая строка, состоящая из точек и цифр. Продукты с одинаковым названием могут иметь разные цены.

Цена каждого продукта записана в следующем формате. Если продукт стоит целое количество рублей, то копейки не пишутся.

Иначе, после записи количества рублей к цене приписывается точка, за которой следом ровно двумя цифрами записаны копейки (если копеек менее 10, то используется лидирующий ноль).

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

Например, записи цен:

• «234», «1.544», «149.431.10», «0.99» и «123.05» являются корректными,
• «.333», «3.33.11», «12.00», «.33», «0.1234» и «1.2» не являются корректными.

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

Facetook — широко известная социальная сеть. Недавно в ней появилась новая функция — стена с приоритетами. Эта функция позволяет сортировать всех ваших друзей по коэффициенту дружбы. Чем больше вы общаетесь с другом, тем больше будет его коэффициент дружбы.

На коэффициент дружбы влияет 3 типа действий:

• 1. человек X написал на стене человек Y ("X posted on Y's wall") — 15 очков;
• 2. человек X прокомментировал сообщение человека Y ("X commented on Y's post") — 10 очков;
• 3. человеку X понравилось сообщение человека Y ("X likes Y's post") — 5 очков.

X и Y — два различных имени. Каждое действие увеличивает коэффициент дружбы между X и Y (и наоборот) на данное количество очков (коэффициент дружбы между X и Y равен коэффициенту дружбы между Y и X).

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

Вася недавно прочитал о битовых операциях, которые используются в компьютерах: AND, OR и XOR. Он неплохо изучил их свойства и придумал новую игру. Изначально Вася выбирает разрядность m для своей игры, это значит, что все числа в игре будут состоять из m битов. Потом он просит Петю выбрать некоторое одно m-битное число. После этого Вася вычисляет значения n переменных. Каждой из переменных присваивается либо константное m-битное число, либо результат выполнения битовой операции, операндами которой могут являться уже определенные переменные или выбранное Петей число. После этого сумма очков, которую получает Петя, равна сумме значений всех переменных.

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

The Rebel fleet is on the run. It consists of m ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form .

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!