Задача A. Форматирование текста ≡

Условие

Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: «,», «.», «?», «!», «-», «:» и «'» (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из заглавных и прописных букв латинского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк.

Дальнейшее использование исходного текста предполагает его форматирование, которое осуществляется следующим образом. Каждый абзац должен быть разбит на строки, каждая из которых имеет длину не больше W. Первая строка каждого абзаца должна начинаться с отступа, состоящего из B пробелов. Слова внутри одной строки должны быть разделены ровно одним пробелом. Если после слова идет один или несколько знаков препинания, они должны следовать сразу после слова без дополнительных пробелов. Если очередное слово вместе со следующими за ним знаками препинания помещается на текущую строку, оно размещается на текущей строке. В противном случае, с этого слова начинается новая строка. В отформатированном тексте абзацы не должны разделяться пустыми строками. В конце строк не должно быть пробелов.

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

Система оценивания

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

Правильные решения для тестов, в которых соседние слова разделены ровно одним пробелом и все знаки препинания следуют сразу за словами и не отделены от них пробелами или символами перевода строк, будут оцениваться из 30 баллов.

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

Первая строка входного файла содержит два целых числа: W и B

Затем следует одна или более строк, содержащих заданный текст.

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

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

Ограничения

5 ≤ W ≤ 100

1 ≤ B ≤ 8

B < W

Длина слова в тексте вместе со следующими за ними знаками препинания не превышает W, а длина первого слова любого абзаца вместе со следующими за ним знаками препинания не превышает (W − B).

Размер входного файла не превышает 100 Кбайт. Длина каждой строки во входном файле не превышает 250.

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

20 4
Yesterday, 
All my troubles seemed so far away, 
Now it looks as though they're here to stay, 
Oh, I believe in yesterday. 

Suddenly, 
I'm not half the man I used to be, 
There's a shadow hanging over me, 
Oh, yesterday  came suddenly...

    Yesterday, All
my troubles seemed
so far away, Now it
looks as though
they' re here to
stay, Oh, I believe
in yesterday.
    Suddenly, I' m
not half the man I
used to be, There' s
a shadow hanging
over me, Oh,
yesterday came
suddenly...

Задача B. Космические исследования ≡

Условие

Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50 × 50 километров. Если разделить ее на квадраты размером 1 × 1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером K × K километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами X и Y от 1 до K километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка K определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

Пояснения к примерам

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Система оценивания

Решения, правильно работающие только для K = 1, будут оцениваться из 30 баллов.

Решения, правильно работающие только для K > 1 и 1 < N ≤ 15, будут оцениваться из 30 баллов.

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

Первая строка входного файла содержит два целых числа: N и K

Следующие N строк содержат по два целых числа: X_i и Y_i — координаты объектов в заданной области.

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

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

Ограничения

1 ≤ N ≤ 10³

1 ≤ K ≤ 5

1 ≤ X_i, Y_i ≤ 50

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

4 1
1 1
10 2
1 3
10 4

30

4 2
1 1
10 2
1 3
10 4

10

1 1
1 1

0

3 3
3 3
3 6
6 3

7

Задача C. Делители ≡

Условие

Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из k чисел (a₁, a₂, …, a_k), если выполнены следующие условия:

1. каждое из чисел a_i является делителем числа n;
2. выполняется неравенство a₁ < a₂ < … < a_k;
3. числа a_i и a_i+1 для всех i от 1 до k − 1 являются взаимно простыми;
4. произведение a₁ a₂… a_k не превышает n.

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

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

Система оценивания

Правильные решения для тестов, в которых n ≤ 1000 и k = 2, оцениваются из 30 баллов.

Правильные решения для тестов, в которых k = 2, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая n ≤ 1000 и k = 2).

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

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

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

В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа n.

Ограничения

2 ≤ n ≤ 10⁸

2 ≤ k ≤ 10

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

90 3

16

10 2

4

Задача D. Дом у дороги ≡

Условие

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

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

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

Система оценивания

Правильные решения для тестов, в которых n ≤ 100 и все прямые параллельны, оцениваются из 20 баллов.

Правильные решения для тестов, в которых n ≤ 100 и все прямые параллельны осям координат, оцениваются из 20 баллов.

Правильные решения для тестов, в которых n ≤ 100, оцениваются из 70 баллов (в эти баллы включаются также по 20 баллов за случаи, описанные в предыдущих двух абзацах).

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

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

Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x₁, y₁, x₂ и y₂ и представляет собой прямую, проходящую через точки (x₁, y₁) и (x₂, y₂).

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

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

Ответ должен иметь абсолютную или относительную погрешность не более 10⁻⁶, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения |x−y| / max(1,|y|) не превышает 10⁻⁶.

Ограничения

1 ≤ n ≤ 10⁴. Координаты заданных точек не превышают по модулю 10⁴. Точки (x₁, y₁) и (x₂, y₂) ни для какой прямой не совпадают.

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

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

0.5000000004656613 0.4999999995343387

Problem E. K-Graph Oddity ≡

Statement

You are given a connected undirected graph with an odd number of vertices. The degree of the vertex, by definition, is the number of edges incident to it. In the given graph the degree of each vertex does not exceed an odd number k. Your task is to color the vertices of this graph into at most k distinct colors, so that the colors of any two adjacent vertices are distinct.

The pictures below show two graphs. The first one has 3 vertices and the second one has 7 vertices. In both graphs degrees of the vertices do not exceed 3 and the vertices are colored into at most 3 different colors.

Input file format

The first line of the input file contains two integer numbers n and m, where n is the number of vertices in the graph (3 ≤ n ≤ 9999, n is odd), m is the number of edges in the graph (2 ≤ m ≤ 100 000). The following m lines describe edges of the graph, each edge is described by two integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the vertex numbers connected by this edge. Each edge is listed at most once. The graph in the input file is connected, so there is a path between any pair of vertices.

Output file format

On the first line of the output file write a single integer number k — the minimal odd integer number, such that the degree of any vertex does not exceed k. Then write n lines with one integer number c_i (1 ≤ c_i ≤ k) on a line that denotes the color of i-th vertex.

The colors of any two adjacent vertices must be different. If the graph has multiple different colorings, print any of them. At least one such coloring always exists.

Sample tests

3 2
1 3
3 2

3
1
1
2

7 8
1 4
4 2
2 6
6 3
3 7
4 5
5 6
5 2

3
1
1
1
2
3
2
2

Problem F. Bipartite graph ≡

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

Output file format

Constraints

Sample tests

3 2
1 2  1 3

BIPARTITE

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

NO

Задача G. Быстрый Дейкстра ≡

Условие

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

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

Ограничения

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

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача H. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

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

3 1
2 3

2

Задача I. Обход в глубину ≡

Условие

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования — паскале и си.

var
  a: array [1..maxn, 1..maxn] 
       of boolean;
  visited: array [1..maxn] 
       of boolean;

procedure dfs(v: integer);
var 
  i: integer;
begin
  writeln(v);
  visited[v] := true;
  for i := 1 to n do begin
    if a[v][i] and 
        not visited[i] then 
    begin
      dfs(i);
      writeln(v);
    end;
  end;
end;

procedure graph_dfs;
var
  i: integer;
begin
  for i := 1 to n do
    if not visited[i] then
    	dfs(i);
end;

int a[maxn + 1][maxn + 1];
int visited[maxn + 1];

void dfs(int v) {
  printf("%d\n", v);
  visited[v] = 1;
  for (int i = 1; i <= n; i++) {
    if ((a[v][i] != 0) && 
        (visited[i] == 0)) {
      dfs(i);
      printf("%d\n", v);
    }
  }
}

void graph_dfs() {
  for (int i = 1; i <= n; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }
}

Петина программа хранит граф с использованием матрицы смежности в массиве "a" (вершины графа пронумерованы от 1 до n). В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

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

Ограничения

1 ≤ n ≤ 300

1 ≤ l ≤ 2 n−1

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

6 10
1
2
3
2
4
2
1
5
6
5

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

Problem J. ACM Computer Factory ≡

Statement

As you know, all the computers used for ACM contests must be identical, so the participants compete on equal terms. That is why all these computers are historically produced at the same factory.

Every ACM computer consists of P parts. When all these parts are present, the computer is ready and can be shipped to one of the numerous ACM contests.

Computer manufacturing is fully automated by using N various machines. Each machine removes some parts from a half-finished computer and adds some new parts (removing of parts is sometimes necessary as the parts cannot be added to a computer in arbitrary order). Each machine is described by its performance (measured in computers per hour), input and output specification.

Input specification describes which parts must be present in a half-finished computer for the machine to be able to operate on it. The specification is a set of P numbers 0, 1 or 2 (one number for each part), where 0 means that corresponding part must not be present, 1 — the part is required, 2 — presence of the part doesn't matter.

Output specification describes the result of the operation, and is a set of P numbers 0 or 1, where 0 means that the part is absent, 1 — the part is present.

The machines are connected by very fast production lines so that delivery time is negligibly small compared to production time.

After many years of operation the overall performance of the ACM Computer Factory became insufficient for satisfying the growing contest needs. That is why ACM directorate decided to upgrade the factory.

As different machines were installed in different time periods, they were often not optimally connected to the existing factory machines. It was noted that the easiest way to upgrade the factory is to rearrange production lines. ACM directorate decided to entrust you with solving this problem.

Input file format

Output file format

Output the maximum possible overall performance, then M — number of connections that must be made, then M descriptions of the connections. Each connection between machines A and B must be described by three positive numbers A B W, where W is the number of computers delivered from A to B per hour.

If several solutions exist, output any of them.

Constraints

Sample tests

3 4
15  0 0 0  0 1 0
10  0 0 0  0 1 1
30  0 1 2  1 1 1
3   0 2 1  1 1 1

25 2
1 3 15
2 3 10

3 5
5   0 0 0  0 1 0
100 0 1 0  1 0 1
3   0 1 0  1 1 0
1   1 0 1  1 1 0
300 1 1 2  1 1 1

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

2 2
100  0 0  1 0
200  0 1  1 1

0 0

Задача K. Политическая карта ≡

Условие

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

Археологам стало очень интересно, сколько же государств существовало на планете Земля в те отдаленные геологические эпохи, когда эта игра занимала умы множества несостоявшихся политиков каждый вечер. Кто знает, может тогда еще не прошло время феодальной раздробленности и их счет шел на тысячи... Чтобы удовлетворить свое любопытство, ученые сделали множество скриншотов, прокрутив карту на различные позиции, а потом склеили их. В результате получился двумерный массив пикселей, слишком большой, чтобы посчитать количество стран вручную. И как только эти древние люди могли держать в голове информацию о таком количестве игроков глобальной геополитики...

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

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

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

Следующие H строк содержат по W целых чисел от 1 до 4 — цвета пикселей.

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

В выходной файл выведите единственное целое число — количество стран на карте

Ограничения

1 ≤ W, H ≤ 1000

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

4 1
1 2 1 2

4

3 3
1 1 2
2 1 1
2 1 2

4

Задача L. K-ая порядковая статистика ≡

Условие

K-ой порядковой статистикой N-элементной последовательности A_N называется число A_K, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность A_N задаётся следующим образом. A₁ = P, A_i = (A_i−1 ⋅ Q) mod V.

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

Во входном файле содержатся целые числа Q V P N K

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

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2³¹−1

1 ≤ K ≤ N ≤ 4 ⋅ 10⁷

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

343 32767 3 10 7

16478

Задача M. Knapsack problem ≡

Условие

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

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

Ограничения

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

3 7
1 5 6

1 0 1

Задача N. LCA ≡

Условие

Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1. Найдите LCA для некоторых пар вершин.

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

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

Ограничения

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

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

1
3

Задача O. LCA на полном бинарном дереве ≡

Условие

Дано бесконечное полное бинарное дерево. Его вершины пронумерованы следующим образом: корень имеет номер 1, для каждой вершина с номером n ее левый ребенок имеет номер 2*n+1, а правый 2*n.

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

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

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

Ограничения

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

12 7

3

Задача P. Буратино ≡

Условие

Папа Карло сменил работу: теперь он работает в мастерской, и целый рабочий день занимается тем, что забивает гвоздики. Чтобы ему было не скучно, у него в мастерской стоит постоянно работающий телевизор. К сожалению, производительность папы Карло напрямую зависит от его настроения, а оно, в свою очередь, — от того, что в данный момент показывают по телевизору. Правда, пока папа Карло забивает гвоздик, он не обращает ни малейшего внимания на телевизор, и поэтому скорость его работы зависит только от того, что показывали по телевизору в тот момент, когда он только начал забивать этот гвоздик. Забив очередной гвоздик, он обязательно мельком смотрит в телевизор (его настроение, естественно, меняется), и после этого он может либо сразу начать забивать следующий гвоздик, либо отдохнуть несколько секунд или даже минут, смотря телевизор.

Папа Карло начинает работу ровно в 9 часов. С 13 часов у него начинается обеденный перерыв. При этом если он незадолго до обеда хочет начать вбивать гвоздик, но понимает, что до перерыва он не закончит эту работу, то он и не начинает ее. Аналогично в 14 часов он вновь приступает к работе, а в 18 уходит домой. Это значит, что в 9:00:00 (аналогично, как и в 14:00:00) он уже может начать забивать гвоздик. Если, например, в 12:59:59 (аналогично, в 17:59:59) он хочет начать вбивать гвоздик, и на это у него уйдет 1 секунда, то он успевает вбить гвоздик до обеда (до окончания работы соответственно), а если 2 — то уже нет.

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

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

Во входном файле записано расписание телевизионных передач с 9:00:00 до 18:00:00 в следующем формате. В первой строке число N — количество телевизионных передач в этот период. В каждой из последующих N строк записано описание одной передачи: сначала время ее начала в формате ЧЧ:ММ:СС (ЧЧ — две цифры, задающие часы, ММ — две цифры, задающие минуты начала, СС — две цифры, задающие секунды начала). А затем через один или несколько пробелов число T_i — время в секундах, которое папа Карло будет тратить на забивание одного гвоздика, если он перед этим увидит по телевизору эту передачу.

Передачи записаны в хронологическом порядке. Первая передача всегда начинается в 09:00:00. Можно считать, что последняя передача заканчивается в 18:00:00.

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

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

Ограничения

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

2
09:00:00 3600
14:00:00 3600

8

4
09:00:00 1800 
12:59:31 10
13:45:23 1800
15:00:00 3600

14

Задача Q. Васины очки ≡

Условие

Вася в казино играет в интересную игру.

Сначала он платит вступительный взнос за игру и в обмен на деньги получает право играть. Более того, за уплаченные деньги он сразу получает X очков.

На автомате, в который он играет, есть три кнопки. Когда он нажимает первую, к его очкам добавляется A очков. Когда нажимает вторую - добавляется B. Когда нажимает третью - добавляется C очков.

Ему разрешается сначала несколько раз (или ни разу) нажать третью кнопку, и затем несколько раз (или ни разу) - первую. Нажимать вторую кнопку Васе запрещено.

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

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

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

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

Во входном файле записаны числа X, A, B, C, Y. Каждое из этих чисел - целое из диапазона [-10⁹, 10⁹].

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

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

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

1 1 0 -1 10

-1

1 2 4 -2 -20

0

1 1 2  3 10

4

Problem R. Triathlon ≡

Statement

Triathlon is an athletic contest consisting of three consecutive sections that should be completed as fast as possible as a whole. The first section is swimming, the second section is riding bicycle and the third one is running. The speed of each contestant in all three sections is known. The judge can choose the length of each section arbitrarily provided that no section has zero length. As a result sometimes she could choose their lengths in such a way that some particular contestant would win the competition.

Input file format

The first line of the input file contains integer number N, denoting the number of contestants. Then N lines follow, each line contains three integers V_i, U_i and W_i, separated by spaces, denoting the speed of i-th contestant in each section.

Output file format

For every contestant write to the output file one line, that contains word "Yes" if the judge could choose the lengths of the sections in such a way that this particular contestant would win (i.e. she is the only one who would come first), or word "No" if this is impossible.

Constraints

1 ≤ N ≤ 100

1 ≤ V_i, U_i, W_i ≤ 10000

Sample tests

9
10 2 6
10 7 3
5 6 7
3 2 7
6 2 6
3 5 7
8 4 6
10 4 2
1 8 7

Yes
Yes
Yes
No
No
No
Yes
No
Yes

Задача S. Скобки ≡

Условие

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

Так, последовательность ()(()) является правильной скобочной последовательностью, потому что она может, например, встречаться в выражении (2+2):(3–(5–2)+4), а последовательности (() и ())( не являются таковыми. Легко видеть, что существует пять правильных скобочных последовательностей, состоящих ровно из шести скобок (по три скобки каждого типа — открывающих и закрывающих): ((())), (()()), (())(), ()(()) и ()()().

Агнесса заинтересовалась простейшими преобразованиями правильных скобочных последовательностей. Для начала Агнесса решила ограничиться добавлением скобок в последовательность. Она очень быстро выяснила, что после добавления одной скобки последовательность перестаёт быть правильной, а вот добавление двух скобок иногда сохраняет свойство правильности. Например, при добавлении двух скобок в различные места последовательности ()() можно получить последовательности (()()), (())(), ()(()) и ()()(). Легко видеть, что при любом способе добавления двух скобок с сохранением свойства правильности одна из новых скобок должна быть открывающей, а другая — закрывающей.

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

Таким образом, если в полученной последовательности добавленная открывающая скобка стоит в позиции i, а добавленная закрывающая — в позиции j, то два способа, соответствующие парам (i 1, j 1) и (i 2, j 2), считаются различными, если i 1 ≠ i 2 или j 1 ≠ j 2.

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

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

Подзадача 1 (40 баллов): Величина n (количество скобок каждого типа) не превосходит 50.

Подзадача 2 (30 баллов): Величина n (количество скобок каждого типа) не превосходит 2500.

Подзадача 3 (30 баллов): Величина n (количество скобок каждого типа) не превосходит 50 000.

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

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

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

()

7

()()

17

(())

21

Задача T. Парк аттракционов ≡

Условие

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

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

Время перемещения участников между автоматами, а также между автобусом и павильоном считается равным нулю. Каждый из участников в любой момент времени может как играть на автомате, так и ждать своей очереди, например, гуляя по парку. Для каждого из M (M ≤ N) автоматов известно время игры на нём t_i (1 ≤ i ≤ M). Прервать начатую игру на автомате невозможно. Автобус привозит всех участников олимпиады в парк одновременно в нулевой момент времени.

Требуется написать программу, которая по заданным числам N, M и t_i определяет оптимальное расписание игры на автоматах для каждого из участников.

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

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

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

2 1
2

4

1 0

1 2

3 2
2 1

6

1 0
2 2

1 2
2 4

2 0
1 4