#197

Темы: [Размещения с повторениями] [Формула]

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

1 секунда

Пусть дана перестановка π. Обозначим φ[i] - количество таких j, что π[j] > π[i], а j < i. φ называется таблицей инверсий перестановки π. Требуется по данной таблице инверсий восстановить перестановку.

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

В первой строке входных данных содержится число 0 < N <= 2000 - количество чисел в перестановке π. Во второй строке записана таблица инверсий φ.

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

Выведите искомую перестановку π.

Примеры

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

3
0 0 2

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

2 3 1

#601

Забор

Темы: [Формула]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 2 тур, Задача A ]

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры

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

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

#937

Заколдованное зеркало

Темы: [Конструктив]

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

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

Когда Алиса учила алфавит, она заметила, что с ее зеркалом что-то не так! Кубик в зеркале мог показывать не ту букву, что изображена на нем, но всегда одну и ту же. Алиса придумала новую игру, пытаясь составить смешные слова из реальных кубиков и из кубиков в зеркале одновременно.

Игра имела следующие правила. Алиса выкладывала из кубиков слово S₁. Эти же буквы в зеркале показывали слово S₂, которое могло отличаться от отражения S₁, так как зеркало было заколдованным. Но длина каждого слова равнялась N.

Затем Алиса проделывала следующие шаги. Она выбирала два кубика i и j и меняла их местами. В зеркале при этом менялись изображения кубиков N – i + 1 и N – j + 1 соответственно.

Цель игры — получить из слова S₁ слово T₁, которое будет выглядеть в зеркале как слово T₂. Алиса не знает, когда это возможно, а когда нет. Помогите ей ответить на этот вопрос.

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

Во входном файле находятся 4 слова S₁, S₂, T₁ и T₂, каждое в отдельной строке. Все слова имеют одну и ту же длину N (1 ≤ N≤ 100) и состоят только из заглавных латинских букв.

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

Выведите Yes или No в зависимости от ответа на вопрос задачи.

Примеры

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

TEAM
TIED
MATE
EDIT

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

Yes

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

TEAM
MATE
TAME
MEAT

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

No

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

AAAA
AAAA
AAAA
AAAA

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

Yes

#939

Печатная машинка

Темы: [Конструктив]

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

Представьте теперь печатную машинку с очень острыми буквами, которые вместо печати протыкают бумагу. Ясно, что цифра 0 на такой машинке вырежет дырку в бумаге, и из нее выпадет маленький овал. То же самое случиться с цифрами 4, 6, 9. А 8 вырежет уже две дырки. Остальные проткнут бумагу, но не вырежут дырку.

Лучшие умы в программировании готовят выставку, посвященную юбилею создания Паскаля. Одна из идей для этой выставки — сделать инсталляцию, состоящую из пустых листов бумаги, содержащих в точности h (0 ≤ h ≤ 510) дырок каждый. Дырки делаются описанной печатной машинкой, путем пробивания на ней неотрицательного целого числа. Число должно быть минимально возможным и не содержать ведущих нулей. Помогите организаторам подобрать соответствующее число.

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

На вход подается число h (0 ≤ h ≤ 510).

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

Выведите число, которое должно быть напечатано.

Примеры

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

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

48888888

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

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

88888888888888888888888888888888888

#940

Важные переключатели

Темы: [Конструктив]

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

К несчастью, переключатели не являются доступными. Но Коля нашел сокет, каждый пин которого соединен с одним из переключателей через некоторую схему. Коля нашел эту схему в Интернете. Он обозначил переключатели маленькими латинскими буквами, а пины сокета — большими буквами. После этого он выписал логическую формулу для каждого пина. Согласно этой формуле включенный переключатель представляется значением true, а выключенный —false.

Коля использует в формуле следующие обозначения (операции перечислены от высшего приоритета к нисшему):

Обозначение пина — буква от ‘A’ до ‘K’ ;
Скобки обозначают, что если E >— это формула, то (E) — тоже формула;
Отрицание — ~E— это формула для любой формулы E;
Конъюнкция — E₁ & E₂ &…&E_n;

Дизъюнкция — E₁| E₂| … | E_n;

Импликация Е₁ => E₂ =>… => E_n. Импликации выполняются справа налево: Е₁ => E₂ => E₃ означат
Е₁ => (E₂ => E₃);

Эквивалентность — Е₁ <=> E₂ <=> … <=> E_n. Такое выражение вычисляется так:
(Е₁ <=> E₂) &(Е₂<=> E₃) & … &(E_n_-1 <=> E_n)..

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

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

Первая строка входных данных содержит единственное целое число n — количество пинов у сокета (1 < n < 10). Следующие n строк содержат описания каждого пина. Одно описание состоит из обозначения пина и соответствующей формулы, отделенной от обозначения символами ‘:=’. Пин обозначен заглавной латинской буквой. Его формула расположена в одной строке и состоит из элементов ‘a’..‘k’, ‘(’, ‘)’, ‘~’, ‘&’, ‘ |’, ‘=>’ и ‘<=>’. Элементы формулы могут быть отделены друг от друга произвольным числом пробелов. Описание каждого пина содержит не более 1000 символов.

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

Если требуемая схема существует, то выведите в первой строке Yes и No в противном случае.

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

Примеры

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

3
A := (a=>c ) & (b<=>d)
C:= a | b
B  :=  c  |  d

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

Yes
(A|~A)&(C|~C)&(B|~B)