Задача 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. Кластер ≡

Условие

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

Пусть кластер состоит из N компьютеров и сервера. Компьютеры имеют разную производительность, так что i-й компьютер заканчивает расчёт одной подзадачи за t_i секунд. По окончании расчёта компьютер отправляет результаты на сервер, получает в ответ следующую подзадачу, тратит на неё ещё t_i секунд, и т.д. Таким образом, в одну секунду на сервер могут прийти ответы от нескольких компьютеров.

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

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

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

В выходном файле должно содержаться количество секунд до максимальной загрузки. Так как это число может быть очень велико, оно должно быть выведено в виде разложения на простые множители. При этом множители должны быть отсортированы по возрастанию и разделяться символом '*' (ASCII 42). Если степень вхождения простого числа больше единицы, следует указать её вслед за числом, разделив их символом '^' (ASCII 94).

Например: число 25 будет иметь вид: 5^2, а число 3000 — 2^3*3*5^3.

Ограничения

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

2
2 3

2*3

3 18 18 18

2*3^2

Задача C. Плотность населения ≡

Условие

После проведения переписи населения Флатландии все данные были нанесены на карту. Прямоугольная карта Флатландии была разделена на клетки единичного размера. Число жителей в каждой клетке изменяется от 0 до 9.

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

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

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

Ограничения

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

3 3 1
020
102
020

1 2 3 2

Задача D. Вектор ≡

Условие

Дан целочисленный вектор P₁, P₂, …, P_N. Над любым вектором, состоящим из двух и более элементов, определим операцию сжатия, состоящую в замене произвольной пары соседних элементов на их сумму. Например, вектор 1 2 3 в результате сжатия может превратиться в вектор 3 3 либо 1 5.

Требуется путем последовательного применения операции сжатия получить из исходного вектора вектор максимально возможной длины, все элементы которого не меньше A и не больше B.

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

Входной файл содержит тройку чисел N A B, за которой следует N чисел P₁, P₂, …, P_N.

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

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

Ограничения

Все числа во входном файле целые.

1 ≤ N ≤ 1000, 0 ≤ A, B, p_i ≤ 10⁶.

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

7 3 6
3 1 1 1 2 2 2

3
5 3 4

7 3 3
3 1 1 1 2 2 2

0

6 20 50
29 5 19 37 43 5

4
29 24 37 48

Задача E. Ближайшие точки ≡

Условие

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: "На числовой прямой задано n точек. Необходимо найти среди них две ближайшие". Расстояние между двумя точками числовой прямой x и y равно |x − y|.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

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

Первая строка входного файла содержит количество точек n.

Вторая строка входного файла содержит n чисел x_i - координаты заданных точек числовой прямой.

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

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

Во второй строке выходного файла необходимо вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от 1 до n в порядке, в котором они заданы во входной файле.

Если ответов несколько, выведите любой из них.

Ограничения

2 ≤ n ≤ 10⁵

x_i - целые числа, не превосходящие 10⁹ по абсолютной величине

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

5
10 3 6 2 5

1
2 4

Задача F. Чебурашка и бильярд ≡

Условие

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

Затем Чебурашка установил бильярдный шарик внутрь рамки, в точку с координатами (x; y) и ударил по нему, в результате чего шарик начал двигаться с вектором скорости (V_x; V_y). Шарик движется без трения, т.е. скорость шарика не уменьшается со временем. При ударе об один бортик шарик отскакивает без потери скорости под углом, равным углу падения. Если шарик ударяется сразу о два бортика (т.е. попадает точно в угол), то вектор его скорости меняет направление на противоположное. Чебурашке интересно, какие координаты будет иметь шарик через время t, и он просит вас написать программу, отвечающую на этот вопрос.

Диаметр шарика пренебрежимо мал по сравнению с a.

Рекомендуется рассмотреть частичные решения

• За время t не происходит ни одного удара о бортик.
• За время t происходит ровно один удар о бортик.

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

Во входном файле содержится целое число a, за которым следуют вещественные числа x y V_x V_y t, заданные с точностью 10⁻⁵

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

Ограничения

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

4 0 0 0.01 0.01 300

1.000 1.000

5 2 1 -1 3 2

0.000 3.000

10 1 1 -200 -1000 6891.99971

1.058 1.290

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

Условие

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

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

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

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

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

Ограничения

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

6 2
1 1 2 2 1 1

3 5 6

Задача H. Миллион Z ≡

Условие

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

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

Ограничения

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

3
A 1 50
X 90 1000
D 30 1000000

2

Задача I. Сухой фотограф ≡

Условие

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

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

Ограничения

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

100 100 4 50
0 0
100 0
0 100
100 100

50 50

Задача Z. Змейка ≡

Условие

Подружки Катя и Надя уже давно играют в игру «Змейка».

Поле для игры представляет собой клетчатый квадрат со стороной n. В каждой клетке квадрата может быть либо зеленая лужайка, либо пень. Изначально в их распоряжении находится змейка длиной 1. За один шаг змейка может перемещаться в одном из 4х направлений: вверх, вниз, вправо и влево. Однако змейка не может ползать по пенькам.

Так же на поле имеется одно яблоко. В момент, когда змейка наползает на яблоко, яблоко пропадает и появляется в другом месте, а длина змейки увеличивается на единицу. (В этот момент туловище змейки продляется на ту клетку, из которой только что выполз хвост). Обратите внимание, что змейка не может переползать через саму себя или ползти в клеточку, в которой находится ее хвост (хвост уже старенький и выползти не успевает).

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

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

В первой строке входного файла находится число n. В последующих n строках содержится по n символов задающих лабиринт. Лужайке соответствует символ ‘.’, пню – ‘#’, i-ому яблоку цифра i

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

В единственной строке выходного файла должно содержаться одно число – минимальное требуемое число ходов. Если собрать все яблоки не возможно, выведите -1.

Ограничения

2 ≤ n ≤ 10.

2 ≤ k ≤ 8.

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

3
#3.
1.2
#4#
        

6

3
#43
1.2
#5#
        

-1