Перебор

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

1. Ровно одна корова была инфицирована изначально (нулевой пациент).
2. После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
3. Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.
 

Примеры

№	Входные данные	Выходные данные
1	4 3 1100 7 1 2 5 2 3 6 2 4	1 1 Infinity

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1]  является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\)   и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 100\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

Выходные данные
Выведите одно целое число: минимальное возможное расстояние от исходной до гармоничной последовательности.
 

Примеры

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

Вечером она решила поискать существующие пифагоровы тройки, но забыла формулу. В итоге вместо правильного критерия она использовала следующий: c = a2 - b.
Вскоре Бельвита опознала ошибку, однако по ее критерию нашлись такие тройки чисел, что они действительно являлись пифагоровыми.
Это заинтересовало Бельвиту и она решила посчитать количество троек целых чисел (a, b, c) таких, что  1 <= a, b, c <= n и они подходят и под настоящую формулу пифагоровых троек, и под ошибочную.
Посчитайте и вы.

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 10⁹).

Выходные данные
Выведите одно число - количество троек целых чисел (a, b, c) таких, что они подходят под оба критерия.

 

Примеры

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

В чулане у Бельвиты имеется n наборов табличек, каждый из которых содержит по 3 одинаковых таблички, на которых записано ровно две строчные латинские буквы. Бельвите не принципиально как именно будет называться ее пекарня, однако она хочет, чтобы в итоговом названии содержалась подстрока s, которая тоже состоит из двух строчных латинских букв.
Помогите Бельвите понять, можно ли выбрать некоторые из имеющихся табличек и составить из них название пекарни, чтобы оно содержало необходимую подстроку.

Входные данные
Первая строка содержит две строчные латинские буквы - строка s, которую Бельвита хочет видеть в названии пекарни. Вторая строка содержит одно целое число n (1 <= n <= 100) - количество наборов табличек в чулане. Следующие n строк содержат по две строчные латинские буквы каждая, описывающие надписи на табличках в наборах.

Выходные данные
Выведите «YES», если Бельвита может выбрать несколько табличек так, чтобы в получившемся слове была подстрока s, и «NO» иначе.
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	ya 4 ah oy to ha	YES	Можно использовать третий, второй и первый набор, составив слово "tooyah", в котором есть подстрока "ya".
2	hp 2 ht tp	NO	Получить слово с подстрокой "hp" никак нельзя.
3	ah 1 ha	YES	Можно использовать две из трех табличек первого набора, составив слово "haha", где есть подстрока "ah".

 

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

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).

 

Примеры

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

 

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

Перестановкой n элементов называется массив из различных натуральных n чисел, каждое из которых от 1 до n. Например, все перестановки 3 элементов: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Элементы перестановки пронумерованы от 1 до n, например для перестановки a = [3, 1, 2] выполнено a[1] = 3, a[2] = 1, a[3] = 2. Элемент с номером i называется неподвижной точкой, если a[i] = i. Так, в перестановке [3, 1, 2] нет неподвижный точек, а в перестановке [1, 3, 2] элемент a[1] = 1 является неподвижной точкой.
Упорядочим все перестановки лексикографически — сначала по первому элементу, потом по второму, и так далее. В начале условия все перестановки трех элементов приведены в лексикографическом порядке. Оставим только те перестановки, которые не содержат неподвижных точек. Для n = 3 останутся перестановки [2, 3, 1] и [3, 1, 2].
По заданным n и t требуется вывести первые t в лексикографическом порядке перестановок n элементов без неподвижных точек. Перестановки следует выводить в лексикографическом порядке.

Входные данные
На ввод подаются два целых числа n и t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 10⁴, nt ≤ 10⁵ ). Гарантируется, что существует хотя бы t перестановок n элементов без неподвижных точек.

Выходные данные
Выведите t строк, на i-й из них выведите n чисел: i-ю в лексикографическом порядке перестановку n элементов без неподвижных точек.

Примеры

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

Дана функция \(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

Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть 3N + M + K возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10⁹ +7).

Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10⁵).

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10⁹ +7).

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 1 1	17	Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9. Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4. Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4. Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина.
2	4 2 2	1227
3	1000 1000 1000	261790852

 

Вам дана строка 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 N-1 ... 3 2 1 следует тождественная перестановка, то есть, 1 2 3 ... N).

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Требуется вывести искомую перестановку.

Примеры

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

Найдите перестановку по её номеру в лексикографическом порядке.

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 12) – количество элементов в перестановке, во второй – число K (1 <= K <= N!) – номер перестановки.

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

Примеры

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

На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос.

Входные данные
Вводится слово, составленное Петей – строка из маленьких латинских букв не длиннее 15 символов.

Выходные данные
Выведите одно целое число – искомое количество слов.
 

Примеры

№	Входные данные	Выходные данные
1	solo	12

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

Выходные данные
Выведите одно число - количество способов выбрать такие печеньки, чтобы среднее значение всех записанных чисел на печеньках было ровно A.
 

 

Примеры

№	Входные данные	Выходные данные	Примечение
1	4 8 7 9 8 9	5	Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8. 1) Выберите 3-ю печеньку. 2) Выберите 1-ю и 2-ю печеньки. 3) Выберите 1-ю и 4-ю печеньки. 4) Выберите 1-ю, 2-ю и 3-ю печеньки. 5) Выберите 1-ю, 3-ю и 4-ю печеньки.
2	3 8 6 6 9	0
3	8 5 3 6 2 8 7 6 5 9	19
4	33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3	8589934591	Ответ может не соответствовать 32-битному целому числу.

 

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

В городе 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

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

Входные данные
Задано единственное число N. (N ≤ 40)

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

Примеры

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

Имеется сетка из N строк и N столбцов квадратов. Пусть (i, j) индексы клетки, которая расположена в i-й строке сверху и j-м столбце слева. Эти клетки должны быть окрашены в один из цветов C от цвета 1 до цвета C. Первоначально (i, j) окрашен в цвет ci,j. Назовем сетку хорошей, когда выполняются следующие условия для всех i, j, x, y, удовлетворяющих \(1<=i,j,x,y<=N\):
- если \((i+j)\%3=(x+y)\%3\), цвет (i, j) и цвет (x, y) совпадают;
- если \((i+j)\%3\neq(x+y)\%3\), цвет (i, j) и цвет (x, y) различны.
Здесь \(X \% Y \) представляет X по модулю Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет X до перерисовки и Y после перекраски (DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.

Входные данные
В первой строке задаются два целых числа N и C. В следующих C строках задаются по C значений Di,j. В последних N строках записаны N чисел в каждой строке - ci,j.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 0 1 1 1 0 1 1 4 0 1 2 3 3	3	Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j  \neq D j, i \).
2	4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2	428

 

Есть N человек. Имя i-го человека - Si . Мы хотим выбрать трех человек, чтобы выполнялись следующие условия:
- имя каждого выбранного человека начинается с M, А, R, С или Н; 
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?

Входные данные
В первой строке записано целое число N (\(1<=N<=10^5\)) В следующих N строках записаны имена Si - строка, состоящая только из английских заглавных букв, длина строки не более 10 символов. Все имена различные.

Выходные данные
Выведите ответ на задачу. Обратите внимание, что ответ может не соответствовать 32-битному целочисленному типу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 MASHIKE RUMOI OBIRA HABORO HOROKANAI	2	Трех людей можно выбрать такими способами: - MASHIKE, RUMOI, HABORO - MASHIKE, RUMOI, HOROKANAI Ответ: 2
2	4 ZZ ZZZ Z ZZZZZZZZZZ	0
3	5 CHOKUDAI RNG MAKOTO AOKI RINGO	7