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

В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из n цифр, каждая цифра может принимать b различных значений от 0 до b − 1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому-то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.

Формат входных данных
Первая строка входных данных содержит число b — количество различных значений одной цифры кода, 2 ≤ b ≤ 10. Вторая строка содержит число n — количество цифр в коде, n \(\geq\) 1, bⁿ ≤ 60 000. Третья строка содержит число t – количество имеющихся донесений о сумме каких-то цифр кода, t \(\geq\) 1.
Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит n символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих в коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях. Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям.

Формат выходных данных
Программа должна вывести одно целое число — количество различных кодов, которые удовлетворяют всем донесениям.

Замечание
В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7, код состоит из 3 цифр. Получены 2 донесения, из первого донесения известно, что сумма первой и второй цифры кода равна 7, из второго донесения известно, что сумма второй и третьей цифры кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».

Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа \(n\) в виде суммы \(k\) слагаемых.

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

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

Формат входных данных
Первая строка ввода содержит число \(n\) (\(-15\le n \le 15\)).

Вторая строка содержит число \(k\) (\(1 \le k \le 15\)).

Гарантируется, что общее число представлений не превышает \(10^5\).

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

Дед Мороз решил проверить фабрику игрушек, все ли подарки для детей готовы. Чтобы дойти до места хранения игрушек, ему необходимо пройти по узкому секретному коридору. В коридоре на каждом метре пути указано число метров от двери. У двери, возле которой стоит Дед Мороз, записано число 0. По коридору можно двигаться как влево, так и вправо. При движении влево числа отрицательные, при движении вправо - положительные.

Так как место засекречено, завод постоянно меняет вход в хранилище игрушек. 

Дед Мороз знает, что вход в фабрику сегодня расположен у двери с числом X. Также известно, что в коридоре, рядом с числом Y находится дверь, перекрывающая проход по коридору. Чтобы ее открыть необходимо взять ключ, который располагается на стене на полке в коридоре рядом с числом Z.

Определите сможет ли Дед Мороз сам добраться до двери к игрушкам. Если сможет, определите минимальное расстояние, которое необходимо будет пройти Деду Морозу. Если не сможет, то выведите -1.

Входные данные
Программа получает на вход строку, содержащую 3 различных ненулевых числа: X, Y, Z (-10³ <= X, Y, Z <= 10³).

Выходные данные
Выведите минимальное расстояние, которое необходимо пройти Деду Морозу от двери, у которой он стоит, до двери, за которой расположено место хранения игрушек. Если Дед Мороз не сможет добраться до этой двери, выведите -1.
 
 

Примеры

№	Входные данные	Выходные данные
1	10 -10 1	10
2	20 10 -10	40
3	100 1 1000	-1

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	6 4 2 aaaaaa bbbb	aabaabaa

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

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

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

Входные данные
В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно (1 ≤ n ≤ 1 000, 0 ≤ m ≤ 20 000).
Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).
Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.

Выходные данные
Выведите  одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите  слово "Impossible''.
 

Примеры

№	Входные данные	Выходные данные
1	4 5 RRRG 1 3 1 4 3 4 2 4 2 3	BBGR
2	4 5 RGRR 1 3 1 4 3 4 2 4 2 3	Impossible

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака + подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	125	176	Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5. Результат после вычисления каждой формулы: 125 1 + 25 = 26 12 + 5 = 17 1 + 2 + 5 = 8 Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2	9999999999	12656242944

 

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

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

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Примеры

№	Входные данные	Выходные данные
1	5 0 1 9 9 2 1 0 9 9 9 9 9 0 9 9 9 9 9 0 9 2 9 9 9 0	1 2 5

Представьте данное число n в виде суммы двух кубов.

Входные данные
Программа получает на вход одно натуральное число n (n <= 1028).

Выходные данные
Программа должна вывести 2 целых неотрицательных числа (в порядке убывания), сумма кубов которых равна n. Если это невозможно, выведите строку impossible.
 

Примеры

№	Входные данные	Выходные данные
1	9	2 1
2	3	impossible

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу n найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Входные данные
Программа получает на вход одно натуральное число n < 10000.

Выходные данные
Программа должна вывести от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Примеры

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

У Пети имеется игровое поле размером 3x3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

Входные данные
Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

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

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 5 6 7 8 9	987456321

Андрей готовился к ЕГЭ по информатике и встретил в демо-версии ЕГЭ 2015 года такую задачу:
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3+1 = 4; 6+5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1311.
Андрей решил, что для самопроверки он напишет программу, которая решает подобную задачу. Мы думаем, что вы тоже с этим справитесь.
Программа получает на вход некоторое натуральное число N, которое может содержать две, три или четыре цифры.

Программа должна вывести такое наименьшее целое четырёхзначное число K, после применения к которому описанного выше алгоритма получается число N. Если же такого числа не существует, программа должна вывести число 0.
 

Ввод	Вывод
1311	2949

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

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

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

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: 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

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