Problem A. Dijkstra ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

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 N M 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.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
5 3 1
1 2 5
1 3 7
3 4 10
 
0 5 7 17 -1

Problem B. Floyd-Warshall ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

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.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 3
1 2 5
1 3 10
2 3 2
 
0 5 7
  0 2
    0

Problem C. Ford-Bellman ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

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 N M S, 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.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 3 1
1 2 5
1 3 10
2 3 2
 
0 5 7

Problem D. Bipartite graph ≡

Author:StdAlg (adapted by T. Chistyakov, A. Klenin)   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Input file contains integers N M, then M pairs of integers ai bi describing the edges of the graph.

Output file format

Output BIPARTITE if the graph is bipartite or NO if it is not.

Constraints

1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2
1 2  1 3
 
BIPARTITE
2 
4 6
1 2  2 3  3 4  4 1  1 3  2 4
 
NO

Задача E. Открытка программиста ≡

Автор:О. Ларькина   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

На день святого Валентина Дима решил сделать подарить своей девушке Лене открытку с сердечками. Лена учится в ДВФУ на программиста, поэтому Диме хотелось сделать программистскую открытку.

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

Изображение открытки представляет собой прямоугольную таблицу, состоящую из символов "." (ASCII 46), "/" (ASCII 47), "V" (ASCII 86), "\" (ASCII 92), "^" (ASCII 94). На открытке изображено n сердец. Каждое сердце задаётся координатами центра x y и размером d. Координата x отсчитывается по горизонтали слева направо, а координата y — по вертикали сверху вниз.

Изображение сердца состоит из шести наклонных линий, состоящих из символов "/" и "\". Две линии, образующие нижний контур сердца, имеют длину по d символов, две линии, образующие внешнюю часть верхнего контура, имеют длину по ⌊(d + 1) / 2⌋ символов, а две линии, образующие внутреннюю часть верхнего контура, имеют длину по ⌊(d − 1) / 2⌋ символов.

Центр и нижняя точка сердца обозначены символами "V". Если d чётно, то две верхние точки сердца обозначены символами "^".

Изображение открытки должно иметь минимально возможный размер, охватывающий изображения всех заданных сердец. Все позиции, не занятые изображениями сердец, должны содержать символ ".".

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

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

Входной файла содержит натуральное число n  — количество сердец, за которым следует n троек натуральных чисел xi yi di.

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

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

Ограничения

1 ≤ n ≤ 102

1 ≤ xi, yi, di ≤ 50

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
4 4 3
7 7 6
17 11 1

./\./\............
/..^..\..^........
\./.\././.\.......
./...\./...\......
/.\./.V.....\.....
\..V......../.....
.\........./......
..\......./.......
...\...../...../V\
....\.../......\./
.....\./........V.
......V...........

Задача F. Водовод на о. Русский ≡

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

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

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида ri, ci, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5
2 
3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
3 
3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6
4 
3 3
...
.##
...

NO

Задача G. Knapsack problem ≡

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.

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

Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите −1.

Ограничения

1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 7
1 5 6
 
1 0 1
0.131s 0.006s 25