Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

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

Красота превыше всего

"Два указателя"

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
 
Входные данные
В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета
 
Выходные данные
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
 
Ввод Вывод
5 3
1 2 1 3 2
2 4
6 4
2 4 2 3 3 1
2 6

Метод двух указателей

"Два указателя"

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

Входные данные
В первой строке записаны  N и K (0<N<= 106, 0<=K<= 109,)  Во второй строке записаны натуральные числа последовательности. Если такой последовательности найдено не будет, то ответ -1.

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

Ввод Вывод
6
7
3 1 3 2 4 3
3

Тихий дон №2

"Два указателя"

Аксинья любит Григория, но она замужем за Степана. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (a_i < 0), а то время, которое она проводит с Григорием, - положительным показателем счастья (a_i > 0). Известно, что Аксинья проводит один день либо с мужем, либо с любовником. Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.

Входные данные.
В первой строке подается 3 числа: N – кол-во дней, L и C (1 <= L, C <= N <= 1 000 000).
Во второй строке содержится N чисел a_i (1 <= |a_i| <= 1 000 000 000).

Входные данные.
Требуется вывести ответ на задачу.

Ввод Вывод
5 3 3
1 -1 2 -2 3
3

 
(с) Шалдин В., 2018

Робот

"Два указателя"

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
 
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.
 
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
 
Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.
 
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
 
Входные данные
В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.
 
Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.
 
Выходные данные
Выходной файл должен содержать единственное целое число "— количество экономически целесообразных способов использования робота.

Ввод Вывод
2
zabacabab
5
2
abc
0