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

Сумма чисел в массиве#33724

Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от a_i до a_j включительно будет максимальна. Индексация элементов начинается с 1.

Входные данные
В первой строке задается натуральное число n <= 100000 — количество элементов в массиве. В следующих n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.

Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным. В первой строке выведите i, во второй - j.

Примеры

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

Алгоритмы обработки Динамическое программирование: один параметр

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

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

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

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

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

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

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

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

Ввод	Вывод
2 30 7 20 80	7

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

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

Копилка#33105

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и F (1 <= E <= F <= 10000). Во второй - число N (1<= N <= 500). В следующих N строках - по два числа, P_i и W_i(1 <= P_i <= 50000, 1 <= W_i <= 10000). Все числа целые.

Выходные данные
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

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

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

Сдача - 1#33104

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные:
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке - N чисел P₁, P₂, ..., P_N;
- в четвертой строке - число M;
- в пятой строке - M чисел Q₁, Q₂, ..., Q_M.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

Выходные данные: если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинала покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	10 3 3 9 14 2 6 2	-2 +9 +3
2	100 3 74 35 8 2 19 6	Impossible

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

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

Сборка компьютера#31928

Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.

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

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента C_i (1 ≤ C_i ≤ 3000), его рейтинг R_i (1 ≤ R_i ≤ 3000) и его тип t_i (1 ≤ t_i ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

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

Ввод	Вывод
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16	18 2 5

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

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

Игра с пешкой#31781

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3
	1
		4
			1
				5
					9
						2
							6

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

В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a₁, a₂, …, a_N (1 ≤ a_i ≤ 100).

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

Выведите одно число – выигрыш первого игрока.

Ввод	Вывод
8 3 1 4 1 5 9 2 6	5

Динамическое программирование на таблицах Простые игры

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

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средняяВойти и решать

Обход по графу. Построение дерева решений#27035

Разработан шифр, при использовании которого каждой цифре ставится в

соответствие определенная буквенная последовательность как приведено в таблице.

1	2	3	4	5	6	7
AB	CB	CBA	ABC	BC	BBC	CCB

С клавиатуры дана буквенная последовательность, содержащая символы только из шифра.

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

Ввод	Вывод
ABCCBABBCCBABC	6

Динамическое программирование: один параметр

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

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

Формат входных данных

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

Формат выходных данных

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

Динамическое программирование: один параметр Строки

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

Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

Формат вывода

Выведите одно число — ответ на задачу.

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

Динамическое программирование: один параметр

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

Формат вывода

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

Пример

Ввод	Вывод
3	6

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

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

Шаблон и слово#23413

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).

Входные данные
В первых двух строках записаны шаблон и слово: в одной из них записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные
Вывести YES, если слово подходит, NO, если не подходит.

Примеры

№	Входные данные	Выходные данные
1	ABBCDA A*CDA	YES
2	AADAAVA ADAAA*	NO

Динамическое программирование: один параметр Строки

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

**Столовские котлеты#23380

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

Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым).

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

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

Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0<=N<=200).

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

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

Примеры

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

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

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

НВП на отрезке#23377

Нам дана числовая последовательность a₁, ..., a_n . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с l_i-ого по r_i-ый элемент".

Подпоследовательностью последовательности a₁ , ..., a_n называется последовательность, которую можно получить путем удаления нескольких элементов a_i (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3 и 5 ), а последовательность (5, 1) - нет.

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

В первой строке записано целое число n (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 10⁹. В третьей строке записано одно целое число q (1 <= q <= 10⁵) - количество запросов. В следующих q строках описаны запросы. Описание i -ого запроса - два числа l_i и r_j (1 <= l_i <= r_i <= n) , записанные через пробел.

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

Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.

Примеры

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

Динамическое программирование: последовательности

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