Задача A. Место у прохода, пожалуйста ≡

Условие

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

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

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

Ограничения

1 ≤ n, l, w, x, y, a ≤ 10⁴

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

400 3250 750 80 60 70

160

450 3250 750 80 60 70

-1

Задача B. Мост ≡

Условие

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

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

Первая строка входного файла содержит целое число m. Следующие m строк содержат по два целых числа — координаты вершин ломаной левого берега: x_1,1, y_1,1, x_1,2, y_1,2, … , x_1,m, y_1,m.

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

Ограничения

2 ≤ m,n ≤ 100

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

4
6 1
3 1
3 0
0 3
3
9 3
2 3
6 5

1.41421356237309505

Задача C. Почти беспрефиксные коды ≡

Условие

В теории кодирования часто используют беспрефиксные коды — наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова "", "a", "ab" и "aba" являются префиксами слова "aba".) другого. Например, набор слов "aba", "aa" и "bac" является беспрефиксным кодом, а набор "abac", "aba", "ba" — нет, поскольку слово "aba" является префиксом слова "abac".

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

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

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ k ≤ 200

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

6 2
aba
bacaba
abacaba
baca
abac
caba

3
aba
bacaba
caba

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

Условие

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

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

Задача E. Драгоценные камни ≡

Условие

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

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

Видов драгоценных камней на Востоке известно не очень много — всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом.

Он заранее определил несколько упорядоченных пар типов камней: (a₁, b₁), (a₂,b₂), \ldots, (a_k,b_k). Эти пары он называет красивыми, их множество мы обозначим как P. Теперь представим ряд камней, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i,j), что 1 ≤ i < j ≤ n, а камни S_i и S_j образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k, что S_i = a_q и S_j = b_q.

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

Напишите программу, которая находит ответ на эту задачу.

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

Первая строка входного файла содержит целые числа n и k — число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую типы камней, которые привезли купцы.

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

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

Ограничения

1 ≤ n ≤ 100000

1 ≤ k ≤ 676

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

7 1
abacaba
aa

6

7 3
abacaba
ab
ac
bb

7

Задача F. Интересные числа ≡

Условие

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересными положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 2₁₀ = 10₂, 24₁₀ = 11000₂.

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

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

Ограничения

1 ≤ n ≤ 10¹⁵

2 ≤ k ≤ 10

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

1 2

2

10 10

110

Задача G. Оптимизация ≡

Условие

В компании "QQQ" работает n человек. Очередной проект компании состоит из m независимых частей. Управляющий компании оценил время, которое требуется для выполнения каждой из частей проекта (предполагается, что это время не зависит от того, кто будет выполнять эту часть). После чего он некоторым образом распределил все m частей между n работниками. В результате оказалось, что некоторым из работников потребуется потратить на выполнение своей работы больше времени, чем другим (поскольку им досталась более объемная работа).

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

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

В выходной файл выведите искомое число оптимизирующих операций.

Во втором примере любая операция является оптимизирующей.

Ограничения

1 ≤ n, m ≤ 10⁵

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

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

2

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

4

Задача H. Шкафы ≡

Условие

Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a₁, a₂, …, a_m, а ящики во втором шкафу — высоту b₁, b₂, …, b_n.

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

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

Ограничения

1 ≤ m, n ≤ 10⁵

Высоты ящиков положительные и не превышают 10⁹.

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

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

3 4
1 2 3
2 3 4 5

Задача I. Архимедова спираль ≡

Условие

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно-исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль — плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ  = OM линейно зависит от угла поворота ϕ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ.

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);
• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);
• начального расстояния R от точки M до начала координат (точки O);
• скорости движения V точки M по лучу OK.

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

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

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

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10^− 5.

Ограничения

1 ≤ ω  ≤ 100

1 ≤ V ≤ 100

0 ≤ R ≤ 100

1 ≤ T ≤ 1000

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

60 10 0 18

-150.302843 -165.275488
180.000000 135.336204

Задача J. Сумма ≡

Условие

Вася любит искать во всем закономерности. В его тетрадке записаны три числа A, B и C, и он хочет установить между ними какую-нибудь простую закономерность. Для начала он хочет узнать, можно ли этим числам приписать в конец несколько нулей так, чтобы сумма первых двух чисел стала равна третьему. Например, если у него записаны числа 9, 34 и 43, то он может не приписывать к ним нулей — сумма 9 и 34 и так равна 43. Если же у него записаны числа 23, 7 и 93, то он может приписать нуль к 7 и получить 70. После чего 23 + 70 = 93.

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

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

Ограничения

Все числа не меньше единицы и не больше 10¹⁰⁰⁰⁰⁰.

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

9
34
43

YES
0 0 0

23
7
93

YES
0 1 0

1
2
4

NO