Структуры данных

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

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

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

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

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

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

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

Наша вселенная представляет собой n-мерный прямоугольный параллелепипед. Множество измерений вселенной B = {a[i] : 1<=i<=n}. 

Множество B такого, что его первые b элементов являются измерениями b-мерного подпараллелепипеда.

Перед учеными встал ряд вопросов типа: какое пространство находится внутри k-мерного подпараллелепипеда, если предположить, что пространство внутри m-мерного нулевое.

Напишите программу, которая даст ответ на вопросы ученых.

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

Все числа неотрицательные.

В первой строке вводятся  целые числа (n, q <= 10^5) размерность нашей вселенной и количество вопросов, интересующих ученых соответственно.

Во второй строчке вводятся n целых чисел - измерения вселенной, каждое из которых не превосходит (10^18 - 14)

Далее следует q строк по два числа, однозначно задающие вопрос указанного типа, интересующий ученых - m, k. (m, k <= n)

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

Программа должна выводить q строк по одному числу. На i-ой строке должен распологаться ответ на i вопрос указанного типа.

 

Пример:

INPUT:

3 1

1 2 3

0 3

OUTPUT:

6

Пояснение:

Т.к. пространство внутри 0 мерного подпараллелепипеда (точки) нулевое (по условию), то пространство внутри 3-х мерного (пространство внутри 3-х мерного - объем) считается по обычной формуле: 1*2*3 = 6

Автор: Иван Шершнев

Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.

 

Формат файла входных данных:

 

Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). В последней строке вводится данное ребро B, E, W.

 

Формат файла выходных данных:

 

Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева c данным ребром. 

 

Ввод:

 

4 4

1 2 1

2 3 2

3 4 5

4 1 4

1 4 7

 

Вывод:

10

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

 

Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

 

Формат выходных данных 
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

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

 

На вход подается сначала число N - количество чисел в последовательности (\(3<=N<=100\)).
Далее идет сама последовательность: N целых чисел, по модулю не превышающих 1000.

 

Выведите три искомых числа в любом порядке. 

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

 

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

Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — a_i и b_i (1 ≤ a_i,b_i ≤ N), описывыющие туннель из пещеры с номером a_i в пещеру с номером b_i. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации