You are to write a program that receives a sequence of words and sorts it in lexicographical order.
Linear order on characters is given by ASCII codes.
Input file format
First line of input file contains integer N — the sequence length.
Following N lines contain one word per line.
Each word is exactly three letters long.
Output file format
Output file must consist of N lines,
each containing one word from sorted sequence.
Набором данных называется пара чисел первое из которых называется ключом,
второе — данными. Ваша задача состоит в том, чтобы упорядочить данные в порядке возрастания ключей.
При совпадении ключей первым в отсортированном массиве должен идти тот же элемент что и в не сортированном.
Формат входного файла
Во входном файле содержится число N, за которым следуют N пар чисел — наборы данных.
Формат выходного файла
В выходном файле должно содержаться ровно N чисел — данные, упорядоченные в порядке возрастания ключей.
Ограничения
0 ≤ N ≤ 100000, все числа находятся в диапазоне от 1 до 100000
Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку.
Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек.
Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.
Хоттабыч вспомнил два своих любимых цвета, нашел пару ближайших друг к другу лампочек
первого и второго цветов (порядок лампочек в паре не имеет значения),
и подсчитал количество лампочек между ними.
Потом он выбрал ещё два цвета и повторил поиск для них...
Хоттабычу очень понравилось это занятие, и теперь он просит вас
написать программу, которая, получив на входе описание гирлянды и M запросов Хоттабыча,
отвечала бы на каждый запрос.
Рекомендуется рассмотреть частичные решения
K ≤ 2
N ≤ 100
Формат входного файла
В первой строке входного файла содержится число N.
В последующих N строчках содержатся цвета лампочек гирлянды.
В N + 2-й строке входного файла содержится число M.
В последующих 2 * M строчках содержатся запросы Хоттабыча (по две строки на запрос).
Формат выходного файла
Выходной файл должен содержать M чисел — ответы для каждого запроса в порядке поступления.
Если в запросе указан цвет, отсутствующий на гирлянде,
то в качестве ответа следует вывести − 1.
Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести − 2.
Ограничения
2 ≤ N ≤ 15000
1 ≤ M ≤ 20000
1 ≤ K ≤ 3000
Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green
K-ой порядковой статистикой N-элементной последовательности AN называется число AK,
которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности
по возрастанию.
Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.
Формат входного файла
Во входном файле содержатся целые числа QVPNK
Формат выходного файла
В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной
последовательности.
Дана последовательность из N целых чисел ai. Над последовательностью M раз выполняется следующая операция.
Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных.
Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.
Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.
Формат входного файла
Первая строка входного файла содержит целые числа N и M — количество элементов последовательности
и количество операций.
Вторая строка входного файла содержит N целых чисел ai — элементы последовательности.
Формат выходного файла
В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.
Ограничения
1 ≤ M < N ≤ 105
− 104 ≤ ai ≤ 104
Описание подзадач и системы оценивания
Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.
Центральным элементом набора из k чисел называется такой элемент, который
после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер
⌈k / 2⌉, считая с единицы).
Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить
значения центрального элемента после добавления каждого числа.
Формат входного файла
Входной файла содержит количество чисел n, за которым следуют n целых чисел ai
в порядке их добавления в набор.
Формат выходного файла
Выходной файл должен содержать n целых чисел — значения центрального элемента после
каждого добавления.
A well known algorithm called heapsort is a
deterministic sorting algorithm taking O(n log n) time
and O(1) additional memory. Let us describe ascending sorting
of an array of different integer numbers.
The algorithm consists of two phases. In the first phase,
called heapification, the array of integers to be sorted
is converted to a heap. An array a[1…n] of integers
is called a heap if for all 1 ≤ i ≤ n the following heap conditions
are satisfied:
- if 2i ≤ n
then a[i] > a[2i];
- if 2i + 1 ≤ n then a[i] > a[2i + 1].
We can interpret an array as a binary tree, considering children
of element a[i] to be a[2i] and a[2i + 1]. In this case
the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2).
In terms of trees
the property of being a heap means that for each node its value is greater
than the values of its children.
In the second phase the heap is turned into a sorted array.
Because of the heap condition the greatest element
in the heapified array is a[1]. Let us exchange it with a[n],
now the greatest element of the array is at its correct position
in the sorted array. This is called extract-max.
Now let us consider the part of the array a[1 ... n-1]. It may be
not a heap because the heap condition may fail for i=1.
If it is so (that is, either a[2] or a[3], or both are greater
than a[1]) let us exchange the greatest child of a[1] with it, restoring
the heap condition for i=1. Now it is possible that the heap condition
fails for the position that now contains the former value of a[1]. Apply the same
procedure to it, exchanging it with its greatest child. Proceeding so
we convert the whole array a[1 ... n-1] to a heap.
This procedure is called sifting down.
After converting the part a[1 ... n-1] to a heap by sifting, we
apply extract-max again, putting second greatest element of
the array to a[n-1], and so on.
For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to
a sorted array. Let us make the first extract-max. After that the array
turns to (3, 4, 2, 1, 5). Heap condition fails
for a[1] = 3 because its child a[2] = 4 is greater than it.
Let us sift it down, exchanging a[1] and a[2]. Now the array is
(4, 3, 2, 1, 5). The heap condition is satisfied
for all elements, so sifting is over. Let us make extract-max again.
Now the array turns to (1, 3, 2, 4, 5). Again
the heap condition fails for a[1]; exchanging it with its greatest
child we get the array (3, 1, 2, 4, 5) which is
the correct heap. So we make extract-max and get
(2, 1, 3, 4, 5). This time the heap condition
is satisfied for all elements, so we make extract-max, getting
(1, 2, 3, 4, 5). The leading
part of the array is a heap, and the last
extract-max finally gives (1, 2, 3, 4, 5).
It is known that heapification can be done in O(n) time. Therefore,
the most time consuming operation in heapsort algorithm is sifting,
which takes O(n * log (n)) time.
In this problem you have to find a heapified array containing
different numbers from 1 to n, such that when
converting it to a sorted array, the total number of exchanges in
all sifting operations is maximal possible. In the example above the
number of exchanges is 1+1+0+0+0 = 2, which is not the maximum.
(5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.
Input file format
Input file contains n.
Output file format
Output the array containing n different integer
numbers from 1 to n, such that it is a heap,
and when converting it to a sorted array,
the total number of exchanges in sifting operations is
maximal possible. Separate numbers by spaces.
Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа N и w, а за ними следует последовательность
из N целых чисел ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами.
Единица на позиции i означает, что элемент последовательности ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите − 1.
Однажды у Хана Соло и Леи Скайуокер родились двое детей. Когда детям было около года они любили играть с камушками. Тогда Лея и Хан
решили собрать им по кучке красивых камней. К обеду они насобирали камней, но надо было распределить их на две кучки так, чтобы дети
не поссорились. Для этого камни надо распределить так, чтобы разница между суммарными весами двух кучек была минимальной и надеяться,
что дети ее не заметят.
Формат входного файла
В выходном файле содержится целое число N - количество камней. Следующие N чисел Wi - веса каждого камня.
Формат выходного файла
Выходной файл должен содержать единственное неотрицательное целое число C - минимальная разность весов.
Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу.
Он заранее готовился к этому: накупил карандашей, ручек, тетрадей.
Среди покупок, кроме обычных тетрадей, были также и двойные,
каждая из которых предназначена сразу для двух предметов.
Каждый день Чебурашке нужно брать с собой тетради для всех предметов,
которые будут преподаваться в его классе в этот день.
Тетради тяжелые, а носить лишний вес в школу не хочется.
Поэтому он пытается распределить предметы по тетрадям таким образом,
чтобы за неделю переносить наименьший возможный вес.
Помогите ему это сделать.
У Чебурашки есть NS одинарных и ND двойных тетрадей.
Все одинарные тетради имеют вес WS, а все двойные — вес WD.
Чебурашка учится N дней в неделю.
Он изучает M предметов, пронумерованных от 1 от M.
Вес, который Чебурашке придётся перенести за один день,
равен сумме весов всех тетрадей, которые он должен будет взять.
Требуется написать программу, вычисляющую наименьший возможный вес,
который Чебурашке придется перенести в сумме за все дни недели.
Формат входного файла
Во входном файле содержатся числа NMNSNDWSWD.
Далее следует расписание, состоящее из N дней.
Каждый день описывается одной строкой.
В начале строки содержится Ki — число уроков в i-ый день,
за которым следует Ki чисел — номера предметов.
Все числа во входном файле целые.
Формат выходного файла
В выходном файле должно содержаться единственное число — минимальный возможный вес.
На некотором языке все слова записываются заглавными латинскими буквами,
и состоят из слогов. Слогом называется непустая последовательность согласных,
заканчивающаяся гласной. Все остальные последовательности букв словами этого
языка не являются.
Например, слово BARBARA состоит из трех слогов — BA, RBA и RA.
Последовательности букв ААХ, Е, К, АНА словами не являются.
Осмысленными считаются слова, в которых все согласные различны.
По данной последовательности из N заглавных латинских букв
определить, является ли она осмысленным словом и, если да, то сколько
различных слогов можно составить из букв этого слова.
Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA,
KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.
Формат входного файла
Входной файл содержит единственную строку — исходную последовательность букв.
Формат выходного файла
Выходной файл должен содержать число − 2, если исходная последовательность
букв не является словом, − 1, если исходное слово бессмысленно, либо число
слогов, которые можно составить из данных букв.
Даны строки S и P, состоящие из малых латинских букв.
Требуется определить сколько различных слов, составленных из букв строки S,
содержат в себе подстроку P.
Например, если S = dcba, P = bc, то получится 11 строк:
bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.
Формат входного файла
Первая строка содержит строку S, вторая — строку P.
Формат выходного файла
В выходном файле должно содержаться единственное число — количество слов.
Ограничения
Длины строк находятся в диапазоне от 1 до 12 букв. Все буквы строки S различны.
В детском танцевальном конкурсе участвовало N школьников.
Организаторы решили наградить всех участников конкурса конфетами K различных сортов.
Чтобы никого не обидеть, всем школьникам решили выдать одинаковое количество конфет.
А чтобы было интереснее, набор конфет каждого школьника должен
отличаться от всех остальных.
Например, если имеется 6 школьников и 3 сорта конфет,
то можно определить такие награды из двух конфет каждая:
(1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3).
В то же время, если имеется 7 школьников и 3 сорта конфет,
то каждому школьнику придётся выдать уже по три конфеты.
Напишите программу, которая по количеству школьников и количеству сортов конфет
определяет наименьшее количество конфет в награде.
Формат входного файла
Входной файл целые числа NK.
Формат выходного файла
Выходной файл должен содержать единственное целое число — наименьшее количество конфет.
Построить код Хаффмана для алфавита из N символов и соответствующих им частот
встречаемости.
Формат входного файла
Во входном файле содержится число N, за которым следуют N чисел
fi — частота встречаемости i − го символа.
Формат выходного файла
Выходной файл должен содержать N строк вида hi — коды Хаффмана
для символов в порядке, соответствующем входному файлу.
Каждый код должен представлять собой строку из цифр 0 и 1.
Если существует несколько решений, вывести любое из них.
Город соединяется с аэропортом автодорогой, имеющей N полос движения.
Дорога состоит из K участков длиной 10 километров каждый.
На каждом участке полосы разделены сплошной линией разметки
(т.е. сворачивать с одной полосы на другую запрещено).
На стыке участков разрешено перемещение на любую из соседних полос.
В начале каждого участка на каждой полосе дороги поставлен знак ограничения скорости,
при этом на разных полосах ограничения могут различаться.
Требуется вычислить минимальное время, за которое можно доехать из города в аэропорт,
не нарушая правил дорожного движения.
Считать, что скорость автомобиля изменяется мгновенно, и на смену полосы время не тратится.
Начинать движение по дороге можно с любой полосы.
Формат входного файла
Во входном файле находятся числа N и K,
за которыми идут N строк по K вещественных чисел ai, j
в каждой — ограничение скорости на j-м участке i-й полосы (в км/час).
Формат выходного файла
Выходной файл должен содержать единственное число — минимальное время (в часах) за которое
можно попасть из города в аэропорт, с точностью до трех знаков после запятой.
Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины.
На табуреткоизготовительную фабрику поступило N ножек,
имеющих слегка различающиеся длины L1,
L2, … LN.
Научно-исследовательский отдел фабрики обнаружил,
что выпуск табуреток можно увеличить, если укорачивать некоторые ножки.
При этом отпиленная часть выбрасывается.
Требуется определить минимальное количество распилов, необходимых для
для изготовления N / 4 качественных табуреток.
Формат входного файла
Входной файл содержит число N, за которым следуют N чисел
Li — длины ножек. Все числа целые.
Формат выходного файла
В выходной файл следует вывести единственное целое число — минимальное
количество распилов.
Вдоль лесной тропинки растёт N деревьев высотой
h1, h2, …, hN
метров соответственно. Расстояние между соседними деревьями равно 1 метру.
Лягушка сидит на дереве с номером A и хочет попасть на дерево с номером B.
Поскольку лазить по деревьям она не может, ей остаётся только перепрыгивать с одной вершины
дерева на другую. При этом лягушка может развивать начальную скорость от 0 до v м/с,
и прыгать под углом от 0 до α градусов.
Требуется найти минимальное количество прыжков, которое потребуются лягушке, или определить,
что достичь цели невозможно.
Ускорение свободного падения g следует принять равным 10 м/с2.
Формат входного файла
Входной файл содержит числа NABv α,
за которыми следует N чисел
h1h2 … hN.
Числа v и α — вещественные, остальные числа — целые.
Формат выходного файла
Выходной файл должен содержать единственное целое число — необходимое количество прыжков,
или −1, если решения не существует.
Ограничения
1 ≤ A, B ≤ N ≤ 100,
1 ≤ hi ≤ 1000,
0.01 ≤ v ≤ 1000,
0.01 ≤ α ≤ 90.
Перед сражением с ситхами Энакен Скайуокер решил протестировать своего дроида R2D2.
Для проверки системы передвижения он решил поместить робота на специальную горизонтальную площадку,
имеющую форму прямоугольника. Площадка разделена на квадратные клетки со сторонами длины 1. На некоторые клетки можно перемещаться,
на некоторые - нет.
R2D2 разрешено перемещаться только вверх, вперед, влево, вправо на соседние клетки.
Для первого теста Энакен хочет заставить робота пройти от начальной клетки площадки до конечной
всеми возможными способами, проходя через каждую клетку ровно 1 раз.
Чтобы заставить робота двигаться, юному джедаю надо записать все траектории, которые следует пройти роботу, в виде
последовательностей символов 'l', 'r', 'u', 'd'. Символ 'l' означает, что робот должен перейти в левую соседнюю клетку, 'r', 'u', 'd' -
в правую, верхнюю, нижнюю соответственно. Энакену лень записывать таким образом все способы перемещения, и он просит вас
написать программу, которая напишет их за него.
Формат входного файла
Первая строка входного файла содержит два целых числа N, M - длины сторон прямоугольника.
За ними следует N * M чисел A[i, j], которые равны 0, если в клетку с координатами i, j перемещаться нельзя,
или 1 - можно. Первое число задает верхнюю левую клетку (она является начальной), последнее - нижнюю правую(конечная).
Гарантируется, что есть хотя бы один путь из начальной клетки в конечную.
Формат выходного файла
В выходной файл выведите число C - количество способов перемещения из начальной клетки в конечную, за которым следует
C строк - способы перемещения в виде последовательностей символов 'l', 'r', 'u', 'd'. Последовательности можно выводить в любом порядке.
You are to write a program that receives an unweighted undirected graph and writes all its vertices in
order of increasing distance from given vertex S.
Distance between vertices A and B is the length of the shortest path from A to B.
If there are several vertices such that their distances to S are equal,
they may be printed in arbitrary order.
Input file format
Input file contains three integers N, M and S, where M is the number of edges,
S is the starting vertex.
Vertices are numbered with integer numbers from 1 to N.
Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.
Output file format
Output file must contain sequence of vertex numbers sorted by increasing distance from S.
If some vertex is not reachable from S, output a single number − 1.
Дан неориентированный граф. Проверьте, является ли он деревом.
Формат входного файла
В первой строке входного файла заданы через пробел два целых числа
n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих
строк содержит два целых числа ui и vi через пробел — номера концов
i-го ребра.
Граф не содержит петель и кратных рёбер.
Формат выходного файла
В первой строке выходного файла выведите YES, если граф является
деревом, и NO в противном случае.
You are to write a program that performs a topological sorting of a directed graph.
Graph contains N vertices, numbered with integers from 1 to N, and M edges.
In other words, given a partial order on numbers from 1 to N,
your program must produce some linear order on these numbers
which does not conflict with the given partial order.
Input file format
Input file contains two integers N and M, followed by M pairs of integers.
Integers in each pair are different, and represent starting and ending vertex of a graph edge.
These pairs may also be considered comparisons where the first number precedes
the second one.
Output file format
Output file must contain a permutation of integers from 1 to N —
numbers of vertices sorted in topological order.
(That is, representing a linear order.)
If ordering is not possible, output file must contain a single number − 1.
Недавно на кружке по программированию Петя узнал об обходе в глубину.
Обход в глубину используется во многих алгоритмах на графах. Петя сразу
же реализовал обход в глубину на своих любимых языках программирования —
паскале и си.
var
a: array [1..maxn, 1..maxn]
of boolean;
visited: array [1..maxn]
of boolean;
procedure dfs(v: integer);
var
i: integer;
begin
writeln(v);
visited[v] := true;
for i := 1 to n do begin
if a[v][i] and
not visited[i] then
begin
dfs(i);
writeln(v);
end;
end;
end;
procedure graph_dfs;
var
i: integer;
begin
for i := 1 to n do
if not visited[i] then
dfs(i);
end;
int a[maxn + 1][maxn + 1];
int visited[maxn + 1];
void dfs(int v) {
printf("%d\n", v);
visited[v] = 1;
for (int i = 1; i <= n; i++) {
if ((a[v][i] != 0) &&
(visited[i] == 0)) {
dfs(i);
printf("%d\n", v);
}
}
}
void graph_dfs() {
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
dfs(i);
}
}
}
Петина программа хранит граф с использованием матрицы смежности в массиве "a"
(вершины графа пронумерованы от 1 до n).
В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.
Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G
с n вершинами и сохранил ее вывод.
А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество
ребер могло быть в графе G. Помогите ему выяснить это!
Формат входного файла
Первая строка входного файла содержит два целых числа: n и l —
количество вершин в графе и количество чисел в выведенной последовательности.
Следующие l строк по одному числу —
вывод Петиной программы. Гарантируется, что существует хотя бы один граф,
запуск программы Пети на котором приводит к приведенному во входном файле
выводу.
Формат выходного файла
На первой строке выходного файла выведите одно число m — максимальное
возможное количество ребер в графе. Следующие m строк должны содержать по два
целых числа — номера вершин, соединенных ребрами. В графе не должно быть
петель и кратных ребер.
Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач.
Для этого на подстанциях были установлены N ретрансляторов.
Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору.
Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод,
назовем нагрузкой на данный провод для i-го ретранслятора.
Максимум из нагрузок на все провода для i-го ретранслятора
называется нагрузкой на данный ретранслятор.
Известно, что по проводам электросети сигнал может пройти
от одного ретранслятора к другому единственным образом.
Требуется написать программу, которая по заданной схеме электросети
подсчитает нагрузку на каждый ретранслятор.
Формат входного файла
Во входном файле содержится число N — количество ретрансляторов, за которыми
следуют N − 1 пар чисел uivi, означающих,
что i-ый провод соединяет ретрансляторы ui и vi.
Формат выходного файла
В выходном файле должно содержаться N чисел a1a2… aN,
где ai — нагрузка на i-ый ретранслятор.
Давным давно в одном далеком королевстве король решил записывать все законы королевства.
С тех пор, когда появлялся новый закон, соответствующую запись добавляли в архив законов.
Много веков спустя юристы обнаружили, что в королевстве было только два вида законов:
прямой закон, который устанавливает новые правила;
отменяющий закон, который отменяет один из предыдущих законов.
Закон считается активным если и только если нет активного закона, отменяющего его.
Ваша задача — написать программу, которая определяет, какие законы до сих пор активны.
Формат входного файла
Первая строка входного файла содержит целое число n
(1 ≤ n≤ 105) — число изданных законов.
Следующие n описывают по одному закону каждая. Каждое описания удовлетворяет одному из следующих форматов:
declare, означает, что издан новый закон.
cancel i, где i — номер закона, отменяемого данным.
Законы нумеруются с единицы.
Формат выходного файла
Первая строка выходного файла должна содержать число активных законов.
Следующая строка должны содержать номера этих законов, перечисленные в возрастающем порядке.
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers NMS, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of N integers — distances from vertex S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤ N, M ≤ 1000.
All weights are less than 1000 by absolute value.
You are to write a program that receives a weighted directed graph and finds
distances from source vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W.
Length of path is the sum of weights of its edges.
Vertices are numbered with integers from 1 to N.
Input file format
First line of input file contains three integers NM and S,
where M is the number of edges. Next M lines contain three
integers each —
starting vertex number, ending vertex number and weight of some edge respectively.
All weights are positive.
There is at most one edge connecting two vertices in every direction.
Output file format
Output file must contain N integers — distances from
source vertex to all vertices.
If some vertices are not reachable from S, corresponding numbers must be −1.
Constraints
1 ≤ N ≤ 1000.
All weights are less or equal than 1000.
You are to write a program that receives a weighted directed graph and finds
all distances from fixed vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W. Length of path
is the sum of weights of its arcs.
Input file format
Input file contains two integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. S is the number of
source vertex. M is the number of arcs. Each of next M lines contain three
integers — numbers of starting and ending vertices of some arc and its weight
respectively. All weights are positive. There is at most one arc connecting
two vertices in every direction.
Output file format
Output file must contain N numbers. Each I-th number is the distance from
vertex S to vertex I. If some vertices are not reachable from S, corresponding
numbers must be −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
You are to write a program that finds shortest distances between all pairs
of vertices in a directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers N and M, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a matrix of size NxN.
Element in the j-th column of i-th row mush be the shortest distance between
vertices i and j.
The distance from the vertex to itself is considered to be 0.
If some vertex is not reachable from some other,
there must be empty space in corresponding cell of matrix.
Constraints
0 ≤ N ≤ 100.
All weights are less than 1000 by absolute value.
You are to write a program that receives two strings and finds position where the second string appears in the first
one as a substring.
Input file format
First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a'
to 'z' and spaces.
Output file format
Output file must contain a single integer — position of the first occurrence of the substring in a string, or − 1 if there is none. Positions are numbered from 1.
Constraints
Length of each string does not exceed 100000 characters.
Sample tests
No.
Input file (input.txt)
Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16
Задача Z. Длинный текст и много слов (revisited)
≡
Имеется текст и N слов. Длина текста составляет L символов,
длина каждого слова — от 1 до 1000 символов.
Требуется для каждого слова определить, входит ли оно в текст.
Все слова и текст состоят из маленьких латинских букв.
Формат входного файла
В первой строке входного файла содержится текст,
во второй — число N, в следующих N строках — слова.
Формат выходного файла
В выходном файле должны содержаться N чисел 1 или 0,
обозначающих, что соответствующее слово входит или не входит в текст.
