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.
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.
You are to write a program that receives a connected undirected graph and finds
all its articulation points, which are the vertices that, if removed,
leave disconnected graph.
Input file format
Input file contains two integers N and M.
Vertices are numbered with integer numbers from 1 to N.
M is the number of edges.
Each of next M lines contain pair of integers — numbers of vertices
connected by an edge. There are no pairs of equal numbers.
Output file format
Output file must contain integer representing a quantity of articulation
points, followed by numbers of corresponding vertices in arbitrary order.
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 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 receives an undirected connected graph and finds its Eulerian cycle.
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 following M lines contains a pair of
vertex numbers, connected by some edge. There is at most one edge connecting two vertices.
Output file format
Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle.
If there does not exist any Eiler cycle, output file must contain − 1.
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 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 directed unweighted graph and finds all vertices of its strong-connected
component, containing given vertex S.
Input file format
Input file contains two integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. M is the number of arcs.
Each of next M lines contain pair of integers — starting and ending vertices of some arc respectively.
There is at most one arc connecting two vertices in every direction.
Output file format
Output file must contain integer number T — amount of vertices in strong-connected component. After that, there must
be T integer numbers in ascending order — vertices of compontent themselves.
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.
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.
Once upon a time in the silent depths of digital forests there lived a Binary Witch.
She was able to forecast weather, telling for any day in the future whether it will be rainy
or sunny.
Her magic was based on the following ancient rule: let a1, a2, ..., aN be the
sequence of binary digits, where ai=0 indicates that i-th day was rainy, and ai=1 -
that it was sunny. To predict the weather in day N + 1, consider the t-postfix
aN-t+1, aN-t+2, ..., aN consisting of the last t elements. If that postfix is encountered some-
where before the position N - t + 1, i.e. if there is such k ≤ N - t, that
ak = aN-t+1, ak+1 = aN-t+2, ..., ak+t-1 = aN then the predicted value will be ak+t.
If there is more than one occurrence of t-postfix, then the rightmost one (with
maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently
for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she
predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all
previous days are predicted correctly, so if first predicted value is b, then we make
forecast for day N + 2 based on N + 1 values, where aN+1 = b.
Because the witch was burned long ago, your task is to write a program to per-
form her arcane job.
Input file format
First line of input file contains two integers N and L, separated by space.
Second line contains a string of N characters "0" and "
1".
Output file format
Output file must contain a single string of L characters, which are forecasts
for days N+1, N+2, ..., N+L.
The game of fool is played with a small set of cards, which includes nine
ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits
each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen
of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a
trump. During the game, the card beats another card, if either it has the same suit and
higher rank, or it is a trump, while the beaten card is not.
In the game, a move proceeds as following. First player puts one of his cards on
the desk, and the second player can either beat it with one of his cards, putting his card
over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in
any of his remaining cards, which has same rank as any card already on the desk. This
card, in turn, may be beaten or taken together with all other cards on the desk, etc. For
example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and
hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then
flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten
with 7h, so the second player has to take it.
Your task is to write a program that, given the trump suit and first and second
playerTs cards, determines for the first player such a move as to eventually make the
second player take.
Your task is to write a program that, given the trump suit and first and second
playerTs cards, determines for the first player such a move as to eventually make the
second player take.
If there is more than one such move, the program must find one with smallest
rank. If there is several moves with smallest rank, program must choose the card with
the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the
example above, second player could beat Kd with 7h, thus preventing further flips. On
the other hand, move of Qh will be immediately taken.
Input file format
In the first line of input file there is a single character h, s, d, or c, determining a
trump suit. On the second line there is a string denoting first playerTs cards, and on the
third line S the string with the second playerTs cards. All cards are different, and the
players have equal number of cards.
Output file format
Output file must contain a single line with either a card to move or a string "NO",
if a program was unable to find it.
You are to write a program emulating a very simple spreadsheet application. It
works with a table with 9 rows, from "1" to "9", and 26 columns, from "A" to "Z".
Table cells are referenced by names composed of column and row codes, ex. "B1",
"S8".
Each cell contains an expression up to 255 characters long. Expressions use
integer constants, cell references, parenthesis, operators "+", "-", "*", and "/" (whole
division). For example: 567, E8/2, (3+B3)*(C4O1) are all valid expressions. All opera-
tors are whole, all arguments and results are guaranteed to be less than 1000000. Divi-
sion by zero yields zero.
If the value of the cell referenced by some expression is not defined, it is pre-
sumed to be 0 (zero). The situation when two or more cells are mutually dependent on
each other is considered a special case of circular reference.
Input file format
First input line contains number of expressions N. Following N lines are in format
<Cell reference>=<expression>. All expressions are correct, and each cell is
defined by at most one expression.
Output file format
Output file must contain single line with either the value of the cell "A1" or number
1000000 (one million) if the value of A1 cannot be computed due to a circular reference.
In some simplistic DBMS named PreQueL, the only column type allowed is
CHAR(1) (a single character), and furthermore, its values are restricted to English upper-
case letters (eAi to eZi). Table may contain up to 9 columns, numbered from 1 to 9.
Tables themselves are named with lower-case English letters (eai to ezi).
The only database query possible first joins all the tables, then selects some rows
according to conditions in one of two forms: either <column>=<value> or
<column1>=<column2>, for example a2=A or b1=c4. All conditions must hold simultaneously,
as if they were connected by eANDi operator.
You must write a PreQueL processor, which, given a tables and a set of conditions,
will produce query result, i.e. those rows of a join satisfying all the conditions. Resulting
rows must be sorted alphabetically.
Input file format
The first line of input file contains of two integers o number of tables T and
number of conditions D.
Starting from the second line there are T tables represented with number of rows
RN and number of columns CN in the first line of a table, which is followed by RN lines
consisting of exactly CN characters each. D lines with conditions follow the whole set of
tables.
Output file format
Output file contains result rows, one row per line. No input query will produce
more than 1000 rows.
Constraints
1 ≤ T ≤ 26, 1 ≤ D ≤ 50, 1 ≤ CN ≤ 9, 1 ≤ RN ≤ 1000.
For each three prime numbers p1, p2 and p3, letis define Hamming sequence
Hi(p1, p2, p3), i = 1,... as containing in increasing order all the natural numbers whose
only prime divisors are p1, p2 or p3.
For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27,...
So H5(2, 3, 5)=6.
Input file format
In the single line of input file there are space-separated integers p1 p2 p3 i.
Output file format
The output file must contain the single integer - Hi(p1, p2, p3).
Constraints
All numbers in input and output are less than 1018.
Your task is to write a program, which, given two circles,
calculates the area of their intersection with the accuracy of two
digits after decimal point.
Input file format
In the single line of input file there are space-separated real numbers
x1y1r1x2y2r2.
They represent center coordinates and radii of two circles.
Output file format
The output file must contain single real number — the area.
