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

Скобки(2)#55113

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.

Входные данные
В первой строке находится единственное число N. 1 <= N <= 14, N - чётное.

Выходные данные
Каждое выражение выводится в отдельной строке, порядок вывода последовательностей произвольный.

Перебор Стек

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

Двоичные числа#54706

Найдите количество чисел Z, удовлетворяющих неравенству A ≤ Z ≤ B, таких, что в записи Z
в двоичной системе счисления используется ровно 2 единицы. Например, если A=10; B=20; то таких чисел 5 (это числа 10=1010₂; 12=1100₂; 17=10001₂; 18=10010₂; 20=10100₂).

Входные данные
На вход программы поступают два числа, записанных через пробел — A, B ( 0 ≤ A, B ≤ 10⁹)

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

Перебор

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

Хардсофт#50835

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайнподпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы.
Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.
Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них.
Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

Формат входных данных
в первой строке через пробел указаны натуральные числа N, M и X. N и M не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а X не превышает 10⁶ и является количеством памяти (в килобайтах), доступным для размещения инлайнподпрограмм. Далее идёт N строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - M строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).
Формат выходных данных
в первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных. Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным.

Задача о рюкзаке Перебор

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

Простое произведение#50347

Натуральное число \(p\) называется простым, если оно имеет ровно два различных делителя: \(1\) и \(p\). Например, числа \(2\), \(3\), \(5\) являются простыми. Число \(1\) простым не считается.

Целое число \(p\) будем называть квазипростым, если \(p\) или \(-p\) является простым. Например, числа \(-2\), \(2\), \(-3\), \(3\), \(-5\), \(5\) являются квазипростыми.

Хотя любое натуральное число можно единственным образом представить в виде произведения простых, для целых чисел и квазипростых это уже неверно. Например, число \(12\) можно тремя способами представить в виде произведения квазипростых: \(12=2\cdot 2\cdot 3\), \(12=(-2)\cdot 2\cdot (-3)\), \(12=(-2)\cdot (-2)\cdot 3\).

Задано целое число \(n\). Выведите все способы представить \(n\) в виде произведения квазипростых. Произведения, которые отличаются только порядком множителей, считаются одним способом.

Формат входных данных
На первой строке ввода находится число \(n\) (\(-10^9 \le n \le 10^9\), \(n \ne 0\), \(n \ne \pm 1\)).

Формат выходных данных
На первой строке выведите \(k\) — количество способов представить \(n\) в виде произведения квазипростых. В следующих \(k\) строках выведите все способы представить \(n\) в виде произведения квазипростых. Произведения можно выводить в любом порядке, множители в каждом произведении можно выводить в любом порядке.

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

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

Сумма#50342

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

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

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

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

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

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

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

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

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

Вордл наоборот#48935

Камила и Динара играют в <<Wordle>>. Камила загадала слово длины \(n\), состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины \(n\), также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:

Буква, совпадающая с буквой в загаданном слове, красится в зеленый цвет и обозначается G.
Буква, которая присутствует в загаданном слове, но стоит не своей позиции, красится в жёлтый цвет и обозначается Y.
Буква, отсутствующая в загаданном слове, красится в белый цвет и обозначается W.

Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.

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

В первой строке вводится одно целое число \(n\) \((1 \le n \le 10)\) — длина загаданного слова.

Во второй строке вводится строка длины \(n\), состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.

В третьей строке вводится строка длины \(n\), состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.

Если подходящих слов не существует, выведите No.

Если хотя бы одно подходящее слово существует, в первой строке выведите Yes, во второй — любое подходящее слово.

Разберем первый пример из условия.

Буквы H и G не встречаются в загаданном слове, поэтому они белые.

Буквы E и B встречаются, но на других позициях, поэтому они жёлтые

Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.

Есть и другие ответы, любой правильный ответ будет зачтен.

Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.

Задача на реализацию Перебор Строки

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

XOR-cумма массива#47936

XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums.

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз.
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.

Входные данные
Программа получает на вход в первой строке натуральное число n - количество элементов массива nums. Во второй строке записаны n чисел nums_i.

Ограничения

1 <= n <= 12
1 <= nums_i <= 20

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

Пояснения к тестовым примерам
В первом примере
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Перебор с возвратом Рекурсия

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

Добраться до игрушек#44034

Дед Мороз решил проверить фабрику игрушек, все ли подарки для детей готовы. Чтобы дойти до места хранения игрушек, ему необходимо пройти по узкому секретному коридору. В коридоре на каждом метре пути указано число метров от двери. У двери, возле которой стоит Дед Мороз, записано число 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

Простые задачи на перебор Условный оператор

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

Мишины кубики#43718

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши 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

"Два указателя"Жадный алгоритм Задача на реализацию Использование сортировки Простые задачи на перебор

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

Xor-пути в матрице#39836

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел a_i,j, где j-й элемент i-й строки равен a_i,j (0 <= a_i,j <= 10¹⁸).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

meet in the middle Перебор

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

Гекльберри Финн и две строки#39674

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.

Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:

Входные данные	Выходные данные
3 wai add	1
5 qdyid xreac	0

Перебор Префиксные суммы(минимумы, ...)Хеш

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

Танцевальные движения#39575

Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10⁵) стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся K (1≤K≤2⋅10⁵) парами позиций (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Каждую минуту i=1…K танца коровы на позициях a_i и b_i меняются местами. Такие же K обменов делаются на минутах K+1…2K, затем опять на минутах 2K+1…3K, и т.д. Другими словами,

на минуте 1 меняются местами коровы на позициях a₁ и b₁.
на минуте 2 меняются местами коровы на позициях a₂ и b₂.
...
На минуте K меняются местами коровы на позициях a_K и b_K swap.
На минуте K+1, меняются местами коровы на позициях a₁ и b₁.
На минуте K+1, меняются местами коровы на позициях a₂ и b₂.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a₁,b₁)…(a_K,b_K) (1≤a_i<b_i≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 4 1 3 1 2 2 3 2 4	4 4 3 4 1	Корова 1 достигнет позиций {1,2,3,4}. Корова 2 достигнет позиций {1,2,3,4}. Корова 3 достигнет позиций {1,2,3}. Корова 4 достигнет позиций {1,2,3,4}. Корова 5 не будет двигаться, и не покинет позицию 5.

Обход в глубину Перестановки

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

Фотография коров#39570

Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из N * N ячеек (как шахматная доска размером N×N) (2≤N≤1000). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:
Никакие две коровы не могут находится в одной и той же ячейке.
Каждая подрешётка размером 2×2 (всего таких подрешёток (N−1)×(N−1)) должна содержать ровно 2 коровы
Например, такое размещение соотвествует правилам:

CCC
...
CCC
А такое размещение - нет

C.C
.C.
C..
поскольку 2×2 регион в правом нижем углу содержит только одну корову.
Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.

Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает. что если корова размещена в ячейке (i,j), красота фотографии увеличивается на a_ij (0≤a_ij≤1000) единиц.

Определите максимально возможную красоту корректного размещения коров.

Входные данные
Первая строка содержит число N. Каждая из следующих N строк содержит по N целых чисел. j-ое число в i-ой строке сверху есть значение a_ij.
Выходные данные
Выведите одно целое число - максимально возможную красоту результирующего фото.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3	22	В этом примере максимальная красота может быть достигнута следующим размещением: CC.. ..CC CC.. ..CC Красота этого размещения 3+3+3+1+3+3+3+3=22.

Перебор

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

Коровий алфавит#39561

Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

По заданной строке букв, которые ФД расслышал из бормотания Беси, определите минимальное количество раз, которое Беси должна пробормотать cowphabet, чтобы ФД услышал заданную строку. ФД не всегда обращает внимание на бормотание Беси, поэтому он может не расслышать некоторые буквы из бормотания Беси. Данная Вам строка содержит только те буквы, которые он услышал.

Входные данные
Первая строка ввода содержит 26 маленьких латинских букв от 'a' до 'z' в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.
Выходные данные
Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	abcdefghijklmnopqrstuvwxyz mood	3	В этом примере cowphabet упорядочен как нормальный алфавит. Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, и большими буквами - какие буквы услышал ФД. abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz

Перебор Строки

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

Треугольники#39517

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

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

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

Гармоничная последовательность lite - 1#39386

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

Профессор называет последовательность целых чисел \(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

Перебор

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

Бельвита и пифагоровы тройки#39366

Сегодня Бельвита узнала про пифагоровы тройки. Если вы вдруг не знали, то это тройка целых чисел (a, b, c) таких, что можно образовать прямоугольный треугольник с длинами первого катета, второго катета и гипотенузы, равными a, b и c соответственно. Более формально, должно выполняться, что a² + b² = c².

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

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

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

Примеры

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

Перебор

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

До Нового года - 1#38928

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

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

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

Примеры

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

Комбинаторика Циклы

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

Раскраска в три цвета#38919

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

Обход в глубину Простые задачи на перебор

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

Без неподвижных точек#38876

Перестановкой 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

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

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