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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:format.in   Ограничение памяти:256 Мб
Выходной файл:format.out  
Максимальный балл:100  

Условие

Многие системы форматирования текста, например 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.

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

Входной файл (format.in) Выходной файл (format.out)
1
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. Космические исследования

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:space.in   Ограничение памяти:256 Мб
Выходной файл:space.out  
Максимальный балл:100  

Условие

Отделу космических исследований поступило задание сфотографировать из космоса 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 строк содержат по два целых числа: Xi и Yi — координаты объектов в заданной области.

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

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

Ограничения

1 ≤ N ≤ 103

1 ≤ K ≤ 5

1 ≤ Xi, Yi ≤ 50

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

Входной файл (space.in) Выходной файл (space.out)
1
4 1
1 1
10 2
1 3
10 4
30
2
4 2
1 1
10 2
1 3
10 4
10
3
1 1
1 1
0
4
3 3
3 3
3 6
6 3
7

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:3 сек
Входной файл:divisors.in   Ограничение памяти:256 Мб
Выходной файл:divisors.out  
Максимальный балл:100  

Условие

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

Будем называть нормальным набор из k чисел (a1, a2, , ak), если выполнены следующие условия:

  1. каждое из чисел ai является делителем числа n;
  2. выполняется неравенство a1 < a2 < … < ak;
  3. числа ai и ai+1 для всех i от 1 до k − 1 являются взаимно простыми;
  4. произведение a1 a2… ak не превышает 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 ≤ 108

2 ≤ k ≤ 10

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

Входной файл (divisors.in) Выходной файл (divisors.out)
1
90 3
16
2
10 2
4

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:house.in   Ограничение памяти:256 Мб
Выходной файл:house.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 104. Координаты заданных точек не превышают по модулю 104. Точки (x1, y1) и (x2, y2) ни для какой прямой не совпадают.

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

Входной файл (house.in) Выходной файл (house.out)
1
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

Author:ACM ICPC NEERC 2010 Jury   Time limit:3 sec
Input file:kgraph.in   Memory limit:256 Mb
Output file:kgraph.out  
Maximum points:100  

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 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 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 ci (1 ≤ ci ≤ 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

No. Input file (kgraph.in) Output file (kgraph.out)
1
3 2
1 3
3 2
3
1
1
2
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

Author:StdAlg (adapted by T. Chistyakov, A. Klenin)   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:1  

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

Input file contains integers N M, then M pairs of integers ai bi describing the edges of the graph.

Output file format

Output BIPARTITE if the graph is bipartite or NO if it is not.

Constraints

1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
1 2  1 3
BIPARTITE
2
4 6
1 2  2 3  3 4  4 1  1 3  2 4
NO

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

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

Условие

Вам необходимо написать программу, которая получает взвешенный ориентированный граф и находит в нем расстояния от вершины S до всех остальных вершин. Расстояние от вершины S до некоторой вершины W — это минимальная длина пути из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.

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

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

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

Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для для них должно быть выведено 1.

Ограничения

1 ≤ N, M ≤ 100000 Все веса меньше или равны 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

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

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

Автор:Жюри ВКОШП-2008   Ограничение времени:2 сек
Входной файл:dfs.in   Ограничение памяти:256 Мб
Выходной файл:dfs.out  
Максимальный балл:100  

Условие

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


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. Помогите ему выяснить это!

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

Первая строка входного файла содержит два целых числа: n и l — количество вершин в графе и количество чисел в выведенной последовательности. Следующие l строк по одному числу — вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

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

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

Ограничения

1 ≤ n ≤ 300

1 ≤ l ≤ 2 n1

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

Входной файл (dfs.in) Выходной файл (dfs.out)
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

Author:T. Chistyakov   Time limit:1 sec
Input file:input.txt   Memory limit:2 Mb
Output file:output.txt  
Maximum points:100  

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

Input file contains integers P N, then N descriptions of the machines. The description of ith machine is represented as by 2 P + 1 integers Qi Si,1 Si,2… Si,P Di,1 Di,2… Di,P, where Qi specifies performance, Si, j — input specification for part j, Di, k — output specification for part k.

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

1 ≤ P ≤ 10, 1 ≤ N ≤ 50, 1 ≤ Qi ≤ 10000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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
2
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
3
2 2
100  0 0  1 0
200  0 1  1 1
0 0

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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H ≤ 1000

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

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

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

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

Условие

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

Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai1 ⋅ Q) mod V.

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

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

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

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

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2311

1 ≤ K ≤ N ≤ 4 ⋅ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
343 32767 3 10 7
16478

Задача M. Knapsack problem

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

Условие

Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей, сумма элементов которой равна w, либо установите, что искомой подпоследовательности не существует.

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

Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.

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

Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите 1.

Ограничения

1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000

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

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

Задача N. LCA

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

Условие

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

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

Первая строка входного файла состоит из единственного числа N. Далее в N1 строке следует описание дерева: пары соединенных вершин. После этого до конца файла записаны пары номеров веришин, для которых следует найти LCA. Количество этих пар не превосходит 10^5.

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

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

Ограничения

1 ≤ N ≤ 105

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

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

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

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

Условие

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

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

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

Во входном файле содержится два числа: номера заданных вершин.

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

В выходном файле должно содержаться единственное число: номер вершины, являющейся LCA двух заданных.

Ограничения

1 ≤ N ≤ 2311

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

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

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

Автор:Кировская командная олимпиада 2001 года   Ограничение времени:5 сек
Входной файл:b.in   Ограничение памяти:200 Мб
Выходной файл:b.out  
Максимальный балл:100  

Условие

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

Папа Карло начинает работу ровно в 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 строк записано описание одной передачи: сначала время ее начала в формате ЧЧ:ММ:СС (ЧЧ — две цифры, задающие часы, ММ — две цифры, задающие минуты начала, СС — две цифры, задающие секунды начала). А затем через один или несколько пробелов число Ti — время в секундах, которое папа Карло будет тратить на забивание одного гвоздика, если он перед этим увидит по телевизору эту передачу.

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

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

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

Ограничения

1 ≤ N ≤ 32400, 1 ≤ Ti ≤ 32400

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

Входной файл (b.in) Выходной файл (b.out)
1
2
09:00:00 3600
14:00:00 3600
8
2
4
09:00:00 1800 
12:59:31 10
13:45:23 1800
15:00:00 3600
14

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

Автор:Кировская командная олимпиада 2001 года   Ограничение времени:5 сек
Входной файл:f.in   Ограничение памяти:64 Мб
Выходной файл:f.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Входной файл (f.in) Выходной файл (f.out)
1
1 1 0 -1 10
-1
2
1 2 4 -2 -20
0
3
1 1 2  3 10
4

Problem R. Triathlon

Author:NEERC 2000-2001   Time limit:4 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

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 Vi, Ui and Wi, 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 ≤ Vi, Ui, Wi ≤ 10000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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. Скобки

Автор:Жюри зимних сборов 2009   Ограничение времени:1 сек
Входной файл:brackets.in   Ограничение памяти:256 Мб
Выходной файл:brackets.out  
Максимальный балл:100  

Условие

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

Так, последовательность ()(()) является правильной скобочной последовательностью, потому что она может, например, встречаться в выражении (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.

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

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

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

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

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

Входной файл (brackets.in) Выходной файл (brackets.out)
1
()
7
2
()()
17
3
(())
21

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

Автор:Жюри ROI-2011   Ограничение времени:2 сек
Входной файл:attract.in   Ограничение памяти:256 Мб
Выходной файл:attract.out  
Максимальный балл:100  

Условие

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

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

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

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

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

В первой строке входного файла содержатся два числа: N и M (1 ≤ M ≤ N ≤ 100). Во второй строке заданы M целых чисел ti (1 ≤ ti ≤ 100), каждое из которых задаёт время игры на i-м автомате (1 ≤ i ≤ M). Числа в строке разделяются одиночными пробелами.

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

В первой строке необходимо вывести одно число — минимально возможное время отправления автобуса из парка аттракционов. Далее необходимо вывести N расписаний игр на автоматах, по одному для каждого из участников. Каждое расписание описывается в (M + 1) строках, первая из которых — пустая, а далее следуют M строк, описывающих автоматы в порядке их посещения этим участником. Посещение автомата описывается двумя целыми числами: номером автомата j (1 ≤ j ≤ M) и временем начала игры участника на этом автомате.

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

Входной файл (attract.in) Выходной файл (attract.out)
1
2 1
2
4

1 0

1 2
2
3 2
2 1
6

1 0
2 2

1 2
2 4

2 0
1 4

0.390s 0.005s 55