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


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

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

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

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

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

Напомним, что если мы сравниваем две последовательности, и у них первые 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).

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

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

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

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

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

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

Выбор участка - 1 (24-25)

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

Маша хочет построить дачу на одной приглянувшейся ей улице. Эта улица имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке указан уровень шума от 1 до 9 (где 1 — тишина, 9 — очень шумно).

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

Необходимо написать программу, которая найдёт номер такого тихого участка и расстояние до ближайшего шумного участка.

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

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

  • В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
  • Во второй строке n чисел от 1 до 9 через пробел

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

  • Номер участка и расстояние до ближайшего шумного (через пробел)

Контрольное значение - 5

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

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел.  Все числа данной последовательности не превышают 107. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу,
- берутся три переданных значения из последовательности таким образом, чтобы между какими-либо двумя моментами передачи прошло ровно K секунд;
- вычисляется сумма выбранных чисел, которая должна быть минимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.


Формат входных данных
В первой строке записано количество чисел N (1 ≤ N ≤ 2·105) и целое число K (1 ≤ K < 105, K < N). Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 107.


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

Самый младший

Алгоритмы обработки Одномерные массивы Линейный поиск

В некотором списке записана информация о годе рождения каждого из N человек. Определить наибольший порядковый номер самого младшего по возрасту человека (считая с 1). 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел).

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

Пример
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 4

Наименьшее число

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

Дана последовательность чисел. Найти в ней наименьшее число.
 
Входные данные.
Задано сначала число N (количество чисел в последовательности), а затем
N чисел. Все числа - из диапазона Integer. N<=100
 
Выходные данные.
Выведите наименьшее число.
 
 

ГАИ

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

ГАИ
 
Вдоль шоссе в точках X1,X2,...,XN расположены посты ГАИ. 
В точке X произошло мелкое ДТП (дорожно-транспортное происшествие).
Требуется определить, какой из постов ГАИ расположен ближе всего
к этой точке, чтобы с него послать к месту происшествия наряд милиции.
 
Входные данные
Во входном файле записано сначала число N - количество пунктов ГАИ. (1<=N<=100)
Далее следуют координаты расположения постов ГАИ на прямом шоссе
(целые числа от -10000 до 10000). Далее идет координата точки,
в которой произошло ДТМ (целое число от -10000 до 10000).
 
Выходные данные
В выходной файл требуется вывести одно число - номер поста ГАИ,
с которого нужно послать наряд к месту ДТП. Если несколько постов
ГАИ находятся на одинаковом расстоянии от точки ДТП, выведите любой из них.
 
Пример входного файла
5
10 2 8 -7 3
7
 
Пример выходного файла
3