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

Карточки#38635

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

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

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

Примеры

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

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

✓ 20✗ 38600лёгкаяВойти и решать

Алмазные Черепашки#38587

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

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

Простые задачи на перебор Цикл for

✓ 18✗ 26600лёгкаяВойти и решать

Раскраска кеглей#38499

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

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

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

Примеры

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

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

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

Буквы по кругу#38237

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

Входные данные
В первой строке записаны строчные латинские буквы в том порядке, в котором они расставлены по кругу по часовой стрелке. Буквы записаны без пробелов, их количество не меньше 1 и не больше 100.

Во второй строке записано слово, которое хочет найти Петя. Оно также состоит из строчных латинских букв и имеет длину от 1 до 100.

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

Примеры

№	Входные данные	Выходные данные
1	abcdefg abd	NO
2	abcdg bag	YES
3	a aaa	YES

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

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

Список простых - 01#38234

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

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

✓ 31✗ 36500лёгкаяВойти и решать

Тапочки#38204

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

Входные данные
Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.
Выходные данные
Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.

Примеры

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

Перебор

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

Сдача#34764

Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль.

Например, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Входные данные
На вход программе подается натуральное число n <= 100 — размер сдачи, которую необходимо выплатить.

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

Примеры

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

Вложенные циклы Задачи на моделирование Комбинаторика

✓ 2 048✗ 3 154500лёгкаяВойти и решать

*Мастика#34763

В магазине продается мастика в ящиках по a кг (тип 1), b кг (тип 2) и c кг (тип 3). Как купить ровно N кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?

Входные данные
Входная строка содержит четыре числа, разделённые пробелами: 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`

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

✓ 1 520✗ 3 488700средняяВойти и решать

Число сочетаний#33679

По данным числам n и k (0<=k<=n) вычислите \(С_n^k\) . Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\).

Решение оформите в виде функции C(n, k).

Входные данные: Вводятся целые числа n и k.

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

Примеры

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

Задачи на процедуры и функции Комбинаторика Рекурсия

✓ 2 901✗ 4 898400лёгкаяВойти и решать

Список делителей - 04#33368

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

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

✓ 109✗ 230600лёгкаяВойти и решать

Список делителей - 03#33367

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

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

✓ 116✗ 175600лёгкаяВойти и решать

Список делителей - 02#33366

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

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

✓ 128✗ 233600лёгкаяВойти и решать

Расчет асимптотики - 2#31797

Для приведенного ниже кода, найдите асимптотику:

int n;
vector <int> arr(n);
next_permutation(arr.begin(), arr.end());

1) O(n!) 2) O(n) 3) O(1) 4) O(nlogn)

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

500лёгкаяВойти и решать

Точки на прямой#28417

Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.

Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

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

Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 10⁹ — x-координаты точек, подаренных Пете.

Гарантируется, что координаты точек во входных данных строго возрастают.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Ввод	Вывод
4 3 1 2 3 4	4
4 2 -3 -2 -1 0	2
5 19 1 10 20 30 50	1

В первом примере нам подходит любая тройка различных точек.

Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.

В третьем примере нам подходит одна тройка: {1, 10, 20}.

"Два указателя"Комбинаторика

✓ 354✗ 711600лёгкаяВойти и решать

Количество сочетаний - 2#27317

По данным числам n и k (\(0 <= k <= n\), \(0< n<=60\)) вычислите количество сочетаний \(C_n^k\).

Примеры

№	Входные данные	Выходные данные
1	3 21	1330

Сочетания

✓ 84✗ 112600лёгкаяВойти и решать

Количество сочетаний#27316

По данным числам n и k (\(0 <= k <= n\), \(0< n<=12\)) вычислите количество сочетаний \(C_n^k\).

Примеры

№	Входные данные	Выходные данные
1	2 8	28

Сочетания

✓ 129✗ 128600лёгкаяВойти и решать

Шахматная доска#27315

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

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

Во входном файле записаны натуральные числа N и K (\(1 <= N, K <= 8\)).

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

В выходной файл выведите одно целое число - ответ задачи.

Примеры

№	Входные данные	Выходные данные
1	8 8	40320

Сочетания

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

Разность#27314

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

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

На вход подаётся одно число - N (\(1 <= N <= 10\))

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

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

Примеры

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

Комбинаторные структуры

✓ 71✗ 40500лёгкаяВойти и решать

Количество чисел Каталана#27313

Вывести N-ное число Каталана

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

Первая строка входных данных содержит одно число N (\(1 <= N <= 20\)).

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

Выведите одно число - N-ное число Каталана

Примеры

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

Комбинаторные структуры

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

Двоичные строки заданной длины#27089

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

Входные данные
Задано единственное число N (натуральное, \(1 <= N <= 10\))

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

Примеры

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

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

✓ 124✗ 56600лёгкаяВойти и решать