Задача A. Аквалангист

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:128 Мб
Максимальный балл:100  

Условие

Аквалангист Джонс находится в море в координате xj, yj на глубине hj метров. Джонс заметил акулу, которая находится в координате xs, ys на глубине hs метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью vs м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

Формат входных данных

Входные данные содержат в двух строках целые числа xj, yj, hj и xs, ys, hs, vs.

Формат выходных данных

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |xj|, |yj|, hj, |xs|, |ys|, hs ≤ 105

1 ≤ vs ≤ 100

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

Стандартный вход Стандартный выход
1
0 0 1
100 100 100 1
YES
2
0 0 1
0 0 2 2
NO

Задача B. Быки и коровы 2

Автор:Малявин Н.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:128 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

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

Формат входных данных

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

Формат выходных данных

Выходные данные должны содержать два числа l, r — координаты самой левой и самой правой клеток отрезка. Клетки нумеруются с единицы.

Ограничения

1 ≤ N < 105, 1 ≤ h ≤ N

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

Стандартный вход Стандартный выход
1
15 5
XX...XXYYYXX.YY
6 10

Задача C. Жадная последовательность

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

Условие

Дана последовательность из N целых чисел ai. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

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

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

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

Вторая строка входного файла содержит N целых чисел ai — элементы последовательности.

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

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 105

104 ≤ ai ≤ 104

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
nm
1202 ≤ n ≤ 5m < nполная
2202 ≤ n ≤ 1000m < n1полная
3602 ≤ n ≤ 105m < n1,2полная

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

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

Задача D. Сбор справок

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

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

Входной файл содержит числа N и M - количество чиновников и "условий" соответственно. Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.

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

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

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
NM
1 25 1 ≤ N ≤ 100 1 ≤ M ≤ 100
2 15 1 ≤ N ≤ 103 1 ≤ M ≤ 104 1
3 20 1 ≤ N ≤ 104 1 ≤ M ≤ 105 1,2
4 40 1 ≤ N ≤ 105 1 ≤ M ≤ 105 1,2,3

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

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

Problem E. Flasks equalizing

Author:M. Sporyshev, A. Zhikhareva   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  
Maximum points:100  

Statement

In the laboratory there is a weird construction consisting of N equal cylindrical flasks in a row.

Flask number i contains ai milliliters of a liquid.

In a single step, you can pour any amount of liquid from a single flask to one or both its neighbours on the left and on the right in any proportion. The amount of liquid in each flask must remain integer value after each step.

Your program must perform the minimum number of aforementioned steps to make all flasks contain the equal amount of liquid.

Input file format

The first line of the input file contains an integer N.

The second line contains N integers ai. It is guaranteed that the total amount of liquid is divisible by N.

Output file format

The first line of the output file must contain an integer S — the minimum number of steps.

Each of the following S lines contain three integers I, L, R — the index of the flask starting from 1, the amount of liquid to pour into the flask to the left and the amount of liquid to pour into the flask to the right respectively.

If there are several solutions, output any of them.

Constraints

1 ≤ N ≤ 105

0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
7 7 1 5 5
2
2 0 4
1 0 2
2
5
7 6 1 5 6
4
2 0 3
4 1 0
1 0 2
5 1 0

0.158s 0.007s 21