Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.
В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.
Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».
По заданному набору доминошек определите, сколько пар «дружных доминошек» можно составить из него. Пары, отличающиеся хотя бы одной доминошкой, считаются различными. По-разному составленная пара из одних и тех же доминошек считается один раз.
В первой строке входного файла содержится натуральное число N — количество доминошек (1 ≤ N ≤ 100 000).
В каждой из последующих строк содержится описание доминошки: два целых числа X и Y (0 ≤ X, Y ≤ 6) — количество точек на каждой из половинок доминошки.
Выведите одно число — количество пар «дружных доминошек».
Во втором тесте дружными являются следующие пары:
1-2 2-3, 1-2 3-1, 2-3 3-1, 2-3 4-3, 2-3 4-3, 3-1 4-3, 3-1 4-3, 4-3 4-3
В этой задаче для хранения ответа необходим 64-битный тип данных (int64 на языке Pascal и long long на языках C/C++).
2 1 2 2 1
1
5 1 2 2 3 3 1 4 3 4 3
8
Петя и Вася придумали систему шифровки для обмена записками. Суть ее заключается в следующем. Дана исходная строка S. S' — циклический сдвиг строки влево (первый символ становится последним, а остальные перемещаются на одну позицию влево), S" — циклический сдвиг строки S' и т.д. Петя с Васей выписывают на листок бесконечную последовательность символов SS'S"S"'.... Если им необходимо зашифровать символ C, то они ищут какое-либо вхождение этого символа в выписанную последовательность и записывают его порядковый номер k. Нумерацию символов они ведут с единицы.
Злоумышленник Коля перехватил сообщение и выкрал исходную строку S. Однако он не может определить, какой символ стоит в последовательности SS'S"S"'... на k-ом месте. Помогите злоумышленнику Коле узнать, какой символ соответствует числу k.
Первая строка входного файла содержит строку, состоящую только из строчных латинских букв. Длина строки не превышает 100000 символов. Вторая строка входного файла содержит единственное целое число 1 ≤ k ≤ 2 × 109.
Единственная строка выходного файла должна содержать символ, который окажется на k-ом месте сформированной строки.
abcd 5
b
abcd 17
a
Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.
Алексей Иванович — азартный игрок, однако вместо участия в игре предпочитает делать ставки. Ему удалось узнать, какая строка будет предложена для игры. Алексею Ивановичу предсказать исход игры при оптимальных действиях обоих игроков не под силу. За помощью он обратился к вам.
В первой строке входного файла содержится количество символов в строке.
Во второй строке входного файла содержится строка, предложенная игрокам. Строка состоит из маленьких латинских букв. Длина строки не превышает 50000 символов.
Выведите номер игрока, который победит в игре (число 1 или 2) при оптимальной игре каждого из игроков.
3 uho
1
6 ababab
2
Развитие химической науки привело к тому, что высшие фуллерены (сложные молекулы углерода в виде шарика или продолговатой трубки) стали недорогими в производстве. Благодаря своим уникальным оптическим свойствам они нашли свое место и в ювелирной промышленности. Ювелирный дом «Кёрл, Крото и Смолли» выпустил уникальную коллекцию украшений из фуллеренов. Украшение продается в виде набора трубок-фуллеренов различной длины, из которых можно составить украшение самостоятельно.
Норма Джин очень любит сложные углеродные соединения и купила себе набор фуллеренов для составления украшений. Ее фирменный стиль состоит в том, чтобы носить украшения, составленные ровно из трех трубок фуллерена, причем в результате должен получаться тупоугольный треугольник. Норма Джин — объект постоянной охоты папарацци, поэтому не может позволить себе дважды появиться на людях с одним и тем же украшением.
Помогите Норме Джин узнать, сколько вечеров она сможет посетить с имеющимся у нее набором фуллереновых трубок. Фуллереновые трубки одинаковой длины считаются различными. Треугольники считаются различными, если они отличаются хотя бы одной трубкой. Треугольники, состоящие из одних и тех же трубок, считаются одинаковыми независимо от порядка трубок.
Первая строка входного файла содержит одно число N (1 ≤ N ≤ 5000) — количество фуллереновых трубок в наборе Нормы Джин.
Вторая строка содержит N упорядоченных по возрастанию целых чисел Li (1 ≤ Li ≤ 2 × 109).
Выведите одно целое число — количество вечеров, на которые сможет сходить Норма Джин.
4 2 2 3 4
3
Александр недавно увлекся горным туризмом. Ему уже надоело покорять отдельные горные пики, и он собирается покорить самую настоящую горную цепь!
Напомним, что Александр живет в плоском мире. Горная цепь состоит из отрезков, соединяющих точки на плоскости, каждая из которых находится строго правее предыдущей (x-координата следующей точки больше, чем у предыдущей). Трассой на горной цепи называется её часть между двумя фиксированными точками цепи, которые не обязательно являются концами отрезков.
Участок, на котором при движении по трассе координата y (высота) всегда возрастает, называется подъемом, величиной подъема называется разность высот между начальной и конечной точками участка. Ниже изображена горная цепь из 7 точек, на ней задана трасса, которая состоит из четырех участков (трасса выделена жирным). Если проходить трассу слева направо, то один из участков является подъемом.
Туристическая компания предлагает на выбор несколько трасс на одной горной цепи. Александр из-за финансовых трудностей может выбрать для поездки только одну из этих трасс. Вы решили помочь ему с выбором. Александру важно для каждой трассы определить суммарную высоту подъемов на ней.
В первой строке входного файла содержится единственное число N — количество точек ломаной, задающей горную цепь (1 ≤ N ≤ 100 000). Далее в N строках содержатся описания точек, каждое из которых состоит из двух целых чисел, xi и yi (1 ≤ xi, yi ≤ 109).
В следующей строке находится число M — количество трасс (1 ≤ M ≤ 100 000).
Далее в M строках содержатся описания трасс, каждое описание представляет собой два целых числа, si и fi, они обозначают x-координаты начала и конца трассы, соответственно. Начало и конец трассы могут совпадать.
Гарантируется, что во входном файле задана именно горная цепь, и ни одна из трасс не выходит за ее пределы.
Для каждой трассы выведите одно число — суммарную высоту подъемов на данной трассе. Ваш ответ будет считаться правильным, его его абсолютная или относительная погрешность не будет превышать 10 - 6.
7 2 1 4 5 7 4 8 2 9 6 11 3 15 3 1 5 10
4.0000000000
6 1 1 3 2 5 6 7 2 10 4 11 1 3 9 11 3 10 7 3
0.6666666667 6.0000000000 4.0000000000