Задача A. Максимальный поток (несколько истоков и стоков)

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

Условие

Требуется найти максимальный поток в сети с несколькими истоками и стоками.

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

В первой строке входного файла содержится число N  — количество вершин в сети. Далее следует N чисел ai ∈ 0, 1, 2. Если ai = 0, то i-ая вершина  — это обычный узел; если ai = 1 то i-ая вершина  — это исток; если ai = 2 то i-ая вершина  — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.

Далее следует матрица целых чисел U размером N × N. 0 ≤ Uij ≤ 106  — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.

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

В выходной файл выведите единственное число  — объем максимального потока.

Ограничения

2 ≤ N ≤ 50

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
0 100
1000 0
100
2
4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0
3
3
10
0 0 1 0 1 2 2 0 2 0 
0 100 0 0 0 1 0 0 0 0
0 0 0 0 0 120 0 0 0 0
100 0 0 0 0 0 0 0 0 0
10 10 0 0 0 0 0 20 0 20
0 0 0 50 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 15 0 15 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0
141

Задача B. Быстрое двудольное паросочетание

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

Условие

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

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

Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.

Далее содержится описание m ребер в виде списка пар целых чисел (ui, vi). Наличие пары (ui, vi) означает ребро между ui-ой вершиной левой доли и vi-ой вершиной правой доли.

Гарантируется, кратных рёбер в графе нет.

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

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

Ограничения

1 ≤ p, q ≤ 105

1 ≤ m ≤ 2 * 105

1 ≤ ui ≤ p

1 ≤ vi ≤ q

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 6
1 1
1 2
2 1
2 2
2 3
3 2
3
1 1
2 3
3 2

Problem C. Cosmonaut

Author:I. Ludov   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

Statement

In the year 2030 International Space Station 2 was launched. It had a torus shape to enable artificial gravity generation. (A torus is a circular tube with circular cross-section). Advanced spacesuit technology and micro-rocket engines allowed for prolonged and easy spacewalks.

During one such spacewalk a crew member was looking at the station from an open space and wondered where should he fly to get to the station surface as fast as possible. Since he was cosmonaut and not astronaut, he had good mathematics education. So after a return to the station he quickly wrote a program which constructed the shortest line from any given point in space to the surface of a given torus.

Can you do this too?

Input file format

Input file contains eleven integer numbers:
xc yc zc — coordinates of torus center,
xd yd zd — a vector collinear to torus symmetry axis,
r1 — distance from the center of the tube to the center of the torus,
r2 — radius of the tube,
x y z — coordinates of the point in space.

Output file format

Output file must contain real numbers xm ym zm — coordinates of the nearest torus point with at least 15 correct digits after decimal point. If there is more than one nearest point, output any of them.

Constraints

 − 106 xc, yc, zc, xd, yd, zd, x, y, z ≤ 106,
0 < r2 < r1 ≤ 106, |xd| + |yd| + |zd| > 0,
point (x, y, z) lies either outside the torus or on its surface.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
0 0 0
0 0 1
10 1
1 0 0
9.0 0.0 0.0
2
5 6 7 1 1 1 50 10 3 2 1
32.5203582126019 5.16103228678696 -22.1982936390279

Задача D. Кубики

Автор:Жюри XVIII городской олимпиады школьников Санкт-Петербурга по информатике   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие - всего лишь отражение в зеркале.

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


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

Первая строка входного файла содержит число N и количество различных цветов, в которые могут быть раскрашены кубики - M. Следующая строка содержит N целых чисел от 1 до M - цвета кубиков.

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

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

Ограничения

1 ≤ N,M ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2
1 1 2 2 1 1
3 5 6

Задача E. Нормальная палиндромика

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

Условие

Палиндром — это строка, которая одинаково читается и в прямом, и в обратном порядке. Например, kazak — палиндром, а kazachka — нет. По данной строке S требуется найти такую кратчайшую (возможно, пустую) строку P, что строка S + P будет палиндромом.

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

Во входном файле содержится строка S, состоящая из маленьких латинских букв.

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

В выходной файл необходимо вывести строку P.

Ограничения

Длина исходной строки не превосходит 300000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcc
ba
2
abcd
cba

Задача F. Есть ли пересекающиеся отрезки?

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

Условие

Напишите программу, определяющую, имеется среди данных n отрезков на плоскости пара пересекающихся.

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

Входной файл содержит число n за которым следует описание отрезков в формате x1 y1 x2 y2.

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

Выходной файл должен содержать слово NO если искомой пары не существует. В противном случае, выходной файл должен содержать слово YES и пару чисел - номера отрезков. Отрезки нумеруются с единицы.

Ограничения

 − 103 ≤ x1, y1, x2, y2 ≤ 103

2 ≤ n ≤ 105

Отрезки не вырождаются в точки

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 3 6
4 3 6 2
6 3 2 2
YES
2 3

Problem G. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  
Maximum points:100  

Statement

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

Задача H. Выборы заведующего кафедрой

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

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области.

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно mj > mi, pj > pi, tj > ti.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел mi pi ti.

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

Задача I. Песочные часы

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:clocks.in   Ограничение памяти:64 Мб
Выходной файл:clocks.out  
Максимальный балл:100  

Условие

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

Порывшись на чердаке, Петя нашел двое старых песочных часов — на a и на b минут соответственно. Каждые песочные часы состоят из двух половинок, одна из которых исходно заполнена песком.

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

Песок пересыпается равномерно и с одинаковой скоростью, вне зависимости от количества песка, оставшегося в верхней половине. В первых часах весь песок пересыпается за a минут, во вторых — за b минут.

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

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

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

Во входном файле заданы целые числа a, b и t.

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

Выведите последовательность инструкций для Пети. Каждая инструкция — это пара <событие>: <действие>. События бывают трех типов: Действия бывают четырех типов: Если подогреть суп с использованием этих песочных часов не удастся, выведите в выходной файл одно слово — «Impossible».

Ограничения

1 ≤ a, b ≤ 500, 1 ≤ t ≤ 105

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

Входной файл (clocks.in) Выходной файл (clocks.out)
1
5 7 9
Initially: flip A and B
When A stops: flip A
When B stops: flip A
When A stops: ready
2
2 4 11
Impossible

Problem J. Improve RLE

Author:I. Ludov, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

Statement

A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system — ACM (Advanced Compression Method) — which will incorporate all of his brilliant ideas.

The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv), he asks you to implement this simple, yet important part of a system.

An algorithm should replace repeating substrings of source string with a single instance of substring concatenated with the number of repetitions. If some substring should not be repeated, it is concatenated with number 1.

Your program must find the shortest possible compression of the given string.

Input file format

A single line of input file contains the string to be compressed. It may contain spaces, but does not contain digits as Kumar has invented a complex digit-escaping system to prevent uncompressing ambiguity.

Output file format

Output file must contain minimal length compression of the source string. There should be no extra whitespace characters before or after the string.

Constraints

Length of the source string is from 1 to 1000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
aaaaaaaaaa
a10
2
a c c c
a1 c3
3
abc
abc1

Problem K. Help Gridland environment

Author:I. Ludov   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

Statement

The Gridland is a small country located on a beautiful hilly landscape. It is well known for its achievements in the fields of nanotechnology and car industry.

The country has many cities, located in the nodes of W × H grid with square cells. All roads between cities go straight along the lines of the grid in either north-south or east-west direction and have the same length.

A young scientist Vasya Reshetkin developed a new hi-tech car powered by nuclear batteries. The car is very energy-efficient: while going uphill, the car consumes a fixed amount of energy per unit of distance, and while going downhill it stops the engine, consuming no energy at all. That means that the amount of energy required to travel along the fixed route from A to B and then back from B to A depends only on the distance, and not on the inclination profile of the road.

Thus if the car requires a units of energy to move from a city to its neighbor, then moving back will require L − a units, where L is the same for all cities. To simplify maintenance, each battery was designed to store exactly L units of energy.

Unfortunately, prolonged storage of half-used batteries may lead to nuclear contamination of the environment, so it is important that the batteries are always used fully.

Your country is known for achievements in computer programming. So you have been given a job to write a program that plans a route from city A to city B such that it will use exactly L × k units of energy for some integer k. This route may not be the shortest one, but this is a price Gridland citizens are willing to pay for environment preservation.

Input file format

First line of input file contains integers L W H — battery capacity, width and height of city grid respectively.

Second line contains integers rA cA rB cB — row and column of city A and row and column of city B respectively. Rows span from west to east in order of increasing column numbers. Columns span from north to south in order of increasing row numbers. All numbering is zero-based.

Next H − 1 lines contain 2 * W − 1 integers e1 s1… eW − 1 sW − 1 sW, where ei is the energy required to move from i-th city in the row to its eastern neighbor, and si — energy to move to its southern neighbor.

Last line contains W − 1 integers ei — energy required to move from the i-th city in the southernmost row to its eastern neighbor.

Output file format

Output file must contain a single line with the string of symbols "N", "S", "E", "W", describing a route from city A to city B which requires integer amount of batteries of capacity L. It there is more than one answer, output any of them not exceeding 3(H + W)L in length. If there is no answer, output a single symbol "X".

Constraints

2 ≤ L, W, H ≤ 1000, 0 ≤ ei, si ≤ L

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 2
1 0 0 2
4 2 5 2 4
2 2
ENE

Задача L. Спортивная ходьба

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

Условие

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

Трасса для спортивной ходьбы представлена в виде ломаной на плоскости с вершинами в точках (x1, y1), (x2, y2), … (xk, yk). Ломаная может иметь самокасания и самопересечения. Судья с номером i неподвижно стоит в точке (cxi, cyi) и обозревает вокруг себя круг с радиусом ri.

Таким образом, каждая точка трассы обозревается некоторым (возможно, нулевым) количеством судей. Напишите программу, которая по заданной трассе и положению судей определит длину участков, обозреваемых ровно m судьями для целых m от 0 до n.

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

Входной файл содержит целые числа n k. Далее содержится n троек целых чисел cxi cyi ri, задающих положение судей. Далее содержится k пар целых чисел xj yj, задающих ломаную.

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

Выходной файл должен содержать n + 1 число — ответы для 0, 1, …, n судей с точностью не менее 10 − 6.

Ограничения

1 ≤ n ≤ 1000;

2 ≤ k ≤ 1000;

 − 1000 ≤ xj, yj, cxi, cyi ≤ 1000;

1 ≤ ri ≤ 1000;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4
3 0 2
6 0 2
0 0
4 0
6 0
10 0
3.000000
6.000000
1.000000

0.844s 0.016s 48