Задача B. Последовательность
Условие
Дана последовательность целых чисел a1, a2, ..., an, каждое из которых
по модулю не превосходит 10000. Эта последовательность записана на бумажной ленте, которая свернута в кольцо.
Разрежем эту кольцо в некоторой точке между числами, получим полоску с записанной
на ней последовательностью следующего вида:
aj, aj+1,..., an, a1, a2, ..., aj − 1.
Назовем точку разреза хорошей, если все частичные суммы полученной последовательности строго положительны:
aj > 0,
aj + aj+1 > 0,
....
aj + aj+1 + ... + an > 0,
aj + aj+1 + ... + an + a1 > 0,
...
aj + aj+1 + ... + an + a1 + a2 + ... + aj − 2 > 0,
aj + aj+1 + ... + an + a1 + a2 + ... + aj − 2 + aj − 1 > 0.
Вам требуется вычислить число хороших точек разреза.
Формат входного файла
Первая строка входного файла содержит число n, а во второй строке заданы числа
a1,
a2, ...,
an.
Формат выходного файла
Выведите в выходной файл число искомых хороших точек разреза.
Ограничения
1 ≤
n ≤ 100000
Примеры тестов
| № |
Входной файл (seq.in) |
Выходной файл (seq.out) |
|---|
| 1 |
5
0 1 -2 10 3
|
2
|
Задача E. Поле чудес
Условие
Для игры в "Поле чудес" используется круглый барабан, разделенный на сектора, и стрелка.
В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число.
Однажды ведущий решил изменить правила игры.
Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке,
в котором на них указывала стрелка в процессе вращения барабана.
Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым.
После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане?
Напишите программу, отвечающую на этот вопрос.
Формат входного файла
Во входном файле записано сначала число
N — количество чисел, которое назвал ведущий.
Затем записано
N чисел, на которые указывала стрелка в процессе вращения барабана.
Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале).
Формат выходного файла
Выведите минимальное число секторов, которое может быть на барабане.
Ограничения
2 ≤
N ≤ 30000
Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.
Примеры тестов
| № |
Входной файл (e.in) |
Выходной файл (e.out) |
|---|
| 1 |
13
5 3 1 3 5 2 5 3 1 3 5 2 5
|
6
|
| 2 |
4
1 1 1 1
|
1
|
| 3 |
4
1 2 3 1
|
3
|
Задача F. Юный поджигатель
Условие
На клеточном поле введена система координат так,
что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
- Спички длины 1 выкладывались по сторонам клеток.
- Спички длины sqrt(2) выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке,
имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью).
Спичка может гореть в нескольких местах (например, когда она загорается с двух концов;
или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается
по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Формат входного файла
Во входном файле записано сначала число
N - количество спичек.
Затем идет
N пятерок чисел вида
X1,
Y1,
X2,
Y2,
T, задающих координаты
концов спички и время ее сгорания при условии, что она будет подожжена с одного конца
(гарантируется, что каждая спичка имеет длину 1 или sqrt(2), все спички образуют связную фигуру,
и положение никаких двух спичек не совпадает).
Формат выходного файла
Выведите минимальное время сгорания фигуры.
Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки.
Если решений несколько, выведите любое из них.
Ограничения
1 ≤
N ≤ 40
Все координаты — целые числа, по модулю не превышающие 200,
время сгорания — натуральное число, не превышающее 10
7.
Примеры тестов
| № |
Входной файл (f.in) |
Выходной файл (f.out) |
|---|
| 1 |
1
0 0 1 1 1
|
1.00
|
| 2 |
5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1
|
3.25
|
| 3 |
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
|
35.00
|
| 4 |
16
0 0 0 1 1 -2 -1 -3 -1 1 -2 -1 -1 0 1 -2 -1 -1 -2 1
-1 0 0 0 1 0 3 1 3 1 1 3 2 2 1 2 2 2 1 1
2 1 1 0 1 2 0 1 1 1 2 0 1 0 1 2 1 1 1 1
0 0 1 0 1 0 1 -1 1 1 -1 1 -1 2 1 0 3 -1 2 1
|
4.50
|
