Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

В биатлоне спортсмен бежит несколько одинаковых основных кругов, между которыми расположены огневые рубежи (то есть основных кругов всегда на 1 больше, чем огневых рубежей). За каждый промах при стрельбе он должен пробежать штрафной круг фиксированной длины p. Известно количество огневых рубежей r, количество промахов k и общая длина дистанции s (сумма всех основных кругов и всех штрафных кругов) для одного из спортсменов.
Найдите длину основного круга.

Формат входных данных
Четыре строки входных данных содержат четыре целых числа: r (1 ≤ r ≤ 10³), k (0 ≤ k ≤ 10⁵), p (1 ≤ p ≤ 10⁵) и s (1 ≤ s ≤ 10⁹). Гарантируется, что длина основного круга при указанных параметрах — натуральное число.

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

Система оценки
Решения, верно работающие при s ≤ 10⁵, получат не менее 30 баллов.
Решения, верно работающие при k = 0, получат не менее 30 баллов.

Замечание
В примере дано:
На дистанции единственный огневой рубеж…
… на котором биатлонист совершил два промаха …
… и поэтому пробежал дополнительно дважды по 150 метров, …
… в результате чего общая протяжённость его пути составила 1100 метров.
Перебирая всевозможные длины основных кругов начиная с 1, дойдём до 400, сумма длин всех кругов окажется равна 1100.

Ввод
1
2
150
1100
Вывод
400

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Камчатка входит в топ лучших мест мира для наблюдения за китами.
Капитан прогулочного катера «Камчатка» отлично знает, что горбатого кита лучше всего искать в прямоугольнике с координатами противоположных углов (x1, y1)–(x2, y2). Однако киты не всегда желают показываться на поверхности, потому он на всякий случай ещё знает, что можно попробовать полюбоваться косатками в прямоугольнике с координатами противоположных углов (x3, y3)–(x4, y4) (оба прямоугольника имеют стороны, параллельные координатным осям).
Очевидно, что капитану лучше всего курсировать в пересечении этих двух прямоугольников для того, чтобы клиенты с наибольшей вероятностью увидели какое-то из морских существ. Требуется найти площадь этого пересечения.

Формат входных данных
На вход подаются восемь чисел — координаты углов двух прямоугольников. В первых двух строках задаются числа x1 и y1, в следующих двух строках задаются числа x2 и y2, далее в двух следующих строках идут x3 и y3, и в последних двух строках — x4 и y4. Эти числа задают координаты противоположных углов двух прямоугольников со сторонами, параллельными координатным осям. Первые четыре числа задают две противоположные по диагонали вершины первого прямоугольника, следующие четыре числа — две противоположные по диагонали вершины второго прямоугольника.
x1 ≠ x2, y1 ≠ y2, x3 ≠ x4, y3 ≠ y4.
Все числа целые и принимают значения в пределах от 0 до 100.

Формат выходных данных
Выведите одно целое число — площадь пересечения двух прямоугольников.

Система оценки
Решения, выдающие правильный ответ для случаев, когда один из углов первого прямоугольника находится внутри второго прямоугольника и один из углов второго прямоугольника находится внутри первого прямоугольника, получат не менее 10 баллов.
Решения, выдающие правильный ответ для случаев, когда x1 < x2, y1 < y2, x3 < x4, y3 < y4, получат не менее 50 баллов. Замечание
На рисунке изображена ситуация для первого примера из условия.

Ввод
1
1
9
6
5
2
14
8
Вывод
16

Ввод
1
4
4
1
2
0
3
3
Вывод
2

Ввод
1
1
3
3
3
5
6
0
Вывод
0

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Маркетологи знают, что в супермаркетах покупатель сначала ведёт себя рационально, а в конце срывается на спонтанную покупку у кассы.
Вы анализируете чек из трёх разных товаров, купленных ровно в том порядке, в котором они написаны в чеке. Всего в магазине n товаров, каждый i-й товар имеет цену ki рублей.
Покупатель выбирает товар по цепочке:

1. Первый товар — любой;
2. Второй товар стоит примерно столько же, сколько первый; разница их цен не превышает t;
3. Третий товар резко отличается по цене от первого; разница их цен строго больше t.

Сколько существует способов собрать такой чек из товаров, имеющихся в магазине?

Формат входных данных
В первой строке вводится натуральное число n — количество товаров. Во второй строке вводится натуральное число t — разность цен (3 ≤ n ≤ 10⁵, 0 ≤ t ≤ 10⁹).
В следующих строках вводятся натуральные числа ki, i-е по счёту число равно стоимости i-го товара (1 ≤ ki ≤ 10⁹).
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных
Выведите ответ на задачу.

Система оценки
Решения, правильно работающие при n ≤ 100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n ≤ 1000, будут оцениваться в 30 баллов.

Замечание
В тестовом примере для сборки чека, который подходит маркетологам, можно использовать следующие товары:
• второй, первый и третий товары;
• второй, первый и четвёртый товары;
• третий, четвёртый и второй товары;
• третий, первый и второй товары;
• четвёртый, третий и второй товары;
• четвёртый, первый и второй товары.

Ввод
4
2
4
5
2
2
Вывод
6

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Антон помогает бабушке поливать огород, который представляет собой прямоугольник из n строк, пронумерованных сверху вниз, и m столбцов, пронумерованных слева направо.
Антон q раз поливает некоторые клетки данного огорода следующим образом: он выбирает ячейку с координатами (x, y) (то есть строку номер x и столбец номер y), а затем поливает все клетки ниже и/или правее. Более формально, он поливает все ячейки с координатами (i, j), где i ≥ x и j ≥ y.
Сколько после всех таких операций окажется клеток, которые не были политы ни разу?

Формат входных данных
В первых трёх строках записаны целые числа n, m и q (1 ≤ n, m ≤ 10⁶, 1 ≤ q ≤ 10⁵) — размеры огорода и количество описанных операций.
Следующие 2q строк содержат целые числа xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) — координаты ячейки, которую выбирает Антон в очередной операции.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных
Выведите одно целое число — количество неполитых клеток огорода.

Система оценки
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Решения, верно работающие при n ≤ 2, получат не менее 20 баллов.
Решения, верно работающие при n, m ≤ 1000, получат не менее 50 баллов.

Замечание
На картинке изображён ход действий Антона в примере из условия.

Операции полива:

1. (2, 3) — полить все клетки с i ≥ 2 и j ≥ 3
2. (3, 2) — полить все клетки с i ≥ 3 и j ≥ 2

Ввод
3
4
2
2
3
3
2
Вывод
7

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Внешний долг Марса достиг небывалых размеров, и для его отображения используется n-значное электронное табло. Используются всегда все n знаков, которые при необходимости могут являться ведущими нулями. Таким образом, это табло может отображать любое целое число от 0 до 10ⁿ – 1 включительно.
Каждый из данных n знаков отображается с помощью семисегментных индикаторов. Каждая цифра (от 0 до 9) представляется набором из семи светящихся сегментов, пронумерованных от 1 до 7, как показано на рисунке.
Некоторые сегменты перегорели и никогда не загораются. Для скольких чисел возможно однозначно определить, какое значение на самом деле показывает табло?
Работоспособность каждого разряда представлена битовой строкой из семи цифр. Каждое число 0 или 1 соответствует статусу соответствующего блока: перегорел или работает. Так, строка 0110111 означает, что перегорели блоки с номерами 1 и 4.

Формат входных данных
Первая строка содержит целое число n (1 ≤ n ≤ 18) — количество разрядов.
Следующие n строк содержат последовательности из семи цифр — по одной в строке.
Строка номер i описывает работоспособность i-го разряда табло.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных
Одно целое число — количество различных чисел, для которых можно однозначно установить, что табло показывает именно их.

Система оценки
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 20 баллов.
Решения, верно работающие при n ≤ 6, получат не менее 40 баллов.

Замечание
Пояснение к первому примеру: не работают верхний и средний горизонтальный сегменты. Тогда на табло неотличимы как пара цифр 0 и 8, так и пара цифр 1 и 7. Все остальные цифры отображаются уникальным образом, и поэтому можно однозначно восстановить, что именно показывает табло.

Ввод
1
0110111
Вывод
6

Ввод
2
1111111
1100011
Вывод
50