Информатика

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

 

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

 

Входные данные
- в первой строке вводятся два натуральных числа: N и K (\(2 <= N ,\ K <= 10000\)), разделённые пробелом;
- во второй строке записаны через пробел N-2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты.
Гарантируется, что все числа по модулю не превосходят 10000.

 

- в первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик;
- во второй строке выводится число прыжков Кузнечика;
- в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

 

Если правильных ответов несколько, выведите любой из них.

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

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна h_i. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i₁, i₂, . . . , i_k (i₁ < i₂ < . . . < i_k), таких что их высота возрастает, то есть, h_i1 < h_i2 < . . . < h_ik.

Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами a_i и b_i , означающими, что, по мнению Пети, высота дерева

с номером a_i на самом деле равна b_i . Обратите внимание, Петины предположения независимы между собой.

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

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

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

Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.

В следующей строке содержатся n целых чисел h_i (1 <= h_i <= 10⁹ ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа a_i и b_i (1 <= a_i <= n, 1 <= b_i <= 10⁹ ).

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

Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.

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

Замечание

Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.

Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).

Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

 

В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= Xi <= 60 000.

 

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

Примеры

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

 

 

Входные данные
Нет.  

Выходные данные
Вывести число P.

 

Входные данные
Вводится вещественное число х (-50 <= х <= 50). Гарантируется, что для заданного х решение существует.

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

 

Входные данные
В первой строке вводится натуральное число N (0 < N <= 10). Во второй строке вводится вещественное число А (-5 <= А<= 5, А!=0).


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

 

\(P = A \cdot (A  -  N) \cdot (A - 2 \cdot N) \cdot...\cdot (A - N^2)\)
 

Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-10<=А<=10).


Выходные данные
Вывести число P.

\(P = A \cdot (A  +  1) \cdot...\cdot (A + N - 1)\)
 

Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-100<=А<=100).

Выходные данные
Вывести число P.

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

день, а также информация о том, является ли этот аккаунт спам-ботом. Возраст аккаунта мы можем взять за X координату точки, а количество сообщений  за Y

коордианату. Задача классификации состоит в том, чтобы провести какую-либо прямую так, чтобы объекты одного типа находились по одну сторону этой прямой, а объекты другого типа  по другую.
 

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

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

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

В этой задаче входной файл содержит несколько тестовых блоков.

В первой строке задано число T  количество тестовых блоков (1 <= T <= 100).

Каждый тестовый блок состоит из числа N  количество описанных объектов (1 <= N <= 2000).

В следующих N строках содержится описания объектов, состоящие из трех целых чисел X, Y , Type (0 <= X, Y <= 10⁷ , 0 <= Type <= 1).

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

Выведите T слов "YES" или "NO" по одному в строке для каждого из тестовых блоков. "YES" необходимо выводить если разделение на классы возможно, "NO"  если невозможно.

Система оценки

Решения, верно работающие при T <= 10, N <= 100, будут набирать не менее половины баллов.

Ввод	Вывод
2 6 1 1 1 1 2 1 1 3 0 2 1 1 2 2 0 3 1 0 6 1 3 0 2 2 0 1 2 1 3 1 1 2 1 1 1 1 0	YES NO

При  полутах  на  самолетах  в  качестве  времени  вылета  и  прилета  используется  местное  время аэропортов вылета и прилета.

Часовые пояса характеризуются разницей во времени с меридианом, на котором расположена Гринвичская обсерватория. Для каждого часового пояса вводится отклонение от UTC (Всемирного координированного времени).

Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7.  Если  вылететь  из  Москвы  рейсом  в  11:15  и  временем  полјта  ровно  в  4  часа,  то  прилет будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).

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

В первой строке записаны целые числа H_D , M_D (0 <= H_D <=  23, 0 <= M_D <= 59)  время вылета.

Во второй строке записаны целые числа H_F , M_F (0 <= H_F <= 10⁹, 0 <= M_F <= 59)  время полёта.

В третьей строке записаны целые числа D, A (-11 6 D, A <= 14)  часовые пояса аэропорта вылета и прилёта.
 

Выведите три числа H_A;M_A; Days  время прилёта в часах и минутах, а также разницу в датах между датой вылета и датой прилёта.

Система оценки

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

Ввод	Вывод
11 15 4 0 3 7	19 15 0
12 0 1 0 -10 13	12 0 1

 

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

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

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

 

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

 

Примеры

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

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

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

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

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

 

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

Ввод	Вывод
ABCCBABBCCBABC	6

Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки (Sx; Sy) клетка (tx; ty). Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе.
Гарантируется, что клетка (Sx; Sy) и клетка (tx; ty)не являются ‘#’ клеткой в каждом запросе.

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

На первой строчке вводятся числа Sx (1 <= S_x <= 100), Sy (1 <= S_y <= 100), tx (1 <= t_x <= 100), ty (1 <= t_y <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.

Пояснение
В тестовом примере после первого запроса матрица будет такой:

Из точки (1; 1) в (2; 3) нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:

Из точки (1; 1) в (2; 3)есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.
 

Маленькому Егору в школе задали простую задачу: вывести абсолютное значение числа. Посмотрим, сможет ли он справится с этим без использования строк (даже в выводе).

 

В единственной строке выходных данных содержится целое число M (-2^63 <= M < 2^63)

 

Выведите число, равное модулю числа M.

 

Пример:

Ввод	Вывод
5	5
-7	7

 

P.S. Задача была проверена неоднократно. Все тесты верные. Ошибок быть не может.

P.P.S Все имена вымышлены, все совпадения с реальными людьми случайны.

(c) Ярослав Свиридов и Владимир Линд

Всемирно известному взломщику Матвею поступил заказ на инновационный сейф, выпущенный компанией "British Scientists, Inc". Этот сейф почти целиком сделан из адамантита, не поддающемуся ни одной из дрелей Матвея. Поэтому его единственным уязвимым местом является патентованный кодовый замок. К счастью, Матвей похитил чертежи сейфа ещё во время его разработки, поэтому точно знает принцип работы замка.

Код вводится с помощью клавиатуры с числами от нуля до девяти. Как только введено необходимое количество цифр, код проверяется по следующему алгоритму. К нулю прибавляется первая введённая цифра, затем отнимается вторая, потом эта разность умножается на третью, и наконец, результат нацело делится на четвёртую. Потом этот алгоритм повторяется для следующих четырёх цифр, и так, пока они не кончатся. Если количество цифр не делится на четыре, то лишние действия просто отбрасываются.  Если при выполнении алгоритма встречается деление на ноль, то он тут же аварийно завершает работу, блокируя сейф. Если в результате получилось число X - секретная константа, которую Матвей тоже знает - замок открывается. 

Матвей внимательно изучил клавиатуру и понял, что по отпечаткам пальцев на кнопкам он может определить, какие цифры используются в коде, и сколько раз. Тут ему стало интересно - а сколько всего комбинаций, подходящих под эти данные, открывают замок? Комбинации считаются различными, если в них отличается порядок следования цифр. 

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

 

В первой строке на вход подаются два числа N (1 <= n <= 8) и Х (1 <= X <= 10^9) - количество цифр в коде и секретная константа. Во второй находится n цифр, разделённых пробелами. Разумеется, цифры могут повторяться. 

 

Вывести необходимо единственное число - ответ на вопрос Матвея.
 

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

Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира.  Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли. Леше известно, что пароль содержит в себе все символы лексикографически максимальной подстроки в строке S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!

Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.

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

Программа получает на вход строку S. Длина S не более 15 символов. Строка записана строчными английскими буквами.
 

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

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

В первой строке ввода содержатся два целых числа N и K (1 ≤ N, K ≤ 10001).

Вывести одно целое число – сумму N и K после завершения работы алгоритма.

Ввод	Вывод
30 15	19

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

В первой строке ввода содержится два целых числа, разделенных пробелом - S (0 ≤ S ≤ 20000 ≤ S ≤ 2000) и P (0 ≤ P ≤ 10000000 ≤ P ≤ 1000000).

Вывести два целых числа I и J через пробел.