Петя склеил из \(N^3\) единичных кубиков большой куб размером \(N\) × \(N\) × \(N\). Устав от этой сложной работы, он отправился спать, а утром, проснувшись, с ужасом обнаружил, что его младший брат Ваня \(K\) раз проткнул куб спицей.
При этом Ваня действовал очень аккуратно, каждый раз установив конец спицы точно в центр грани какого-нибудь граничного единичного кубика, он протыкал куб параллельно соответствующей оси координат, при этом целый ряд из \(N\) кубиков оказывался испорчен.
Немного успокоившись после этого тяжелого потрясения, Петя заинтересовался, сколько кубиков в его творении осталось неповрежденными. Помогите ему ответить на этот сложный вопрос.
В первой строке вводятся числа \(N\) и \(K\) (1 <= \(N\) <= 1000, 0 <= \(K\) <= 150). Следующие K строк описывают Ванины преступные действия. Каждая строка содержит три числа - два из них представляют собой соответствующие координаты всех кубиков, проткнутых спицей, а третье, соответствующее координате, в направлении которой был проткнут куб, равно 0. Например, если \(N\) = 3, тройка (1, 0, 3) означает, что спицей были проткнуты кубики (1, 1, 3), (1, 2, 3) и (1, 3, 3). Все координаты лежат в пределах от 1 до \(N\). Известно, что Ваня никакое действие не выполнял два раза (т.е. никакая тройка не встретится во входных данных дважды).
Выведите единственное число - количество неповрежденных кубиков.
5 3 1 2 0 2 3 0 3 3 0
110
Те, кто часто путешествуют самолетами, любят просить место у прохода. Ведь если сидеть у прохода, можно встать и прогуляться, не тревожа своих соседей.
Компания «Аэротрам» готовит к производству новый самолет «T-239-n». Перед инженерами встала задача спланировать организацию салона, чтобы как можно больше мест было у прохода. Будем использовать следующую упрощенную математическую модель салона самолета. В горизонтальном сечении салон представляет собой прямоугольник длиной l и шириной w сантиметров. Кресло представляет собой прямоугольник размером x на y сантиметров и должно быть расположено в салоне так, чтобы его сторона длиной x была параллельна стороне салона длиной l. Проход представляет собой полосу шириной a, параллельную стороне салона длиной l. Проход идет вдоль всего салона.
В салоне требуется разместить n кресел. Помогите инженерам компании выяснить, как организовать салон, чтобы максимальное количество кресел было расположено у прохода. В салоне необходимо сделать хотя бы один проход. Кресло считается расположенным у прохода, если оно имеет хотя бы одну общую сторону с проходом.
Входной файл содержит шесть целых чисел: n, l, w, x, y и a (1 ≤ n ≤ 10000, 1 ≤ l,w,x,y,a ≤ 104).
Если разместить n кресел в салоне так, чтобы был хотя бы один проход, невозможно, выведите в выходной файл единственное число −1 . Иначе выведите максимальное количество кресел, которое можно разместить у прохода.
Комментарий к примерам тестов.
В первом примере оптимально расположить кресла, например, следующим образом:
400 3250 750 80 60 70
160
450 3250 750 80 60 70
-1
На днях Алиса делала уборку в своей комнате и нашла дневник, который вела в начальной школе. Там она с удивлением обнаружила запись о том насколько ее поразило то, что \(2 + 2 = 2 \cdot 2\). Невероятно, умножение и сложение дают один и тот же результат!
Эта запись натолкнула Алису на следующую задачу: пусть целые заданы числа \(a\) и \(b\). Сколько различных значений в наборе чисел
| \(a + b\), | \(\;a - b\), | \(\;a \cdot b\), | \(\;a / b\), | \(\;a^b\), |
| \(b + a\), | \(\;b - a\), | \(\;b \cdot a\), | \(\;b / a\), | \(\;b^a\). |
Деление происходит без округления, результат деления может не быть целым числом. Если какое-либо выражение из этого набора некорректно, то Алиса его не рассматривает. Некорректными считаются деление на ноль и возведение нуля в неположительную степень.
Первая строка входного файла содержит целые числа \(a\) и \(b\), разделенные пробелом (\(|a|, |b| \le 10^9\)).
Выведите в выходной файл количество различных чисел в приведенном наборе.
Погостив пару недель у Темного Властелина и прослушав истории о всех его похождениях за последние годы, сэр Петрейн понял, что он уже давно не совершал никаких подвигов. Посидев за чашкой чая и тщательно обсудив будущий подвиг, они решили, что Петрейну нужно победить ужасного дракона, который уже давно терроризирует западные окраины Личного королевства. И вот он отправился готовиться к великому походу.
Но какой рыцарь идет на дракона без рыцарского обмундирования? Поэтому Петрейну нужны доспехи, щит и меч. Всем известно, что чем щит больше, тем эффективней будет он в бою. Сейчас у Петрейна есть два треугольных щита, но он считает их недостаточно надежными и хочет сделать из них один.
Королевский оружейник, взявшийся за изготовление щита, предложил следующий способ: два имеющихся щита кладутся рядом так, чтобы они соприкасались сторонами и фиксируются в таком положении. Сэр Петрейн заметил, что как бы оружейник не старался, у полученного в результате щита всегда будет одинаковая площадь, а значит его эффективность в бою с драконом будет зависеть только от того, какие щиты дал Петрейн оружейнику, но не от того, как они скреплены.
Но ему нужен не просто кусок металла, а щит с символикой его рода: золотым обрамлением по периметру. Однако золото сейчас дорого, поэтому Петрейну хочется, чтобы периметр полученного щита был как можно меньше. Помогите ему выяснить, какой минимальный периметр может иметь щит.
В первой строке заданы три числа \(a_1\), \(b_1\) и \(c_1\) — длины сторон первого щита. Во второй строке заданы три числа \(a_2\), \(b_2\) и \(c_2\) — длины сторон второго щита. Обе строки задают корректные невырожденные треугольники. Все числа во входном файле не превосходят \(100{\,}000\).
Выведите единственное число — минимальный периметр щита, который можно изготовить из них указанным способом.