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

Множество формул#38653

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

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

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

По номеру#38636

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

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

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

Примеры

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

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

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

Числовые печеньки - 2#38634

У Громозеки 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-битному целому числу.

Динамическое программирование Комбинаторика

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

Издевательство#38632

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

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

Простые задачи на перебор Способы задания графа

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

Сумма двух кубов#38620

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

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

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

Примеры

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

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

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

Теорема Лагранжа#38618

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

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

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

Примеры

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

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

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

Разбиение на невозрастающие слагаемые, лексикографический порядок#38609

Дано натуральное число 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

Разбиения Рекурсия

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

Март#38588

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

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

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

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

Конфеты и коробки#38505

В ряд расположены N ящиков. Изначально в i-м ящике слева находится a_i конфет. Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и x (\(0<=x<=10^9\)). Во второй строке содержится N целых чисел a_i(\(0<=a_i<=10^9\)).

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 2 2	1	Необходимо съесть одну конфету во второй коробке. Тогда количество конфет в каждой коробке станет (2,1,2).
2	6 1 1 6 1 2 0 4	11	Например, можно съесть шесть конфет во второй коробке, две в четвертой и три в шестой. Тогда количество конфет в каждой коробке станет (1,0,1,0,0,1).
3	5 9 3 1 4 1 5	0	Цель уже достигнута
4	2 0 5 5	10	Все конфеты должны быть съедены.

Одномерные массивы Перебор Цикл for

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

Взвешивание#38318

Даны двухчашечные весы и набор гирек. На левую чашу весов положили взвешиваемый предмет весом K граммов. Можно ли привести весы в состояние равновесия, и если можно, то определите для каждой чаши весов, какие гирьки на нее для этого нужно положить. Имеющиеся гирьки разрешается класть на любую из чаш весов (каждая гирька имеется только в одном экземпляре, некоторые гирьки можно не использовать).

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

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

Примеры

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

Перебор Рекурсия

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

Квас#38313

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

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

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

Входные данные
Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 5 3 10	3
2	6 4 4 1 5 1 3	2	На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком. Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 52 + 32 (в 4-й и 6-й) + 13 (в 5-й см. рисунок). Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 32 + 42 + 43 = 28 тугриков.

Обход в ширину Перебор

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

Ставки#38309

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".

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

Входные данные
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Примеры

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

Примечание: Решения задачи на языке программирования Python не проходят ограничения по времени.

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

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

Преферанс#38239

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

Каждый игрок похвастал, сколько у него тузов. Определите, сколько игроков заведомо солгали.

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

Входные данные
Вводятся 4 числа (от 0 до 9 каждое), разделенных пробелом – количество тузов по словам первого, второго, третьего и четвертого игроков.

Выходные данные
Выведите одно число – минимальное количество игроков, которые заведомо солгали. Если все одновременно могли сказать правду, выведите число 0.

Примеры

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

Перебор Циклы

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

Разложение на простые множители#38215

Разложение на простые множители числа 12 можно записать тремя способами:

12=2·2·3=2·3·2=3·2·2

А сколькими способами можно записать разложение на простые множители числа N?

Входные данные
Вводится одно натуральное число N (2 <= N <= 1 000 ).

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

Примеры

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

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

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

Будильники#38210

Будильник в сотовом телефоне можно настроить так, чтобы он звонил каждый день в одно и то же время, либо в указанное время в определенный день недели. Независимо можно настроить несколько будильников.

По информации о будильниках и текущему времени и дню недели определите, когда прозвонит очередной будильник.

Входные данные
В первой строке вводятся три числа, задающие текущее время: день недели (от 1 до 7), часы и минуты.

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

В следующих N строках вводятся описания N будильников. Описание каждого будильника состоит из трех чисел: дня недели (число от 1 до 7 для понедельника, …, воскресенья, соответственно, 0 – если будильник должен звонить каждый день), часов (от 0 до 23), минут (от 0 до 59).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 10 20 2 1 23 15 0 10 10	3 10 10
2	7 1 1 3 7 0 59 7 23 59 7 1 1	7 1 1	Во втором примере третий будильник будет звенеть в начальный момент времени.

Дата и время Одномерные массивы Перебор Условный оператор

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

Максимальная прибыть (ТЯжелая - 1, дубль 24755)#34958

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Перебор

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

Задача из ЕГЭ#34848

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

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

Ввод	Вывод
1311	2949

Задача на реализацию Простые задачи на перебор

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

Монетки#31794

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

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

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30

Рекурсивный перебор Рекурсия

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

Palindromic Paths#28324

Ферма Джона представлена решёткой из N×N полей(2≤N≤18), каждое из которых помечено буквой алфавита. Например,

ABCD

BXZX

CDXB

WCBA

Каждый день корова Беси идёт с левого верхнего угла в правый нижний, двигаясь либо на одну клетку вправо, либо на одну клетку вниз. Беси записывает строку, которая получается в результате её маршрута, построенную из букв, по которым она прошла. Он будет очень расстроена, если в результате построенная строка окажется палиндромом (читается одинаково от начала к концу и от конца к началу), поскольку она запутается в каком направлении она шла.

Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

ФОРМАТ ВВОДА :

Первая строка ввода содержит N, а последующие N строк содержат N описание поля. Каждая строка содержит по N символов в диапазоне A..Z.

ФОРМАТ ВЫВОДА :

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

Ввод	Вывод
4 ABCD BXZX CDXB WCBA	4

meet in the middle Перебор

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

Бесси поквиталась#28322

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

Беси даёт ФД выражение (B+E+S+S+I+E)(G+O+E+S)(M+O+O), содержащее семь переменных B,E,S,I,G,O,M ( "O" это переменная, а не 0). Для каждой переменной она даёт ФД список до 20 целых чисел, которые эта переменная может принять. Беси просит ФД посчитать количество различных способов назначить значения переменным, чтобы вычисленное выражение было чётным числом.

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

Первая строка ввода содержит целое число N. Каждая из N следующих строк содержит переменную и возможное значение для этой переменной. Каждая переменная появится в этом списке не менее одного раза и не более 20 раз. Для одной и той же переменной все задаваемые значения различны. Все значения находятся в диапазоне от −300 до 300.

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

Выведите единственное целое число, задающее количество способов, которыми ФД может назначить значения переменным, чтобы выражение давало чётный результат.

Ввод	Вывод
10 B 2 E 5 S 7 I 10 O 16 M 19 B 3 G 1 I 9 M 2	6

Всего имеется 6 подходящих вариантов назначения переменным значений:

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
                = (2, 5, 7, 10, 1, 16, 2 ) -> 35,496
                = (2, 5, 7, 9,  1, 16, 2 ) -> 34,510
                = (3, 5, 7, 10, 1, 16, 2 ) -> 36,482
                = (3, 5, 7, 9,  1, 16, 19) -> 53,244
                = (3, 5, 7, 9,  1, 16, 2 ) -> 35,496

Заметим, что (2,5,7,10,1,16,19) и (3,5,7,9,1,16,19) рассматриваются как различные назначения, несмотря на то, что они дают одинаковый результат.

Перебор

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