Задача  1.              Конвейер

Имя входного файла:

pipe.in

Имя выходного файла:

pipe.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

4 мегабайта

Максимальная оценка за задачу:

80 баллов

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

Рассмотрим следующую простую модель конвейера, состоящего из p ступеней. Ступень i конвейера получает операнд от i-1 ступени, производит над ним некоторую операцию, полученный результат является операндом для ступени i+1. На проведение операции ступенью i над операндом требуется время ti. Ступень конвейера готова для приема и обработки следующего операнда, после того как завершит свою операцию и передаст результат следующей ступени. Если ступень i завершила свою операцию, но не передала результат следующей ступени (т.к. ступень i+1 не готова), то она не может принять операнд (ступень i не готова = не находится в состоянии готовности). Последняя ступень конвейера p выдает результат на выход конвейера сразу по завершению своей операции. На вход конвейера операнды поступают бесперебойно: как только первая ступень оказывается в состоянии готовности, она немедленно получает очередной операнд для обработки.

Рассмотрим, для примера, работу двухступенчатого конвейера, время операции первой ступени которого 1 секунда, второй – 2 секунды. В момент запуска конвейера на вход первой ступени поступает первый операнд. Через одну секунду, первая ступень обработает первый операнд и передаст его второй ступени, в этот же момент в конвейер (в первую ступень) поступит второй операнд. Через две секунды после начала работы конвейера первая ступень завершит обработку второго операнда, однако вторая ступень будет занята обработкой первого операнда и первая ступень не сможет в этот момент передать ей второй операнд. Через три секунды вторая ступень закончит обработку первого операнда и передаст результат на выход конвейера (таким образом первый операнд будет полностью обработан), первая ступень передаст второй операнд в освободившуюся вторую ступень и получит со входа конвейера третий операнд для обработки. Через 5 секунд после начала работы конвейер выдаст полностью обработанный второй операнд. К этому времени третий операнд только поступит во вторую ступень. Таким образом, за 5 секунд конвейер успеет полностью обработать только 2 операнда.

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

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

В первой строке входного файла дано время работы конвейера – вещественное число с точностью три знака после запятой T (0 < T <= 109).

Во второй строке входного файла находится количество ступеней конвейера – целое число p (1<=p <=106).

В следующих p строках дано время операции каждой ступени – вещественное число с точностью три знака после запятой ti  (0<ti <=109).

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

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

Примеры

pipe.in

pipe.out

6.000

2

1.000

2.000

2

5.000

2

1.001

2.000

1

 

Задача  2.              Метель

Имя входного файла:

blizzard.in

Имя выходного файла:

blizzard.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

16 мегабайт

Максимальная оценка за задачу:

100 баллов

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

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

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

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

Во входном файле записано сначала число N — количество городов в области (1<=N<=106).  Во второй строке дано M — число проезжих дорог в списке дорожной службы (1<=M<=106).  Далее следует описание дорог, по одной дороге в строке. Дорога обозначается номерами городов, которые она непосредственно соединяет, разделенными пробелом.

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

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

Примеры

blizzard.in

blizzard.out

6

5

1 2

3 1

2 3

4 5

6 5

1

3 4

 

 

Задача  3.              В далёком космосе

Имя входного файла:

space.in

Имя выходного файла:

space.out

Максимальное время работы на одном тесте:

5 секунд

Максимальный объем используемой памяти:

4 мегабайта

Максимальная оценка за задачу:

120 баллов

 

 

Где-то далеко в Космосе находится загадочная планета Захадум – родина древнейшей расы Теней. На родной мир Теней очень часто нападала другая древняя раса. Чтобы обезопасить себя, Тени решили построить систему предупреждения, заранее обнаруживающую приближение вероломного врага. Зона космоса, которую нужно контролировать, представляет собой куб, разбитый на N3 одинаковых секторов в форме куба. Таким образом, куб разделили на N слоев по N2 секторов в каждом. Каждый слой занумеровали от 1 до N по порядку. Положение сектора в одном слое определяется аналогично элементу в двумерном массиве (первое число – номер строки, второе – номер столбца) и показано на рис. 1

 

В каждом секторе можно построить следящую станцию. Станция может следить за секторами, которые пересекаются прямыми, проходящими через центр сектора станции и параллельными сторонам зоны космоса (кубу) – см. рис 2.

       (рисунок 1)

 

 

Галактическая война истощила ресурсы Теней, поэтому Древнейший повелел строить минимально возможное количество станций.

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

 

 

 

     (рисунок 2)

 

 

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

Входной файл содержит целое число N (N<=1000) .

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

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

В следующих K строках выводятся три числа, задающие сектор космоса, в котором нужно строить следящую станцию. Первое число – номер слоя, следующие два числа определяют сектор в этом слое (см. рис).

Примеры

space.in

Space.out

1

1

1 1 1

2

2

1 1 1

2 2 2

4

8

1 1 1

1 2 2

2 3 4

2 4 3

3 1 2

3 2 1

4 3 3

4 4 4

 

Задача  4.              Властелин колец

Имя входного файла:

chain.in

Имя выходного файла:

chain.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

4 мегабайта

Максимальная оценка за задачу:

90 баллов

У кузнеца имеется N цепей, каждая цепь состоит из колец. В одной цепи может быть от 1 до 32000 колец.

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

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

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

В первой строке входного файла находится количество цепочек – целое число N (1≤N ≤32000).

В следующих N строках дано количество колец в каждой цепочке – по одному числу в строке.

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

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

.

Пример

chain.in

chain.out

3

2

3

2

2

 

 

Задача  5.              Яблоневый сад

Имя входного файла:

orchard.in

Имя выходного файла:

orchard.out

Максимальное время работы на одном тесте:

4 секунды

Максимальный объем используемой памяти:

12 мегабайт

Максимальная оценка за задачу:

120 баллов

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

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

Поэтому советник сначала решил перенумеровать ряды яблонь.  Отсчет он начал с места, где была посажена самая древняя яблоня. Направление  на север и восток он решил считать положительным, а направление на запад и юг отрицательным. Таким образом, ряды, расположенные севернее и  восточнее самой древней яблони нумеруются положительными числами (1, 2, … ), а ряды, расположенные южнее и западнее самой древней яблони нумеруются отрицательными числами (-1, -2, …). Положение самой древней яблони  - (0,0).  

 

(рисунок 1)

Яблони обозначены серыми кружками, самая древняя яблоня – черным.

 

Разобравшись с нумерацией, советник приступил непосредственно к измерениям. Выбрав две какие-либо яблони, он соединял их веревочкой. Соединение получалось удачным, если при прохождении веревочки через точки пересечения перпендикулярных рядов во всех них оказывалось по яблоне. Удачное соединение он считал «правильным яблоневым отрезком». Отрезок, начало и конец которого совпадают, советник также считал «правильным яблоневым отрезком». Такой отрезок содержал в себе одну яблоню.

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

Но возникла новая проблема, о которой советник не подумал вначале. Действительно, некоторые яблони могли быть посчитаны несколько раз: «правильные яблоневые отрезки» могли пересекаться, перекрываться и даже быть вложенными друг в друга. Поэтому не так то просто получить общее количество яблонь по списку советника.

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

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

В первой строке входного файла дано количество записей советника K (0 <= K <= 103).

Далее идут K строк с описаниями правильных яблоневых отрезков по одному описанию в строке.

Каждое описание состоит из четырех целых чисел (по модулю не превышающих 2*109) – координат начала и конца «правильного яблоневого отрезка», разделенных пробелом. Координаты – это номер ряда, идущего с юга на север, и номер ряда, идущего с запада на восток (в соответствии с нумерацией советника), на пересечении которых находится яблоня (см. рисунок 1).

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

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

Примеры

(последний пример соответствует рисунку 1)

orchard.in

orchard.out

3

1 1 1000 1

1 2 1000 2

1 3 1000 3

3000

 

2

-1 0 1 0

0 -1 0 1

5

 

3

-2 -2 2 2

1 1 3 3

-2 1 2 -1

8

 

 

Задача  6.              Известная геометрическая задача

Имя входного файла:

geometr.in

Имя выходного файла:

geometr.out

Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка за задачу:

90 баллов

В геометрии при изучении теоремы Пифагора часто встречается следующая задача.

Получить отрезок, длина которого точно равна , где N – целое число. Разрешается пользоваться бесконечной линейкой с нанесенными на нее делениями (цена деления равна 1) и угольником для получения прямых углов.

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

Например, для получения отрезка длины достаточно построить два отрезка по 1 (2 построения),

а для получения отрезка, равного , можно построить отрезок, равный 2, и отрезок, равный 1, (2 построения) или получить отрезок, равный (2 построения), и отрезок, равный 1 (всего 3 построения).

           

 

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

 

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

Входной файл содержит единственное целое число N (N≤231) – квадрат длины отрезка, который надо получить.

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

Первая строка должна содержать число K – количество построений,  вторая строка  должна содержать K чисел, разделенных пробелами, – длин отрезков, которые необходимо построить для получения отрезка заданной длины. Если какие либо отрезки используются в построении несколько раз – они указываются столько же раз.

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

Примеры

geometr.in

geometr.out

4

1

2

2

2

1 1

6

3

2 1 1