Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(20 задач)
    Формула(15 задач)
    Комбинаторика(8 задач)
---> 50 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 1 секунда

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

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

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

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

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

Примеры
Входные данные
3
0 0 2
Выходные данные
2 3 1 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Том Сойер получил важное задание по покраске забора. Забор состоит из 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$). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры
Входные данные
1 1
1
1 1
Выходные данные
2
Входные данные
5 2
2
1 2
5 5
Выходные данные
12
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
TEAM
TIED
MATE
EDIT
Выходные данные
Yes
Входные данные
TEAM
MATE
TAME
MEAT
Выходные данные
No
Входные данные
AAAA
AAAA
AAAA
AAAA
Выходные данные
Yes

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

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

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

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

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

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

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

Примеры
Входные данные
15
Выходные данные
48888888
Входные данные
70
Выходные данные
88888888888888888888888888888888888

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

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

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

  • Обозначение пина — буква от ‘A’ до ‘K’ ;
  • Скобки обозначают, что если E >— это формула, то (E) — тоже формула;
  • Отрицание — ~E— это формула для любой формулы E;
  • Конъюнкция E1 & E2 &…&En;
  • Дизъюнкция — E1| E2| … | En;
  • Импликация Е1 => E2 => => En. Импликации выполняются справа налево: Е1 => E2 => E3 означат
    Е1 => (E2 => E3);

  • Эквивалентность — Е1 <=> E2 <=> … <=> En. Такое выражение вычисляется так:
    (Е1 <=> E2) &(Е2<=> E3) & … &(En-1 <=> En)..

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

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

Первая строка входных данных содержит единственное целое число 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)

Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест