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

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 50

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

2
1 2
0 100
1000 0

100

4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0

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. Быстрое двудольное паросочетание ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ p, q ≤ 10⁵

1 ≤ m ≤ 2 * 10⁵

1 ≤ u_i ≤ p

1 ≤ v_i ≤ q

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

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 ≡

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

Output file format

Constraints

Sample tests

0 0 0
0 0 1
10 1
1 0 0

9.0 0.0 0.0

5 6 7 1 1 1 50 10 3 2 1

32.5203582126019 5.16103228678696 -22.1982936390279

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

Условие

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

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

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

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

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

Ограничения

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

6 2
1 1 2 2 1 1

3 5 6

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

Условие

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

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

Ограничения

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

abcc

ba

abcd

cba

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

Условие

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

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

Входной файл содержит число n за которым следует описание отрезков в формате x₁ y₁ x₂ y₂.

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

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

Ограничения

 − 10³ ≤ x₁, y₁, x₂, y₂ ≤ 10³

2 ≤ n ≤ 10⁵

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

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

3
1 1 3 6
4 3 6 2
6 3 2 2

YES
2 3

Problem G. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

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

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

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

Условие

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

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

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

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

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

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

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

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

• Initially — начальный момент времени, в последовательности должна быть ровно одна инструкция, помеченная этим событием, она должна быть первой;
• When A stops — когда заканчивает пересыпаться песок в первых часах;
• When B stops — когда заканчивает пересыпаться песок во вторых часах.

• flip A — перевернуть первые часы;
• flip B — перевернуть вторые часы;
• flip A and B — перевернуть и те и другие часы;
• ready — снять суп с плиты, инструкция с таким действием должна быть ровно одна, она должна быть последней.

Ограничения

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

5 7 9

Initially: flip A and B
When A stops: flip A
When B stops: flip A
When A stops: ready

2 4 11

Impossible

Problem J. Improve RLE ≡

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

Output file format

Constraints

Sample tests

aaaaaaaaaa

a10

a c c c

a1 c3

abc

abc1

Problem K. Help Gridland environment ≡

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 r_A c_A r_B c_B — 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 e₁ s₁… e_W − 1 s_W − 1 s_W, where e_i is the energy required to move from i-th city in the row to its eastern neighbor, and s_i — energy to move to its southern neighbor.

Last line contains W − 1 integers e_i — 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

Sample tests

5 3 2
1 0 0 2
4 2 5 2 4
2 2

ENE

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

Условие

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

Трасса для спортивной ходьбы представлена в виде ломаной на плоскости с вершинами в точках (x₁, y₁), (x₂, y₂), … (x_k, y_k). Ломаная может иметь самокасания и самопересечения. Судья с номером i неподвижно стоит в точке (cx_i, cy_i) и обозревает вокруг себя круг с радиусом r_i.

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

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

Входной файл содержит целые числа n k. Далее содержится n троек целых чисел cx_i cy_i r_i, задающих положение судей. Далее содержится k пар целых чисел x_j y_j, задающих ломаную.

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

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

Ограничения

1 ≤ n ≤ 1000;

2 ≤ k ≤ 1000;

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

2 4
3 0 2
6 0 2
0 0
4 0
6 0
10 0

3.000000
6.000000
1.000000