Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Коровы увлекаются словесными пазлами. Например, таким

USOPEN

OOMABO

MOOMXO

PQMROM

Как коровам, им интересно только единственное слово "MOO", которое может появиться во многих местах горизонтально, вертикально или по диагонали. Пример сверху содержит 6 таких слов.

Фермер Джон тоже любитель таких пазлов. Поскольку коровы не хотят, чтобы он разгадывал пазлы раньше коров, они зашифровали пазл, используя заменяющий шифр, который заменяет каждую букву алфавита некоторой другой, отличающейся буквой. Например, A может заменяться буквой X, B - буквой A и т.д. Никакая буква не заменяется собой и никакие две буквы не заменяются одной и той же буквой (иначе расшифровка может стать неоднозначной).

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

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

Первая строка ввода содержит N и M, описывающие количество строк и столбцов в пазле (оба не более 50). Каждая из следующих N строк содержит по M символов, описывающих одну строку зашифрованного пазла. Каждый символ - большая латинская буква в диапазоне A..Z.

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

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

Ввод	Вывод
4 6 TAMHGI MMQVWM QMMQSM HBQUMQ	6

Пояснение
Это пазл, приведенный в начале задачи, где "M" и "O" были заменены на "Q" и "M" соответственно.

Перебор

✓ 9✗ 341 100средняяВойти и решать

Where's Bessie?#27222

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

Картинка, получаемая камерой, может быть описана решёткой из 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

Задача на реализацию Обход в глубину Перебор

✓ 5✗ 41 100средняяВойти и решать

Bovine Genomics №2#27221

У Фермера Джона есть 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 G T T G C A ... T

Корова без пятен 3: A G T T C C A ... T

Посмотрев внимательно на эту таблицу он предположил, что позиции 2 и 4 могут отвечать за пятнистость. Поскольку, глядя на символы в этих позициях, ФД может предсказать, какая из его коров пятнистая, а какая - нет (например, если он видит G и С - значит, корова не пятнистая).

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

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

Первая строка ввода содержит NN (1≤N≤500) и MM (3≤M≤50). Каждая из следующих N строк содержит по M символов. Это описание геномов пятнистых коров. Следующие N строк описывают геномы коров без пятен.

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

Вычислите количество множеств из трёх различных позиций, которые могут объяснять пятнистость. Множество из трёх различных позиций может объяснять пятнистость, если пятнистость может быть предсказана абсолютно точно для популяции коров ФД, при анализе этих трёх позиций генома.

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

Вывод формулы Перебор

✓ 6✗ 191 100средняяВойти и решать

Перестановки#27214

Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно выполняться следующие три условия:

1. Шестнадцатеричные цифры в записи числа упорядочены по невозрастанию.

2. Если перевести это число в двоичную систему счсиления, то запись будет содержать не менее 5-ти идущих подряд единиц.

3. Любое шестнадцатеричное число, образованное перестановкой цифр этого числа и переведенное в двоичную систему счисления, также будет содержать в двоичной записи не менее 5-ти единиц подряд.

Перебор Системы счисления

✓ 12✗ 321 000средняяВойти и решать

Boolean Satisfiability#27116

Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this problem you are given a Boolean formula, and you need to find out if the variables of a given formula can be consistently replaced by the values true or false in such a way that the formula evaluates to true. SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of 3-CNF formula (3-SAT). However, for example, SAT problem for 2-CNF formulae (2-SAT) is in P.

#SAT is the extension of SAT problem. In this problem you need to check if it is possible, and count the number of ways to assign values to variables. This problem is known to be #P-complete even for 2-CNF formulae. We ask you to solve #1-DNF-SAT, which is #SAT problem for 1-DNF formulae.
You are given a Boolean formula in 1-DNF form. It means that it is a disjunction (logical or) of one or more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not). Formally:

Your task is to find the number of ways to replace all variables with values true and false (all occurrences of the same variable should be replaced with same value), such that the formula evaluates to true.

Input
The only line of the input file contains a logical formula in 1-DNF form (not longer than 1000 symbols). Logical operations are represented by ‘|’ (disjunction) and ‘~’ (negation). The variables are ‘A’ . . . ‘Z’ and ‘a’ . . . ‘z’ (uppercase and lowercase letters are different variables). The formula contains neither spaces nor other characters not mentioned in the grammar.

Output
Output a single integer — the answer for #SAT problem for the given formula

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7

Алгоритмы на графах Комбинаторика Конструктив

✓ 11✗ 16900средняяВойти и решать

Автомобильные номера#27092

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

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

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

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: «A», «B», «C», «E», «H», «K», «M», «O», «P», «T», «X», «Y» (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входных данных будут использоваться буквы латинского алфавита.

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

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

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

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

В последующих k строках выведите все такие номера в произвольном порядке.

Ввод	Вывод
X772KX	9 X277XK X277KX X727XK X727KX X772XK X772KX K277XX K727XX K772XX

Перестановки

✓ 8✗ 12800средняяВойти и решать

Гладкие числа#27087

Назовем число гладким, если его цифры, начиная со старшего разряда, образуют неубывающую последовательность. Упорядочим такие числа в возрастающем порядке и присвоим каждому номер. Требуется по номеру N вывести N-ое гладкое число.

Входные данные
На вход программы поступает номер N (\(1 <= N <= 2147483647\)).

Выходные данные
Выведите соответствующее номеру N гладкое число.

Примеры

№	Входные данные	Выходные данные
1	3	3
2	11	12

Перестановки

✓ 19✗ 711 000средняяВойти и решать

Матвей и замок#27025

Всемирно известному взломщику Матвею поступил заказ на инновационный сейф, выпущенный компанией "British Scientists, Inc". Этот сейф почти целиком сделан из адамантита, не поддающемуся ни одной из дрелей Матвея. Поэтому его единственным уязвимым местом является патентованный кодовый замок. К счастью, Матвей похитил чертежи сейфа ещё во время его разработки, поэтому точно знает принцип работы замка.

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

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

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

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

В первой строке на вход подаются два числа N (1 <= n <= 8) и Х (1 <= X <= 10^9) - количество цифр в коде и секретная константа. Во второй находится n цифр, разделённых пробелами. Разумеется, цифры могут повторяться.

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

Вывести необходимо единственное число - ответ на вопрос Матвея.

Ввод	Вывод
4 0 2 2 3 6	4
2 1 1 1	0

Перестановки

✓ 6✗ 28900средняяВойти и решать

Вывод паролей#27024

Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира. Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли. Леше известно, что пароль содержит в себе все символы лексикографически максимальной подстроки в строке S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!

Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.

Пароли выводятся в алфавитном порядке.
Подстрокой называется некоторая непустая подпоследовательность подряд идущих символов строки. Лексикографически максимальная подстрока это подстрока, стоящая на последнем месте в отсортированном по алфавиту списке всех подстрок исходной строки.

Формат входных данных

Программа получает на вход строку S. Длина S не более 15 символов. Строка записана строчными английскими буквами.

Формат выходных данных

Выведите в алфавитном порядке все варианты паролей для строки S. Каждый пароль выводится в отдельной строке.

Перестановки

✓ 34✗ 47800средняяВойти и решать

Алгоритм#27013

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

В первой строке ввода содержится два целых числа, разделенных пробелом - S (0 ≤ S ≤ 20000 ≤ S ≤ 2000) и P (0 ≤ P ≤ 10000000 ≤ P ≤ 1000000).

Вывести два целых числа I и J через пробел.

Ввод	Вывод
22 120	10 12

Простые задачи на перебор

✓ 34✗ 70800средняяВойти и решать

Школьные наборы#27000

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

Формат входных данных

В первой строке входного файла записано натуральное число N> (1<=N<<=100).

Формат выходных данных

Вывести искомое количество наборов.

Ввод	Вывод
2	3

Комбинаторика

✓ 21✗ 53800средняяВойти и решать

Палиндромы#26998

Вам дана строка символов, состоящая из заглавных букв латинского алфавита. Подсчитайте сколько различных палиндромов можно составить, меняя местами буквы этой строки. Палиндромом называется строка, которая одинаково читается как справа налево, так и слева направо. Например, “ABCBA” - палиндром, а “ABCDA” - нет.

Формат входных данных

В первой строке входного файла содержится непустая строка, состоящая из заглавных букв латинского алфавита. Её длина не превосходит 35 символов.

Формат выходных данных

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

Ввод	Вывод
ABCBA	2

Комбинаторика

✓ 5✗ 511 000средняяВойти и решать

Максимальное число делителей#26984

Напишите программу, которая по заданному числу n находит такое число от 1 до n, включительно, что оно имеет максимальное число положительных целых делителей. Например, если n = 15, то ответом на задачу будет число — 12, так как у него 6 делителей: 1, 2, 3, 4, 6 и 12.

Формат входных данных

Дано одно натуральное число n (1 ≤ n ≤ 100 000).

Формат входных данных

В первой строке выведите число из диапазона от 1 до n, включительно, которое имеет максимальное число делителей. Во второй строке выведите число его делителей. Если в диапазоне от 1 до n существует несколько чисел с максимальным числом делителей, то выведите любое из них.

Простые задачи на перебор Простые числа и разложение на множители

✓ 9✗ 133900средняяВойти и решать

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

Формат вывода

Выведите единственное натуральное число — количество различных путей наименьшей длины.

Пример

Ввод	Вывод
3	6

Динамическое программирование: один параметр Комбинаторика

✓ 22✗ 148900средняяВойти и решать

Легкая, вариант -2#24902

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: LDDLDDL, где символ L обозначает строчную латинскую букву, а D цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит второй блок цифр (цифры на позициях 5 и 6).

Филипп считает, что все номера в Берляндии уникальны, поэтому он хочет быстро подобрать все залитые цифры, так чтобы среди всех номеров не было двух одинаковых. Задача показалась ему нерешаемой, и он попросил вас помочь ему.

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

В первой строке записано натуральное число n, не превосходящее 1000 — количество номеров в стопке.

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

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

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

Первая строка должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входном файле.

Если ответов несколько — разрешается вывести любой.

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

Пример входных и выходных данных

Ввод	Вывод
4 a10a10c a30b??c a30b??c x70r??r	YES a10a10c a30b10c a30b22c x70r37r
3 a00b10c a00b10c c02y03x	NO
2 a99a??b a99a??b	YES a99a11b a99a22b

Задача на реализацию Простые задачи на перебор

✓ 24✗ 72900средняяВойти и решать

Orders#24733

Блейз отправляет приказы на перемещение своим войскам, собранным из жителей одной из теней. К сожалению, они не понимают амберский язык, поэтому Блейзу приходится отправлять им сообщения на их родном языке.
В этом и заключается проблема: Амберийский принц плохо знает орфографию этого языка, поэтому иногда он делает ошибки в словах, но не более одной ошибки в слове.
В языке очень много слов, поэтому если в слове изменится хотя бы одна буква, то его смысл может кардинально измениться. Если армия не правильно поймет приказ, то вся военная кампания может провалиться. Поэтому Блейзу очень важно проверять правильность в написании слов. Он решил попросить вас помочь ему.
Вы должны создать программу, которая будет выводить в лексикографическом порядке все возможные слова, которые Блейз мог пытаться написать с учетом того, что он мог ошибиться 1 раз.

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

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

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

Бор Обход в глубину Перебор

✓ 7✗ 241 100средняяВойти и решать

Перестановки с другим началом (С', С)#23336

Перестановкой размера n называется упорядоченный набор из n чисел, в котором каждое число от 1 до n встречается ровно один раз. Например, (4, 2, 3, 5, 1) - это перестановка размера 5.

Нам дано число n и последовательность a, в которой k натуральных чисел.

Вычислите, сколько существует перестановок размера n, которые не начинаются на данную последовательность.

Формат входных данных

В первой строке содержатся два натуральных числа n и k (1 <= n <= 9, 1 <= k <= 100) .

Во второй строке содержатся k натуральных чисел, составляющие последовательность a. Каждое из этих чисел не превышает 100.

Формат выходных данных

Выведите количество перестановок размера n- которые не начинаются на данную последовательность a.

Ввод	Вывод
3 2 2 1	5
5 2 4 4	120
5 6 2 3 9 5 6 6	120

Комбинаторика

✓ 34✗ 63800средняяВойти и решать

Число способов#22015

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

Посчитайте, сколько есть способов у игрока попасть в правую

нижнюю клетку.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,

1<=M<=10).

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

В выходной файл запишите искомое число способов.

Примечание

При указанных ограничениях, число способов входит в тип Longint.

Пример входного файла

2 3

Пример выходного файла

Пояснение

Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие

способы попасть из левого верхнего угла в правый нижний:

1) вниз, вправо, вправо

2) вправо, вниз, вправо

3) вправо, вправо, вниз

Еще один пример входного файла

3 3

Пример выходного файла

Динамическое программирование на таблицах Динамическое программирование: один параметр Комбинаторика

✓ 21✗ 29800средняяВойти и решать

21946#21946

Графическое изображение, показывающее соотношение каких-либо величин называется

1. графиком
2. таблицей
3. картинкой
4. диаграммой

Комбинаторика

1 000средняяВойти и решать

Троллейбусы#18728

Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<=500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.

Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы:

1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.

2) Максимальное из времен ожидания троллейбуса было минимально.

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

В строке записано сначала число k, затем - число N (0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров

на остановку. Каждое из этих чисел - целое от 0 до 100000.

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

Запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно.

Если решений несколько, выведите любое из них.

Примеры

№	Входные данные	Выходные данные
1	100 5 0 210 99 551 99	10 51

Вложенные циклы Простые задачи на перебор

✓ 13✗ 561 000средняяВойти и решать

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7