Развитие химической науки привело к тому, что высшие фуллерены (сложные молекулы углерода в виде шарика или продолговатой трубки) стали недорогими в производстве. Благодаря своим уникальным оптическим свойствам они нашли свое место и в ювелирной промышленности. Ювелирный дом «Кёрл, Крото и Смолли» выпустил уникальную коллекцию украшений из фуллеренов. Украшение продается в виде набора трубок-фуллеренов различной длины, из которых можно составить украшение самостоятельно.
Норма Джин очень любит сложные углеродные соединения и купила себе набор фуллеренов для составления украшений. Ее фирменный стиль состоит в том, чтобы носить украшения, составленные ровно из трех трубок фуллерена, причем в результате должен получаться тупоугольный треугольник. Норма Джин — объект постоянной охоты папарацци, поэтому не может позволить себе дважды появиться на людях с одним и тем же украшением.
Помогите Норме Джин узнать, сколько вечеров она сможет посетить с имеющимся у нее набором фуллереновых трубок. Фуллереновые трубки одинаковой длины считаются различными. Треугольники считаются различными, если они отличаются хотя бы одной трубкой. Треугольники, состоящие из одних и тех же трубок, считаются одинаковыми независимо от порядка трубок.
Первая строка входного файла содержит одно число N (1 ≤ N ≤ 100) — количество фуллереновых трубок в наборе Нормы Джин.
Вторая строка содержит N упорядоченных по возрастанию целых чисел Li (1 ≤ Li ≤ 20 000) — длины трубок.
Выведите одно целое число — количество вечеров, на которые сможет сходить Норма Джин.
4 2 2 3 4
3
Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.
XML-строка состоит из открывающих и закрывающих тегов.
Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>.
Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.
XML-строка называется корректной, если она может быть получена по следующим правилам:
Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.
Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.
Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).
Строка во входном файле заканчивается переводом строки.
Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.
Примеры входных и выходных файлов
|
input |
output |
|
<a></b> |
<a></a> |
|
<a><aa> |
<a></a> |
|
<a><>a> |
<a></a> |
|
<a/</a> |
<a></a> |
Пусть нам дано натуральное число \(N\). Рассмотрим множество различных целых чисел \(\{a_1, a_2, \dots, a_k\}\), где каждое число лежит в интервале от \(0\) до \(N-1\) включительно. Назовём такое множество свободным от сумм, если в этом множестве не найдётся таких трёх чисел, что сумма двух из них сравнима с третьим по модулю \(N\). Строго говоря, назовём множество свободным от сумм, если для каждой тройки (не обязательно различных) индексов \(x\), \(y\) и \(z\) (\(1\leq x,y,z\leq k\)) выполняется неравенство: \(\)(a_x+a_y) \bmod N \neq a_z\(\)
где \(p \bmod q\) — остаток от деления \(p\) на \(q\).
Например, при \(N=6\) множествами, свободными от сумм, не являются, например, \(\{0\}\) (т.к. \((0+0)\bmod 6=0\)), \(\{1,2\}\) (т.к. \((1+1) \bmod 6=2\)), \(\{3,4,5\}\) (т.к. \((4+5)\bmod 6=3\)), но множество \(\{1,3,5\}\) является свободным от сумм.
По заданному \(N\) определите, сколько существует множеств, свободных от сумм.
Во входном файле находится одно целое число \(N\). Гарантируется, что \(1\leq N\leq 35\).
В выходной файл выведите одно число — ответ на задачу.
Все множества, свободные от сумм, для \(N=6\) — это следующие: \(\{5\}\), \(\{4\}\), \(\{3\}\), \(\{3,5\}\), \(\{3,4\}\), \(\{2\}\), \(\{2,5\}\), \(\{2,3\}\), \(\{1\}\), \(\{1,5\}\), \(\{1,4\}\), \(\{1,3\}\), \(\{1,3,5\}\), \(\{\}\) (последнее множество — пустое, т.е. не содержащее ни одного элемента, с \(k=0\) — тоже считается свободным от сумм).
2
2
6
14
Магическим квадратом будем называть квадрат с одинаковой суммой чисел по всем вертикалям и горизонталям; никаких требований на суммы по диагоналям накладывать не будем. Составьте такой квадрат из заданного набора чисел.
Во входном файле записаны 16 различных целых чисел в интервале от 0 до 32 768.
В выходной файл необходимо вывести искомое расположение чисел, составляющее магический квадрат \(4\times 4\) (каждое число должно встречаться ровно один раз), в четырех строках по четыре числа, или строку «NO SOLUTION», если квадрат составить нельзя.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 6 13 14
2 11 12 9
15 7 4 8
16 10 5 3