Для ускорения прохождения «коротких» заданий на ЭВМ выбран пакетный режим работы с квантованием времени процессора. Это значит, что всем заданиям пакета по очереди представляется процессор на одинаковое время 10 с (круговой циклический алгоритм разделения времени). Если в течение этого времени заканчивается выполнение задания, оно покидает систему и освобождает процессор. Если же очередного кванта времени не хватает для завершения задания, оно помещается в конец очереди — пакета. Последнее задание пакета выполняется без прерываний. Пакет считается готовым к вводу в ЭВМ, если в нем содержится K заданий. Новый пакет вводится в ЭВМ после окончания обработки предыдущего. Задания поступают в систему с интервалом времени 60 ± 30 с и характеризуются временем работы процессора 50 ± 45 с.
Требуется смоделировать процесс обработки N заданий и определить время начала и окончания каждого процесса.
Входные данные
На первой строке входного файла INPUT.TXT находятся числа N и K - число процессов и количество процессов в пакете (1 ≤ N ≤ 1000, 1 ≤ K ≤ 100). Гарантируется, что N делится на K. Далее следуют N строк с информацией о времени формирования и необходимое время на выполнение для каждого процесса. Все процессы стартуют в один день и следуют в порядке возрастания времени ввода их в систему.
Выходные данные
Выведите в выходной файл OUTPUT.TXT для каждого процесса в отдельной строке время его старта и время окончания через пробел в формате ЧЧ:ММ:СС.
Требуется вывести квадрат, состоящий из N×N клеток, заполненных числами от 1 до N2 по спирали (см. примеры).
Входные данные
Во входном файле INPUT.TXT задано целое число N – размер квадратной матрицы (2 ≤ N ≤ 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, заполненную числами от 1 до N2 по спирали, при этом между числами может быть любое количество пробелов. Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.
В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
Входные данные
Во входном файле INPUT.TXT записано сначала число N - количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.
Выходные данные
В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
Неспокойно сейчас на стапелях шестого дока межгалактического порта планеты Торна. Всего через месяц закончится реконструкция малого броненесущего корвета “Эния”. И снова этому боевому кораблю и его доблестной команде предстоят тяжелые бои за контроль над плутониевыми рудниками Сибелиуса. Работа не прекращается ни на секунду, лазерные сварочные аппараты работают круглые сутки. От непрерывной работы плавятся шарниры роботов-ремонтников. Но задержаться нельзя ни на секунду.
И вот в этой суматохе обнаруживается, что термозащитные панели корвета вновь требуют срочной обработки сульфидом тория. Известно, что на обработку одного квадратного метра панели требуется 1 нанограмм сульфида. Всего необходимо обработать N прямоугольных панелей размером A на B метров. Вам необходимо как можно скорее подсчитать, сколько всего сульфида необходимо на обработку всех панелей “Энии”. И не забудьте, что панели требуют обработки с обеих сторон.
Входные данные
Первая строка входного файла INPUT.TXT содержит 3 целых положительных числа через пробел: N (N ≤ 100), A (A ≤ 100), B (B ≤ 100)
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести единственное число – вес необходимого для обработки сульфида тория в нанограммах.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 2 3
60
2
14 23 5
3220
Задача E. Фермер - 2
(Время: 1 сек. Память: 64 Мб)
После решения задачи с пашней земли, фермер хочет построить на этой земле как можно больший по площади сарай прямоугольной формы. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму прямоугольной сеткой размера M×N. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Сарай должен быть построен на свободных узлах сетки.
Помогите фермеру определить максимально возможную площадь сарая.
Входные данные
В первой строке входного файла INPUT.TXT записаны два натуральных числа N и M (1 ≤ N,M ≤ 1000) – размеры фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) из M нулей и единиц, описывающих ферму. Единицы соответствуют свободным для постройки участкам.
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь сарая, который может построить фермер на своем участке.
Недавно Билл устроился на работу полицейским. Теперь ему предстоит каждый вечер обходить свой участок, который представляет собой прямоугольник, состоящий из N×M кварталов. Каждый квартал имеет вид квадрата размером 100 х 100 метров, кварталы отделены друг от друга прямыми улицами.
Таким образом, через участок Билла проходит N+1 улица, идущая с запада на восток, и M+1 улица, идущая с севера на юг. Перекрестки разбивают улицы на (N+1)*M + (M+1)*N отрезков, каждый из которых имеет длину 100 метров.
Совершая обход, Билл выходит из полицейского управления, расположенного около юго-западного угла его участка, обходит свой участок и возвращается в управление. Во время обхода Билл должен пройти по каждому отрезку улицы на территории своего участка как минимум один раз. Известно, что во время обхода Билл проходит отрезок длиной 100 метров за одну минуту. Выясните, какое минимальное число минут потребуется Биллу, чтобы совершить обход.
Входные данные
Входной файл INPUT.TXT содержит натуральные числа N и M, не превышающие 10 000.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное время, за которое Билл может совершить обход.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 1
4
2
2 2
16
3
4 3
38
Пояснение
Один из возможных оптимальных путей для Билла во втором примере показан на рисунке:
