New

Счастливые билеты

Задача 1

Сегодня у Маши олимпиада по информатике. Как всегда, в школу Маша едет на троллейбусе и покупает билетик. Маша верит, что билетики имеют особую силу, и чем более счастливый ей попадется билет, тем лучше она решит свои задания. Счастьем билета называется максимальное число повторений какой-то цифры в номере билета. Например, для билета с номером 14533, счастье будет равно 2, потому что цифра 3 повторяется 2 раза.

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

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

В единственной строке содержится одно целое число N (0 <= N <= 10¹⁸)

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

Выведите единственное число - счастье билета.

Примеры

Столбы

Задача 2

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

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

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

В первой строке содержится одно целое число N (1 <= N <= 200 000)

Во второй строке - N целых чисел A_i (0 <= A_i <= 1 000 000 000), разделенных пробелами - высоты столбов.

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

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

Примеры

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

Во втором примере ей подходит только 4 отрезка (выделены жирным шрифтом):

2 3 2 3, 2 3 2 3, 2 3 2 3 и 2 3 2 3

В третьем примере - 12 отрезков:

1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1,

1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1

Неожиданная встреча

Задача 3

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

Маша задумалась, и решила проверить Васю - предложила ему найти самый красивый отрезок из всех. Вася с легкостью справился с задачей, и сказал, что все столбы - конечно же и есть самый красивый отрезок. А в ответ предложил более интересную задачу: среди всех возможных отрезков найти K-ый по красоте отрезок.

Маша еще быстрее справилась с поставленной задачей. Сможете ли вы?

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

В первой строке содержится два целых числа N и К (1 <= N <= 200 000,
1 <= K <= 10¹²), разделенные пробелами. Гарантируется, что K будет не больше, чем возможное число отрезков.

Во второй строке - N целых чисел A_i (0 <= A_i <= 1 000 000 000), разделенных пробелами - высоты столбов.

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

Выведите единственное число - K-ую по величине возможную красоту отрезка.

Примеры

В первом примере Маше нужно выбрать первый по красоте отрезок - то есть самый красивый. Это и будет отрезок 1 2 3 4 5, сумма высот в нем равна 15.

Во втором примере первым по красоте отрезком будет 2 3 2 3, его красота равна 10.

Вторым по красоте - 2 3 2 3, его красота равна 8

Третьим по красоте - 2 3 2 3, его красота равна 7

Есть три отрезка с красотой 5 - отрезки 2 3 2 3, 2 3 2 3, 2 3 2 3. Они являются четвертым, пятым и шестым по красоте. Нас интересует красота пятого по красоте отрезка. Значит, ответ - 5.

Запутанная школа

Задача 4

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

Школа представляет собой N комнат, между M парами из которых можно пройти напрямую. K из них являются столовыми. Задача Маши заключается в том, чтобы найти такие 2 столовых, что время на проход между ними будет минимально. Именно этим путем она пойдет искать кабинет информатики.

Помогите Маше найти кратчайшее такое расстояние.

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

В первой строке содержится три целых числа N, M и К (1 <= N <= 100 000,
1 <= M <= 200 000, 2 <= K <= N), разделенные пробелами.

Во второй строке - K различныхцелых чисел S_i (1 <= S_i <= N), разделенных пробелами - номера комнат, являющихся столовыми.

В следующих M строках содержится описание переходов между комнатами. Каждая строка содержит три числа A_i, B_i, C_i, разделенных пробелами. И означает, что между комнатами A_i и B_i можно пройти в обе стороны за C_i секунд.

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

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

Примеры