Язык программирования

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 

Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры

№	Входные данные	Выходные данные
1	1	( ) [ ] { }

Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось. 

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

Напомним, иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 

Меллерт Гихаил сегодня был в прекрасном настроении до того, как его одноклассник Фусков Кедор не заговорил о политике. Гихаил очень сильно разозлился, поэтому придумал задачу по информатике для Кедора, чтобы тот начал решать и наконец-то заткнулся. 

Задача была такая:  “Существует n логических функций, которые зависят от одного и того же множества переменных. Даны n чисел, битовое представление которых определяет таблицу истинности для каждой функции. Вам необходимо найти такой порядок расположения функций, чтобы из каждой функции логически следовала любая из последующих или сказать, что это  невозможно. Если ответ существует, то необходимо найти лексикографически минимальный порядок. Можно показать, что размер множества переменных, от которого зависят функции, не влияет на решение задачи”.

 Кедор – ваш лучший друг, а Гихаил – заклятый враг, поэтому вы решили помочь с решением задачи, а затем вместе с Кедором возобновить разговоры о политике, чтобы Гихаил от злости улетел на Луну.

 

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

В первой строке дано число n (1 <= n <= 10) – кол-во функций. 

Во второй строке дано n чисел в диапазоне [0; 10^9] – таблицы истинности функций, переведенные в десятичную систему счисления. 

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

Если порядок существует, в первой строке выведите “YES”, во второй лексикографически минимальную перестановку из всех возможных. Если порядка нет, то выведите “NO”.

Пример

Ввод	Вывод
3 3 1 7	YES 2 1 3
2 1 2	NO

(с)  Курбатов Е., 2017

 

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

 

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

На вход подается одна строка без пробелов и знаков переноса строки.

В ней могут содержаться такие символы:

x - переменная, относительно которой Курбат должен решить

уравнение. Может стоять где угодно.

+-*/= - соответствующие знаки арифметических операций. НЕ могут стоять в начале уравнения. Могут стоять после икса или констант.

^ - возведение в степень. Может стоять только после икса. После может стоять только константа.

Числа от -10^1000 до 10^1000 - константы. Могут стоять после иксов, 

знаков арифметических операций и знака возведения в степень.

 

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

Если курбат может решить уравнение, то выведите "Yes", иначе выведите "No".

Ввод	Вывод
10x+x=7	Yes

(с) Григорьев Е., 2017

Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:

 

RSRSSS

RSRSSS

RSRSSS

 

Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).

 

Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.

ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.

 

Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.

 

INPUT FORMAT:

 

* Строка 1: Два разделённых пробелом целых числа M и N.

 

* Строки 2..M+1: M строк ровно по N символов (каждый R или S),

        описывающих желаемое финальное состояние поля.

 

 

 

Ввод	Вывод
3 6 RSRSSS RSRSSS RSRSSS	3

 

OUTPUT DETAILS:

 

ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец,  S в колонках 4-6.

 

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.

 

ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t_1, t_2, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.

 

ФД заметил, что слова из списка T обладают таким свойством, что никакое из них не является подстрокой другого слова из T. В частности, это означает, что ранее вхождение слова из T в S всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки S.

 

INPUT FORMAT: 

Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t_1, t_2, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.

 

OUTPUT FORMAT: 

Строка S после всех удалений. Гарантируется, что S не станет пустой.
 

Ввод	Вывод
begintheescapexecutionatthebreakofdawn 2 escape execution	beginthatthebreakofdawn

 

Ферма Джона представлена решёткой N×N полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:

ABCD

BXZX

CDXB

WCBA

Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.

 

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.

 

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.
   

Ввод	Вывод
4 ABCD BXZX CDXB WCBA	12

Беси может сделать следующие палиндромы:

 

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"

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

Напишите программу, которая заполняет матрицу из N строк и M столбцов натуральными числами змейкой, как показано в примере.
 

Напишите программу, которая заполняет матрицу неотрицательными числами по диагоналям (см. пример). Значение элемента матрицы равно расстоянию от левого верхнего угла матрицы.
 

Недавно вошла в моду корова-художница Picowso.

Picowso рисует особым образом. Она начинает на чистом холсте N×N, представленной матрицей N×N нолей, где ноль означает пустую ячейку холста. Затем она рисует до 9 прямоугольников на холсте, каждый одним из 9 цветов (последовательно пронумерованных 1…9). Например, она может начать рисовать прямоугольник цветом 2, получая такое промежуточное состояние холста:

 

2220 

2220 

2220 

0000

Затем она может нарисовать прямоугольник цветом 7:

 

2220 

2777 

2777 

0000

Затем она может нарисовать прямоугольник цветом 3:

 

2230 

2737 

2777 

0000

Каждый прямоугольник имеет стороны, параллельные сторонам холста и самый большой прямоугольник может быть размером с весь холст, а самый маленький размером в одну ячейку. Каждый цвет из 1…9 используется ровно один раз, хотя впоследствии любой цвет может полностью покрыть некоторые из ранних цветов.

 

По заданному конечному положению холста вычислите сколько из ещё видимых цветов могли быть первым нарисованным цветом.

 

ФОРМАТ ВВОДА:

 

Первая строка ввода содержит N, размер холста (1≤N≤10). Следующие N строк описывают финальную картинку холста, каждая содержит по N чисел в интервале 0…9. Гарантируется, что такой ввод был получен рисованием как описано выше с использованием различных цветов.

ФОРМАТ ВЫВОДА:

 

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

Ввод	Вывод
4 2230 2737 2777 0000	1

У Фермера Джона есть N коров с пятнами и N коров без пятен. ФД, как генетик, знает, что пятна на коровах вызваны мутациями в одной позиции коровьего генома.

За большие деньги ФД выписал геномы своих коров. Каждый геном есть строка длины M, построенная из четырёх символов A, C, G, T. Когда он выписал их, у него получилась такая таблица (для N=3):

 

Позиция:                  1 2 3 4 5 6 7 ... M

 

Пятнистая корова 1: A A T C C C A ... T

Пятнистая корова 2: G A T T G C A ... A

Пятнистая корова 3: G G T C G C A ... A

 

Без пятен корова 1: A C T C C C A ... G

Без пятен корова 2: A C T C G C A ... T

Без пятен корова 3: A C T T C C A ... T

Внимательно проанализировав эту таблицу, он предположил, что позиция 2 есть потенциальное место в геноме, которое отвечает за пятнистость. Потому что в этой позиции у коров без пятен находится один и тот же символ С, а у пятнистых коров находятся символы A или G. Причём G больше никогда не появлялось на позиции 2. Позиция 1 не может объяснять пятнистость, поскольку A в этой позиции есть и у пятнистых коров.

 

По заданным геномам коров ФД, посчитайте количество позиций, которые потенциально могли бы объяснять пятнистость.

 

ФОРМАТ ВВОДА:

 

Первая строка ввода содержит N и M, оба - положительные целые числа не более 100. Каждая из следующих N строк содержит по M символов. Они описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен.

ФОРМАТ ВВОДА:

 

Вычислите количество позиций генома (целое число в интервале от 0…M), которые потенциально могут объяснять пятнистость. Такие позиции можно предсказывать по заданной информации.
 

Ввод	Вывод
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	1

Фермер Джон тестирует новую камеру, которая может "схватить картинку" и автоматически вычислить положение коров. К несчастью, у камеры не очень хороший алгоритм поиска коров и ФД нуждается в Вашей помощи.

Картинка, получаемая камерой, может быть описана решёткой из N×N символов, каждый в интервале A…Z, представляющих один из 26 возможных различных цветов. ФД считает наилучшим такой алгоритм распознавания коров: PCL (возможное размещение коровы) - это прямоугольник на решётке (возможно вся решётка) со сторонами параллельными сторонам решётки, не содержащий внутри других PCL и обладающий следующим свойством: внутри этого прямоугольника должны присутствовать ровно два цвета, один формирует непрерывный регион, а другой формирует два или более непрерывных регионов.

 

Например, такой образ

 

AAAAA

ABABA

AAABB

есть PCL, поскольку символы A формируют непрерывный регион, символы B форрмируют более одного непрерывного региона. Интерпретация - это корова с цветом A и с пятнами цвета B.

 

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

 

По заданному образу камеры ФД определите количество PCL.

 

ФОРМАТ ВВОДА:

 

Первая строка ввода содержит N, размер решётки (1≤N≤20). Следующие N строк описывают образ, каждая состоит из N символов.
 

ФОРМАТ ВЫВОДА:

 

Количество PCL в образе.
 

Ввод	Вывод
4 ABBC BBBC AABB ABBC	2