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


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

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

Найдите последовательность

Линейный поиск

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

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

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

Входные данные
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные
В выходной файл выведите выигрышную последовательность.

Примеры
№ Входные данные Выходные данные Пояснение
1 4
MAMA		 A Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
2 4
ALLO		 ALLO Выигрышной является исходная строка
3 5
BBABB		 ABB  

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

Линейный поиск Перебор

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

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

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

 
Примеры
№ Входные данные Выходные данные
1 
3
 
0
2 
9
 
1

Линейный поиск-1

Линейный поиск

Напишите программу, которая определяет, сколько раз встречается заданное число x в данном массиве.

Входные данные
В первой строке задается одно натуральное число N, не превосходящее 10000 – размер массива.
Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
В третьей строке содержится одно целое число x , не превосходящее по модулю 1000.

Выходные данные
Вывести одно число – сколько раз встречается x в данном массиве.

Пример
входные данные 
5
1 2 3 4 5
3
выходные данные 
1

Касса (D, C')

Линейный поиск

Оля решила стать предпринимателем, и недавно открыла свой магазин "Н-аудио". Магазин работает уже в течение целых n дней, и в конце каждого дня Оля приходит, и записывает на листочек количество денег в кассе магазина. При этом, в конце дня деньги из кассы не изымаются,  то есть, после первого дня в кассе хранится выручка за первый день, после второго дня выручка за первый и второй дни и так далее. Оле стало интересно, в какой из n дней выручка магазина была максимальна. Если таких дней несколько, то Олю интересует первый такой день.
 
Формат входных данных  
в  первой строке входного файла находится целое число n - количество дне, в течение которых
работал магазин 1 <= n <= 105 . В i-ой из следующих n строчек содержится целое число ai -
описание баланса рублей в кассе магазина после i-ого дня 0 <= ai <=109
гарантируется, что деньги из кассы никогда не забирали, то есть ai > ai?1 -  для любого i от 2 до n.
 
Формат выходных данных
В единственной строке выходного файла выведите два целых числа - номер дня, в котором
выручка магазина была максимальна, и величину этой выручки. Если таких дней несколько, то
выведите самый ранний из них. Дни в магазине нумеруются с единицы?
 
Ввод Вывод
3
4
5
17		 3 12
5
1
1
3
5
5		 3 2

Монотонность

Линейный поиск

Университет Иннополис готовится к проведению Летней школы олимпиадного программирования. Сейчас им нужно выбрать даты проведения.

Организаторы заметили, что школа проходит лучше, если настроение детей с каждым днем школы улучшается, также они заметили, что настро- ение школьников сильно зависит от погоды: в ясную погоду школьники веселее, чем в пасмурную. Организаторы запросили прогноз погоды на n дней, в которые можно провести школу. Для каждого дня они посчитали число ai — солнечность i-го дня. Теперь они хотят выбрать для про- ведения школы некоторый непрерывный отрезок дней, такой, что каждый следующий день школы солнечность строго больше, чем в предыдущий.

Помогите организаторам школы найти максимальное число дней, которые может идти школа.

Формат входных данных
В первой строке входного файла задано число n — число дней, в которые можно провести школу. Во второй строке заданы n ( 1<=n<=105) чисел ai — солнечности дней (0 <= ai <= 109 ).
Формат выходных данных
Выведите одно число: максимальное число дней, которое может идти школа так, чтобы каждый следующий день школы был солнечнее, чем предыдущий.
 

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

Контрольное значение для Деда Мороза

ЕГЭ - вычислительные задачи Линейный поиск

Электронная почта Деда Мороза в течении долгого времени принимает заказы на новогодние подарки. Все желания детей кодируются некоторым положительным целым числом и затем передаются по каналу связи. Количество заказаов заранее неизвестно, но их всегда не менее двух. Признаком конца данных считается число 0. 
Для того, чтобы понять, что все данные приняты без ошибок, после данных передаётся контрольное значение. Контрольное значение равно максимально возможному произведению двух чисел из переданных, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Дед Мороз очень занят в последний месяц перед Новым годом и просит вас обработать все входные данные и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.


Формат входных данных
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Формат выходных данных
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

Примечание
В последней строке в зависимости от результата (если переданное контрольное значение и вычисленное контрольное значения равны) может быть values true

Телефонный справочник

Линейный поиск Задача на реализацию Строки

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

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 106) 

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.
 

Подпоследовательность с количеством положительных кратным 11

Линейный поиск

Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратно K = 11. Найдите наибольшую сумму такой подпоследовательности. 

Формат входных данных
В первой строке записано натуральное число N - количество чисел (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Формат выходных данных
Выведите одно число - ответ на задачу.

Подпоследовательность с кратным количеством

Линейный поиск

Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратных двум кратно K. Найдите такую подпоследовательность с максимальной суммой. 

Формат входных данных
В первой строке записаны два натуральных числа N и K (1 <= N <= 1 000 000, 1 <= K <= 100). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

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

Квадраты и кубы

Целые числа Арифметические алгоритмы (Теория чисел) Бинарный поиск Линейный поиск Вещественные числа

В лаборатории теории чисел одного университета изучают связь между
распределением квадратов и кубов натуральных чисел.
Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных
чисел от a до b, включительно. Будем называть k-плотностью этого множества количество
пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2– y3| ≤ k.
Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как
подходят следующие пары:

 x = 1, y = 1, |x2– y3| = |1 – 1| = 0;
 x = 3, y = 2, |x2– y3| = |9 – 8| = 1;
 x = 5, y = 3, |x2– y3| = |25 – 27| = 2.
 
Требуется написать программу, которая по заданным натуральным числам a и b, а
также целому неотрицательному числу k, определяет k-плотность множества натуральных
чисел от a до b, включительно.
Формат входных данных
Входные данные содержат три строки. Первая строка содержит натуральное число a,
вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное
число k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).
Формат выходных данных
Выходные данные должны содержать одно целое число: искомую k-плотность
множества натуральных чисел от a до b, включительно.
 
Ввод Вывод
1
30
2		 3

Наиболее удаленная точка

Элементарная геометрия Линейный поиск

Выведите координаты наиболее удаленной от начала координат точки.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 103
по абсолютной величине.

Выходные данные
Выведите  координаты точки, наиболее удаленной от начала координат.

Забавный конфуз

Линейный поиск Целые числа Одномерные массивы

Пусть A — массив, состоящий из N элементов A1,...,AN. Обозначим его максимальноеи минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1≤i≤N. Такое преобразование массива A назовем операцией Confuse. Напишите программу, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).

Входные данные
Первая строка входного файла содержит целые числа N и K, где N — количество элементов массива B (2 ≤ N ≤ 10000), а K — количество применений операции Confuse к начальному массиву A, 1 ≤ K ≤ 100. Вторая строка файла содержит N элементов массива B. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

Выходные данные
Единственная строка выходного файла должна содержать целое число - разность max(A) и min(A).
Hallowen