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

Петя нарисовал на бумаге 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

Дана функция \(z(x) = ax^3 + bx^2 + cx + d\). Для заданных чисел a, b, c и d, выведите все целые значения x из диапазона от 0 до 1000, при которых функция z(x) принимает нулевое значение.

Входные данные
Программа получает на вход 4 числа: a, b, c и d. Каждое число записано в отдельной строке.

Выходные данные
Выведите все значение x, которые удовлетворяют условию задачи в порядке возрастания. 
 

Примеры

№	Входные данные	Выходные данные
1	1 -5 6 0	0 2 3

Вам дана строка 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

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований ученые пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать…
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык — язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции — сложение, умножение и вычитание (марсиане никогда не использовали “унарный минус”: вместо “–5” они писали “0–5”). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3 + 3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью “18=7 (5 3) 2”, то возможна такая расстановка знаков: “18=7+(5–3)*2” (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью “5=3 3”, то марсиане явно не имели в виду числового равенства, когда писали это…
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа “–1”. Выходная строка не должна содержать пробелов.
 

Примеры

№	Входные данные	Выходные данные
1	18=7 (5 3) 2	18=7+(5–3)*2
2	5= 3 3	-1

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

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

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

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

Примеры

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

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2385177; 2385437] простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку (каждое число с номером выводите с новой строки). 

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

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

Ввод	Вывод
1311	2949

Входные данные 
Входная строка содержит четыре числа, разделённые пробелами: a , b , c и N .

Выходные данные 
В первой строке нужно вывести число K способов, которыми можно купить заданное количество мастики (N кг), не вскрывая ящики. В каждой из последующих K строчек программа должна вывести (через пробелы) три числа, ka , kb и kc : количество ящиков 1, 2 и 3 типов для каждого из K вариантов закупки. Варианты должны выводиться в лексикографическом порядке: сначала варианты с наименьшим значением ka , для одинаковых ka – сначала варианты с наименьшим значением kb и т.д.

 

Примеры

№	Входные данные	Выходные данные
1	15 17 21 185	5 0 1 8 1 10 0 3 7 1 5 4 2 7 1 3

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [102438; 124698] числа, у которых ровно 7 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 7 делителей с новой строки в порядке возрастания произведения этих 7 делителей. Делители должны следовать в порядке возрастания.

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [108933; 132757] числа, у которых ровно 2 различных натуральных делителя, не считая 1 и самого числа. Для каждого найденного числа выведите эти 2 делителя с новой строки в порядке возрастания произведения этих 2 делителей. Делители должны следовать в порядке возрастания.

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [289039; 311993] числа,  у которых ровно 8 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 8 делителей с новой строки в порядке возрастания суммы этих 8 делителей. Делители должны следовать в порядке возрастания.

Примеры

№	Входные данные	Выходные данные
1	2	11 10 01 00

Ввод	Вывод
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