Задача A. Шестиугольник

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

Условие

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

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

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

textbfОбратитевнимание, что при заданных ограничениях для хранения значений переменных необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint64 в textbfFree textbfPascal, textbflong в textbfJava.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ ai ≤ 108

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие в случае, когда все стороны шестиугольника равны, получат не менее 20 баллов.

Пояснение к примеру

Смотри рисунок.

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

Стандартный вход Стандартный выход
1
4
1
3
3
2
2
35

Задача B. Длинная улица

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

Условие

В городе, где живет Тимофей, все дома расположены вдоль одной стороны единственной улицы. Нумерация домов начинается с 0, в котором как раз и проживает наш герой. Сегодня он с кратким рабочим визитом намеревается посетить своего друга Арсения, который проживает в доме номер a.

Тимофей может идти пешком, при этом перемещение от дома номер d до дома d + 1 (или наоборот) занимает у него ровно одну минуту.

Также Тимофей может поехать на автобусе, первая остановка которого расположена как раз напротив его дома, а все последующие — напротив домов, номера которых оканчиваются на 0 (то есть 10, 20, и так далее). При этом перемещение от одной остановки до следующей занимает у автобуса ровно одну минуту.

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

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

Единственная строка входного файла содержит натуральное число a — номер дома Арсения.

textbfОбратитевнимание, что при заданных ограничениях для хранения значений переменных необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint64 в textbfFree textbfPascal, textbflong в textbfJava.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ a ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a ≤ 105, получат не менее 60 баллов.

Пояснение к примеру

В примере дано a = 17. Тимофей сядет на автобус, проедет 2 остановки и через две минуты выйдет напротив дома 20. Путь пешком до дома Арсения займет еще три минуты. Итого пять минут.

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

Стандартный вход Стандартный выход
1
17
5

Задача C. Робот гардеробщик

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

Условие

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

Реализовано это было следующим образом: прямоугольный гардероб имеет размеры a на b. По периметру трёх сторон через единичные расстояния расположены крючки для одежды. Точно по центру четвертой стороны (она равна b и имеет четную длину) находится робот-гардеробщик, принимающий одежду и номерки. Получив очередное задание, робот доезжает до одного из крючков, меняет местами номерок и одежду и возвращается к зрителю. Перемещаться робот может только по линиям квадратной сетки, поэтому для определения длины перемещения нового гардеробщика используется манхэттенское расстояние.

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

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

Две строки входного файла содержат два натуральных числа: a и b. Гарантируется четность b.

textbfОбратитевнимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint64 в textbfFree textbfPascal, textbflong в textbfJava.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ a, b ≤ 108

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = 1, получат не менее 20 баллов.

Решения, верно работающие при a, b ≤ 105, получат не менее 60 баллов.

Пояснение к первому примеру

В первом примере приведён самый маленький из возможных гардеробов: a = 1 и b = 2. Его план изображен на рисунке. Робот обозначен красной точкой, крючки — синими. Отмечены пути от стартового положения робота до каждого из крючков. Каждый путь гардеробщик преодолеет дважды — он принимает от человека верхнюю одежду, добирается до крючка, возвращается на своё стартовое место и передаёт зрителю его номерок. Всего ему придется преодолеть 2 × (1 + 2 + 1 + 2 + 1) = 14 единиц.

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

Стандартный вход Стандартный выход
1
1
2
14
2
5
4
142

Задача D. Новогодняя гирлянда

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

Условие

В гирлянде из n лампочек некоторые горят, а остальные — перегорели. Какое наименьшее число неисправных лампочек нужно заменить, чтобы среди любых x подряд идущих лампочек хотя бы y горели?

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

Первая строка входного файла содержит натуральное число n — количество лампочек в гирлянде. Вторая строка содержит n цифр 0 и 1 — состояние лампочки: 0 — перегорела, 1 — нет. Третья строка содержит два натуральных числа x и y, записанных через пробел.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ y ≤ x ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при y = x, получат не менее 25 баллов.

Пояснение к примеру

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

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

Стандартный вход Стандартный выход
1
10
0110001000
4 2
2

Задача E. Тимофей вычёркивает числа

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

Условие

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

На какой по счёту операции было удалено число n?

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

Две строки входного файла содержат натуральные числа n и k.

textbfОбратитевнимание, что при заданных ограничениях для хранения значений переменных необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint64 в textbfFree textbfPascal, textbflong в textbfJava.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ k ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 105, получат не менее 20 баллов.

Пояснение к примеру

В примере дано n = 20 и k = 3. Из натурального ряда за одну операцию будут вычеркнуты все числа, позиции которых делятся на 3. Определим, на какой операции будет вычеркнуто число 20. Смотри рисунок.

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

Стандартный вход Стандартный выход
1
20
3
7

0.305s 0.013s 27