Тимофей на клетчатом листочке обвел прямоугольник размером a × b и закрасил его черным и белом цветом шахматной раскраской с клеткой размером n, начиная черной клеткой с левого нижнего угла. Сколько всего единичных клеточек прямоугольника оказалось закрашено черным?
Формат входных данных
Единственная строка входного файла содержит три натуральных числа, записанных через пробел: a, b и n.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу.
Ограничения
1 ≤ a, b, n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Решения, верно работающие при n кратном a и n кратном b, получат не менее 20 баллов.
Решения, верно работающие при n кратном a, получат не менее 40 баллов.
Артём и Женя играют в придуманную ими самими игру "Захват клеток". Евгений ходит первым и ему требуется закрасить n клеток, таким образом, чтобы общее количество клеток, попавших внутрь области закрашенных, было наибольшим (клетки области должны быть окружены полностью — со всех сторон и углов). Вся эта область, включая закрашенные клетки на границе, объявляется захваченной. Помогите Жене определить число клеток, которое он может захватить первым ходом.
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n.
Формат выходных данных
Выведите одно натуральное число — наибольшее число захваченных клеток.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В первом примере больше трех клеток захватить нельзя.
Во втором примере 10 закрашенных клеток можно расположить таким образом, чтобы окружить ещё 2 клетки.
Как-то раз Тимофей сидел на контрольной работе по математике. И свой вариант, и вариант соседки по парте, красавицы Алёны, давно были решены. От скуки Тимофей стал рисовать на клетчатом листочке-черновике.
Сперва он поставил на пересечении линий квадратной сетки две точки — синюю и черную. Потом через каждую точку провел по четыре прямые соответствующих цветов — параллельные линиям сетки и под углом в 45 градусов. В некоторых точках черные и синие прямые пересеклись. Заинтересовавшись, Тимофей выделил их зеленым цветом и некоторое время молчаливо созерцал. Наконец, пробормотал: "Любопытно!" — и соединил некоторые зеленые точки отрезками так, чтобы получился выпуклый многоугольник наибольшей площади.
В настоящее время Тимофей готовит статью для публикации в известном математическом журнале "Выпуклые многоугольники и их применение в народном хозяйстве Дальнего Востока". Основу статьи составляет 2020-страничный вывод формулы площади многоугольника Тимофея — именно так скромно назвал автор своё построение. Мы не просим Вас доказать правильность этой формулы — просто найдите зависимость между положением двух исходных точек и площадью получившейся фигуры.
Формат входных данных
Единственная строка входного файла содержит два неотрицательных целых числа, записанных через пробел: x и y — расстояния между проекциями двух исходных точек на оси координат.
Формат выходных данных
Выведите одно натуральное число — площадь многоугольника Тимофея, построенного на основе данных точек.
Ограничения
0 ≤ x, y ≤ 108
0 < x + y
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при x = 0, получат не менее 20 баллов.
Решения, верно работающие при x = y, получат не менее 20 баллов.
Перед Тимофеем стоит серьёзная математическая задача — определить количество различных квадратов в прямоугольном ступенчатом "треугольнике" с катетом n.
Формат входных данных
В единственной строке записано одно натуральное число n.
Формат выходных данных
Выведете одно натуральное число — ответ на задачу. Гарантируется, что он не превысит 1018.
Ограничения
1 ≤ n ≤ 106
Система оценки и описание подзадач
Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 1: 1 ≤ n ≤ 1000, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Пояснения к примерам
Комментарий к первому примеру:
"Треугольник" с катетом пять вмещает 15 квадратов со стороной один, 6 квадратов со стороной два и 1 квадрат со стороной три. Всего 22 различных квадрата.
Комментарий ко второму примеру:
"Треугольник" с катетом восемь вмещает 36 квадратов со стороной один, 21 квадрат со стороной два, 10 квадратов со стороной три и 3 квадрата со стороной четыре. Всего 70 различных квадратов.
— А как я узнаю связного? — поинтересовался агент 007.
— Вот по этой купюре, — мягко улыбнулся Q, — я её разрежу замысловатым образом, одну часть отдам Вам прямо сейчас, а вторую Вам покажет наш связной при встрече. Если разрез совпадёт, можете не сомневаться — перед Вами наш разведчик.
Слышен звук разрезаемой бумаги.
— Постойте, Q! Я хочу добавить дополнительную проверку. Пусть обе части купюры имеют одинаковую площадь.
— Но я уже почти закончил! Даже не знаю, удастся ли мне сделать последний разрез, чтобы удовлетворить Ваше требование!
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: h и w — размер банкноты. Во второй строке через пробел расположены h − 1 натуральных чисел xi — координаты вертикальных разрезов купюры по линиям квадратной сетки сверху вниз.
Формат выходных данных
Выведите одно натуральное число — место последнего разреза, после которого купюра распадется на две равные по площади и по высоте части. Если такой разрез сделать невозможно, выведите число -1.
Ограничения
2 ≤ h ≤ 105
2 ≤ w ≤ 109
1 ≤ xi ≤ w − 1
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при h = 2, получат не менее 10 баллов.
Решения, верно работающие при w = 2, получат не менее 10 баллов.
Пояснение к примерам
В первом примере дана купюра размером 6 × 12, её площадь равна 72. Разрезы сделаны по красной линии. После последнего разреза (по зеленой линии) купюра распадется на две равные по площади части (по 36).
Во втором примере площадь купюры выражается нечетным числом единичных квадратов, разрезать её на две равные по площади части, делая разрезы по линиям квадратной сетки, невозможно.
Тимофей очень любит участвовать в разнообразных игровых конкурсах для школьников. "Китайская панда — иероглифы для всех", "Кентавр", "Французский пудель", "Золотой урон", "Сумчатое — аборигенам" — он не пропускает ни одного. Но особенно Тимофею нравится конкурс по технологии информационной коммуникации (ТИК).
Участникам конкурса ТИК предлагается ответить на n вопросов. На каждый вопрос предлагается четыре варианта ответа, обозначенных буквами a, b, c и d. Участник выбирает один из вариантов и отмечает его крестиком в поле для ответа. Правильный ответ на вопрос приносит конкурсанту один балл, неправильный — ноль баллов. Всего в конкурсе можно набрать от 0 до n баллов.
Вот и настал день проведения долгожданного конкурса. Одна беда — именно сейчас Тимофею нужно срочно убегать по очень важным делам. Поэтому он заполнил клеточки крестиками, совершенно не вчитываясь в задания. Делал он это в соответствии с собственной Стратегией: поставил случайным образом крестик в поле для ответа на первый вопрос, а каждый следующий крестик ставил на одну позицию выше или ниже предыдущего. Ниже приведен пример заполнения поля для ответов в соответствии со Стратегией.
Сегодня, наконец, опубликовали ответы на задания конкурса. Тимофей совершенно не помнит расстановку своих крестиков, но хочет узнать максимально возможное количество баллов, которое он теоретически может получить.
Формат входных данных
В первой строке входного файла записано одно натуральное число n — количество вопросов.
Во второй строке записаны верные ответы на вопросы конкурса — строка из n символов. На каждой позиции в строке стоит одна из четырех букв: a, b, c или d.
Формат выходных данных
В единственной строке выходного файла запишите одно натуральное число — максимальное количество баллов, которое может набрать Тимофей в соответствии со Стратегией.
Ограничения
1 ≤ n ≤ 105
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: n = 2, баллы: 15.
Подзадача 2: n ≤ 8, баллы: 30.
Подзадача 3: нет дополнительных ограничений, баллы: 55.
Пояснения к примерам
Комментарий к первому примеру:
Единственный вариант заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 4: baba.
Комментарий ко второму примеру:
Один из вариантов заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 8: abcbabcb. Больше 3 баллов набрать невозможно.
В городе, где живут два закадычных друга Андрей и Борис, введена прямоугольная декартова система координат. И так вышло, что дом Андрея расположен в точке с координатами (a, 0), а дом Бориса — в точке с координатами (0, b). Обычно друзья встречались в точке (0, 0) и шли гулять, но сегодня они решили встретиться в какой-нибудь другой точке. При этом Андрей по-прежнему хочет пройти до места встречи расстояние a, а Борис — расстояние b. Помогите друзьям встретиться!
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b.
Формат выходных данных
Выведите два натуральных числа x и y — координаты новой точки встречи. Гарантируется, что входные данные таковы, что x и y окажутся натуральными.
В городе, где живут два закадычных друга Андрей и Борис, введена прямоугольная декартова система координат. И так вышло, что дом Андрея расположен в точке с координатами (a, 0), а дом Бориса — в точке с координатами (0, b). Обычно друзья встречались в точке (0, 0) и шли гулять, но сегодня они решили встретиться в какой-нибудь другой точке. При этом Андрей по-прежнему хочет пройти до места встречи расстояние a, а Борис — расстояние b. Помогите друзьям встретиться!
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b.
Формат выходных данных
Выведите два натуральных числа x и y — координаты новой точки встречи. Гарантируется, что входные данные таковы, что x и y окажутся натуральными.
Тимофей — страстный футбольный болельщик. Он внимательно следит за ходом основных турниров, коллекционирует автографы известных футболистов и играет в компьютерную игру "FIFA 2020".
Сегодня Тимофей решил создать свой клуб, чтобы сразиться в виртуальных поединках со своими друзьями. Как истинный патриот своего края, название для своей команды он выбрал не раздумывая — "Вулкан". Осталось нарисовать эмблему, загрузить её на сайт игры, и можно будет начинать участие в дружеском чемпионате.
Наступило время урока математики. Тимофей задумчиво рисует на клетчатом листочке силуэты огнедышащих гор, пытаясь найти наиболее красивое их расположение. Правила, наложенные Тимофеем на эмблему такие:
1) Рисунок должен помещаться в прямоугольник высотой n клеток и шириной 2 × n.
2) Эмблема состоит из единственной непрерывной ломаной линии, начинающейся в левом нижнем и заканчивающейся в правом нижнем углу прямоугольника.
3) Ломаная проходит исключительно по диагоналям клеток. Изменение направления возможно только в узле клетчатой решетки.
Каждый элемент ломаной, состоящий из двух отрезков, первый из которых расположен на "северо-восточной", а второй — на "юго-восточной" диагонали, называется вулканом. Помогите Тимофею определить количество различных эмблем для заданных размеров изображения и количества вулканов.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — высота эмблемы и v — количество вулканов.
Формат выходных данных
Выведите одно натуральное число — количество различных эмблем. Гарантируется, что это число не превзойдет 109
Ограничения
1 ≤ v < n ≤ 16
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере нужно найти количество различных эмблем размером 4 × 8, на которой изображено ровно два вулкана.
На рисунке изображены все возможные случаи v для n = 4. Видно, что для v = 2 число различных эмблем равно 6.
