Информатика

Даша имеет n ювелирных украшений. Каждое украшение имеет стоимость wi и значимость для Даши vi. В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только k из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:
\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)

Даша решает сохранить такие k украшений, для которых параметр важности будет максимально возможным. Помогите ей правильно выбрать украшения.

Входные данные
Первая строка ввода содержит числа n – количество ювелирных изделий у Даши и k – количество ювелирных изделий, которые планируется оставить (1 ≤ k ≤ n ≤ 100000).

В следующих n строках содержатся по два числа – v_i и w_i (0 ≤ v_i ≤ 10⁶,1≤w_i≤10⁶, обе суммы всех значений vi и wi не превосходят 10⁷ каждая).

Выходные данные
Выведите k чисел – номера ювелирных украшений, которые следует оставить. Если существует несколько решений, то выведите любое из них.

Введем следующие операции надо прямоугольной таблицей символов. Пусть нам дана матрица А, состоящая из m строк (первый индекс) и n столбцов (второй индекс). Определим результирующую матрицу В для каждой из операций следующим образом:

• Транспозиция относительно главной диагонали (код операции '1'): B_j,i=A_i,j
• Транспозиция относительно другой диагонали (код операции '2'): B_n-j+1,m-i+1=A_i,j
• Горизонтальное отражение (код операции 'H'): B_m-i+1,_j=A_i,j
• Горизонтальное отражение (код операции 'V'): B_i,n-j+1=A_i,j
• Поворот на 90 ('A'), 180 ('B'), или 270 ('C') градусов по часовой стрелке: B_j,m-i+1=A_i,j (для 90º)
• Поворот на 90 ('X'), 180 ('Y'), или 270 ('Z') градусов против часовой стрелки: B_n-j+1,i=A_i,j (для 90º)

Вам дана последовательность не более 100000 операций над исходной матрицей. Выведите полученную в результате этих операций матрицу.
Входные данные
В первой строке входных данных находятся значения m и n (0<m,n≤300). В каждой из следующих m строк находятся по n печатных символов (т.е. не используются символы с кодами от 33 до 126).

Последняя строка содержит описание операций, которые были выполнены над этой матрицей, путем записи без пробелов из кодов. Операции выполняются по порядку слева направо.

Выходные данные
Выведите сначала два целых числа − число строк и столбцов в результирующей матрице. Затем выведите саму матрицу в том же формате, что и во входных данных.

Напишите программу, моделирующую работу детерминированного конечного автомата (ДКА). Описание автомата и входная строка вводятся на стандартном потоке ввода. Результат работы автомата над данной строкой выводится на стандартный поток вывода.

Входные данные
Описание автомата задаётся в следующей форме. Сначала задаётся функция перехода автомата. Функция перехода задаётся в виде троек CUR CHAR NEW, где CUR — идентификатор исходного состояния — произвольная символьная строка, не содержащая пробельные символы. CHAR — символьная строка длиной ровно 1 символ. NEW — идентификатор целевого состояния — произвольная символьная строка, не содержащая пробельные символы. Элементы описания перехода могут отделятся друг от друга произвольным количеством пробельных символов. Описание функции перехода завершается строкой "END" в качестве идентификатора исходного состояния. Элементы CHAR и NEW отсутсвуют.

Далее перечисляются заключительные состояния автомата. Каждое состояние — это символьная строка. Список состояний завершается символьной строкой "END". Далее задаётся начальное состояние автомата — символьная строка. Затем задаётся проверяемое слово — символьная строка. Все элементы входного файла могут отделяться друг от друга произвольным количеством пробельных символов. Можете предполагать, что входные данные корректны, то есть удовлетворяют спецификации и действительно задают детерминированный конечный автомат.

Выходные данные
Результат работы автомата должен быть напечатан в следующем виде. Сначала напечатайте число 1, если данный автомат допускает данную цепочку, и 0 в противном случае. Затем напечатайте количество символов, прочитанных во входной цепочке к моменту принятия автоматом решения. Наконец, напечатайте идентификатор состояния, в котором в данный момент находился автомат.

Ценные бумаги на фондовом рынке характеризуются множеством параметров. У них есть цена и ликвидность, также оценивать динамичность изменения цены, среднюю прибыльность, потенциал роста прибыльности и др. показатели. Аналитики трейдовой компании "WebMarket" ввели специальный показатель надежности ценной бумаги и научились эффективно его оценивать. Большое значение этого показателя соответствует малому риску покупки ценной бумаги. Но с ростом надежности обычно падает среднее оцениваемое значение прибыльности.

Для своих клиентов, играющих на рынке ценных бумаг, компания "WebMarket" решила открыть значения этого показателя и более того, автоматизировать покупку ценных бумаг с заданным порядковым номером по значению надежности. Аналитики проанализировали идею, и решили, что наличие такого функционала будет способствовать привлечению новых клиентов на рынок "WebMarket", повышению объемов сделок, а значит, и повышению прибылей "WebMarket". Важно также отметить, что торговля на базе этого показателя может позитивно сказаться на российском фондовом рынке и cделать его более здоровым. Алгоритмы оценки надежности уже написаны, средства выделены, необходимая реклама проведена. Осталось только написать сам код.

Ценные бумаги в базе данных имеют три атрибута:

• code — непустая строка латинских символов и цифр длины 30 или меньше
• id — целочисленный идентификатор (начиная с 0)
• reliability — целое число из диапазона [−2³¹,2³¹)

.
Каждой новой ЦБ выдается следующий по порядку id и значение её надёжности устанавливается в 0. Если ценная бумага отзывается с рынка, ее id для новых бумаг не используется.

База данных получает запросы, которые позволяют вводить новые ЦБ на рынок, получать текущую информацию о ЦБ, отзывать ЦБ с рынка, менять значение надежности у ЦБ и находить ЦБ, которая стоит на n-м месте, если упорядочить ЦБ по убыванию надежности, а при одинаковых значениях по возрастанию идентификатора.

При добавлении ЦБ с кодом, который раньше встречался, но соответствующая ЦБ была отозвана с рынка, ей назначается новый идентификатор.

Входные данные
Первая строка входа содержит число запросов N. (1≤N≤100000). Затем идут N  строк, каждая из которых содержит один запрос. Запросы бывают 4 типов:

• ISSUE code: добавить новую ЦБ code в базу данных, или вывести информацию о ЦБ, если она уже есть в базе
  • если ЦБ code существует, то вывести EXISTS id reliability
  • если ЦБ code не существует, то вывести CREATED id 0
• DELETE code: удалить ЦБ code из базы
  • если ЦБ code существует, то вывести OK id reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• RELIABILITY code reliability: увеличить количество очков ЦБ, гарантируется, что значение останется в диапазоне [−2³¹,2³¹)
  • если ЦБ code существует, то вывести OK id new_reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• FIND n: найти n-ю ЦБ (начиная с 0)
  • если база не пуста, найти ЦБ, которая имела бы порядковый номер n (нумерация начинается с 0), если все ЦБ упорядочить сначала по убыванию баллов, а группы ЦБ с одинаковыми баллами упорядочить по времени их добавления (то есть по возрастанию id); а если n больше, чем количество ЦБ в базе, то найти последнюю ЦБ в этом порядке; для обоих случаев вывести OK code id reliability
• если база пуста, то вывести EMPTY

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

На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные
Вводятся два числа от 1 до 8: номер столбца (считая слева) и номер строки (считая снизу), где изначально стоит шашка.

Выходные данные
Вывести одно число - количество путей в дамки.

В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

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

Входные данные
Вводятся два числа N и M — размеры таблицы (1≤N≤20, 1≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

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

Входные данные
Вводится одно число N (0<=N<=30).

Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).

Организаторы TВ-Шоу “Ключ к успеху” подготовили ряд призов для победителей. Если победитель набрал X очков, он должен выбрать призов в точности на X у.е. От предыдущих шоу у организаторов остались N призов стоимостью a₁,a₂,... ,a_n< у.е. соответственно. К сожалению, не известно, сколько именно очков наберет победитель очередной игры. Организаторы решили купить еще M призов, чтобы максимизировать минимальную сумму очков, которую уже нельзя будет набрать имеющимися призами.

Например, если уже имеются призы в 2, 3 и 9 у.е., а покупается 2 приза, то купить надо призы стоимостью 1 и 7 долларов. Тогда победитель сможет набрать себе призы при любом счете от 1 до 22 очков.

Входные данные
В первой строке входных данных находятся два целых числа N и М — число призов у организаторов и число призов, которое они собираются докупить (0 ≤ N ≤ 30, 1 ≤ M ≤ 30). Вторая строка содержит N целых числе в диапазоне от 1 до 10⁹ — стоимости имеющихся призов

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

Люди, покупающие какие-либо билеты, часто пытаются понять, на сколько счастливый билет им попался. При этом определения счастья бывают различные. В общественном транспорте Кирова для нумерации билетов используются числа от 1 до n. Витя считает билет счастливым, если его номер делится на сумму его цифр. Помогите Вите определить количество счастливых билетов.

Входные данные
На вход подается число n (1 ≤ n ≤ 10¹²).

Выходные данные
Выведите количество счастливых билетов в диапазоне от 1 до n.

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

К несчастью, переключатели не являются доступными. Но Коля нашел сокет, каждый пин которого соединен с одним из переключателей через некоторую схему. Коля нашел эту схему в Интернете. Он обозначил переключатели маленькими латинскими буквами, а пины сокета — большими буквами. После этого он выписал логическую формулу для каждого пина. Согласно этой формуле включенный переключатель представляется значением true, а выключенный —false.

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

• Обозначение пина — буква от ‘A’ до ‘K’ ;
• Скобки обозначают, что если E >— это формула, то (E) — тоже формула;
• Отрицание — ~E— это формула для любой формулы E;
• Конъюнкция — E₁ & E₂ &…&E_n;
• Дизъюнкция — E₁| E₂| … | E_n;
• Импликация Е₁ => E₂ =>… => E_n. Импликации выполняются справа налево: Е₁ => E₂ => E₃ означат Е₁ => (E₂ => E₃);
• Эквивалентность — Е₁ <=> E₂ <=> … <=> E_n. Такое выражение вычисляется так: (Е₁ <=> E₂) &(Е₂<=> E₃) & … &(E_n-1 <=> E_n)..

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

Входные данные
Первая строка входных данных содержит единственное целое число n — количество пинов у сокета (1 < n < 10). Следующие n строк содержат описания каждого пина. Одно описание состоит из обозначения пина и соответствующей формулы, отделенной от обозначения символами ‘:=’. Пин обозначен заглавной латинской буквой. Его формула расположена в одной строке и состоит из элементов ‘a’..‘k’, ‘(’, ‘)’, ‘~’, ‘&’, ‘ |’, ‘=>’ и ‘<=>’. Элементы формулы могут быть отделены друг от друга произвольным числом пробелов. Описание каждого пина содержит не более 1000 символов.

Выходные данные
Если требуемая схема существует, то выведите в первой строке Yes и No в противном случае.

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

Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа t обозначим h(t) максимальное значение k, такое что t делится на 2k. Например, h(24)=3, h(5)=0. Обозначим l(t)=2h(t), например, l(24)=8, l(5)=1.

Рассмотрим массив a[1], a[2], … , a[n] целых чисел. Дерево Фенвика для этого массива — это массив b[1], b[2], …, b[n], такой что  \( \sum\limits_{j=i-l(i)+1}^{i}a[j] \) Таким образом: b[1]=a[l], b[2]=a[l]+a[2], b[3]=a[3], b[4]=a[l]+a[2]+a[3]+a[4], b[5]=a[5], b[6]=a[5]+a[6], Например, дерево Фенвика для массива a=(3,−1,4,1,−5,9) есть массив b=(3,2,4,7,−5,4).

Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив a=(0,−1,1,1,0,9) таковым является.

Вам дан массив а. Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.

Входные данные
В первой строке входных данных содержится количество чисел в массиве n (1 ≤ n ≤ 100000). Во второй строке находятся сами n целых чисел. Все числа по модулю не превосходят 10⁹.

Выходные данные
Выведите n чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.

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

Входные данные
Когда Алиса учила алфавит, она заметила, что с ее зеркалом что-то не так! Кубик в зеркале мог показывать не ту букву, что изображена на нем, но всегда одну и ту же. Алиса придумала новую игру, пытаясь составить смешные слова из реальных кубиков и из кубиков в зеркале одновременно.

Игра имела следующие правила. Алиса выкладывала из кубиков слово S₁. Эти же буквы в зеркале показывали слово S₂, которое могло отличаться от отражения S₁, так как зеркало было заколдованным. Но длина каждого слова равнялась N.

Затем Алиса проделывала следующие шаги. Она выбирала два кубика i и j и меняла их местами. В зеркале при этом менялись изображения кубиков N – i + 1 и N – j + 1 соответственно.

Цель игры — получить из слова S₁ слово T₁, которое будет выглядеть в зеркале как слово T₂. Алиса не знает, когда это возможно, а когда нет. Помогите ей ответить на этот вопрос.

Входные данные
Во входном файле находятся 4 слова S₁, S₂, T₁ и T₂, каждое в отдельной строке. Все слова имеют одну и ту же длину N (1 ≤ N≤ 100) и состоят только из заглавных латинских букв.

Выходные данные
Выведите Yes или No в зависимости от ответа на вопрос задачи.

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

Центробанк Флатландии планирует выделить N пакетов помощи. Каждый пакет характеризуется его суммой A_i.

Банки предоставили запросы на помощь. На данный момент поступило M запросов. Каждый запрос характеризуется его продолжительностью B_i дней.

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

По известной информации о пакетах помощи и запросах подсчитайте количество возможных пар пакет-запрос.

Входные данные
Первая строка содержит целое число N – количество пакетов помощи (1 ≤ N ≤ 100 000). Вторая строка содержит N целых чисел: a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁶).

Вторая строка содержит целое число N – количество запросов (1 ≤ M ≤ 100 000). Вторая строка содержит N целых чисел: b₁, b₂, . . . , b_n (1 ≤ b_i ≤ 10⁶).

Выходные данные
Выведите количество возможных пар.

Комментарий к примеру

Пары могут быть следующие: (3, 1) дважды как (a₁, b₁) и (a₁, b₂), (3, 3), (4, 1) дважды, (4, 2), (5, 1) дважды, (6, 1) дважды, (6, 2) и (6, 3).

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

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

Помогите почтальону составить такой маршрут.

Входные данные
Сначала записано число N — количество площадей в городе (2≤N≤1000). Далее следуют N строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют mi
 пар натуральных чисел: в j-ой паре первое число — номер площади, в которую идет j-ая улица с i
-ой площади, а второе число — длина этой улицы.

Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.

Все числа во входном файле не превосходят 100000

Выходные данные
Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте, а во вторую — номера площадей в порядке их посещения.

Если решения нет, выведите в выходной файл одно число –1.

Если решений несколько, выведите любое.

Карту местности условно разбили на квадраты, и посчитали среднюю высоту над уровнем моря для каждого квадрата.

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

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

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

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

Входные данные
В первой строке записаны числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).

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

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

• определяет, является ли заданный граф четно-нечетным;
• в случае отрицательного ответа на пункт 1 находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X выполняется следующее условие: все пути между i и j состоят из четного числа ребер.

Входные данные
Первая строка входного файла содержит число вершин графа N (1≤N≤100) и число ребер M (1≤M≤1000), а каждая последующая — пару чисел (i,j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j.

Выходные данные
Первая строка выходного файла должна содержать ответ на пункт 1 в форме «YES/NO». В случае отрицательного ответа на пункт 1 вторая строка должна содержать количество вершин в множестве X, а третья — номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.

По дороге в школу Петя любит забегать в киоск и покупать себе мороженое. Однако при этом он часто опаздывает в школу. Неожиданно Петя понял - он просто ходит не по кратчайшему пути!

Помогите Пете победить опоздания. Город можно представить как N перекрестков, соединенных M улицами, про каждую улицу известна ее длина. Дом Пети находится на перекрестке A, школа - на перекрестке B, а киоск с мороженым - на перекрестке C. По пути в школу Петя никогда не проходит через один перекресток дважды.

Входные данные

Первая строка содержит числа N и M (3 ≤ N ≤ 30 000, 0 ≤ M ≤ 50 000). Вторая строка содержит три различных числа - A, B и C. Следующие M строк содержат по три целых числа X_i, Y_i и L_i - номера перекрестков, соединенных улицей и ее длину (длина - целое положительное число, которое не превышает 10⁴).

Выходные данные

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

В противном случае выведите -1 на первой строке.

Дано N точек на плоскости, их надо покрасить в черный и белый цвета.

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

Требуется посчитать количество раскрасок, удовлетворяющих этим условиям.

Входные данные
В первой строке задано число 2≤N≤300. В следующих N строках заданы координаты точек.

Выходные данные
Выведите единственное число - количество различных раскрасок.

Есть замок — точка (0,0). Замок окружен несколькими непересекающимися заборами, каждый представляет из себя выпуклый многоугольник.

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

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

Входные данные
8 первой строке задано число N (1≤N≤100000). Далее следуют описания N заборов. Каждое описание начинается с числа K, далее следуют К строк, содержащих по два числа X и Y — координаты вершин (0≤X,Y≤2⋅10⁶). Вершины каждого многоугольника перечисляются в порядке обхода против часовой стрелки. Гарантируется, что точка (0,0) лежит внутри каждого забора.

Далее следует число M (0≤M≤100000) — количество захватчиков. В следующих М строках заданы координаты захватчиков.

Суммарное число вершин во всех многоугольниках не превосходит 100000.

Все вводимые числа являются целыми.

Выходные данные
Выведите единственное число — общую захваченную площадь с шестью знаками после десятичной точки.