--->
21 задач
<---
Источники
Алисе нравятся две вещи — ее зеркало и ее кубики. Кубики были предназначены для изучения детьми алфавита, то есть на их сторонах написаны некоторые буквы. Алиса любит играть с кубиками возле зеркала.
Когда Алиса учила алфавит, она заметила, что с ее зеркалом что-то не так! Кубик в зеркале мог показывать не ту букву, что изображена на нем, но всегда одну и ту же. Алиса придумала новую игру, пытаясь составить смешные слова из реальных кубиков и из кубиков в зеркале одновременно.
Игра имела следующие правила. Алиса выкладывала из кубиков слово S1. Эти же буквы в зеркале показывали слово S2, которое могло отличаться от отражения S1, так как зеркало было заколдованным. Но длина каждого слова равнялась N.
Затем Алиса проделывала следующие шаги. Она выбирала два кубика i и j и меняла их местами. В зеркале при этом менялись изображения кубиков N – i + 1 и N – j + 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.
Коля использует в формуле следующие обозначения (операции перечислены от высшего приоритета к нисшему):
Коля может построить новую схему, соответствующую любой формуле. Переменными в этой формуле будут состояния пинов сокета. Для начала он хочет построить схему, в которой входными значениями будут состояния всех пинов сокета, а в качестве выхода мы получим значение единственного переключателя, который при любых входных значениях будет находится в состоянии включено. Напишите программу, которая поможет Коле написать соответствующую формулу.
Первая строка входных данных содержит единственное целое число 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)
Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:
| 1 | 2 | … | N |
| N+1 | N+2 | … | 2*N |
| : | : | … | : |
| N*(N–1)+1 | N*(N–1)+2 | … | N*N |
Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).
Дэвиду приходится довольно часто повторять этот трюк, и, чтобы не ошибиться, он попросил написать программу, которая будет ему сообщать, сколько ходов должны делать телезрители, и какие картинки нужно убирать. Напишите такую программу.
Во входном файле записано одно число N — размер квадрата (2N100).
В выходной файл ваша программа должна печатать следующие строки чисел:
K1 X1,1 X1,2 … X1,m1
K2 X2,1 X2,2 … X2,m2
…
Ke Xe,1 Xe,2 … Xe,me
где Ki — это число ходов, которые должны сделать телезрители, а Xi,1 … Xi,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все Ki должны удовлетворять условию 2NKi10000 и все Ki должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать Ki ходов, Дэвид должен убирать хотя бы одну картинку. Каждое Ki должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.
3
7 1 3 7 9 9 2 4 6 8
В тридесятом царстве в новогодние праздники все лягушки собираются на самом большом болоте, чтобы поиграть в замечательную игру. Всего в этом царстве живет N зеленых лягушек и M коричневых. Для игры они выбирают на болоте N + M + 1 кочку, на первые N кочек слева садятся зеленые лягушки, а на последние M — коричневые (т. е. между ними находится одна кочка, на которой никто не сидит). Зеленые лягушки садятся лицом к коричневым лягушкам, а коричневые — к зеленым. Кочки настолько маленькие, что развернуться на них, не свалившись в болото, совершенно не возможно. Поэтому лягушки могут двигаться только вперед и не могут разворачиваться.
На каждом ходе игры одна из лягушек перепрыгивает с той кочки, где она сидит, на свободную кочку. При этом лягушка может прыгнуть на соседнюю кочку вперед, либо перепрыгнуть через одну кочку, если соседняя занята.
Чтобы праздник удался, зеленые лягушки должны оказаться на последних кочках, а коричневые — на первых. Порядок, в котором лягушки окажутся на кочках, не важен. Так как на праздник каждый раз приходит разное количество лягушек, то им каждый год приходится придумывать очередность прыжков. Напишите программу, которая поможет лягушкам составить план прыжков.
Поиграть в эту игру для случая N=M=3 можно по ссылке:
Во входном файле записаны два числа N и M (1≤N≤1000, 1≤M≤1000) – количество зеленых и коричневых лягушек соответственно.
Выведите последовательность прыжков лягушек для достижения поставленной цели. Каждый прыжок можно задать одним числом — номером прыгающей лягушки (поскольку свободная кочка всегда ровно одна). Пронумеруем всех лягушек в соответствии с их начальным положением. Зеленые лягушки будут пронумерованы числами от 1 до N, а коричневые — с N+1 до N+M в порядке слева направо.
В первую строку выходного файла выведите число K — количество прыжков. K не должно превышать 107. Далее выведите K чисел — номера лягушек.
Если же достичь требуемой рассадки лягушек нельзя, выведите одно число –1.
2 1
5 2 3 2 1 3