Темы
Информатика(2656 задач)
--->
228 задач
<---
Александр недавно увлекся горным туризмом. Ему уже надоело покорять отдельные горные пики, и он собирается покорить самую настоящую горную цепь!
Напомним, что Александр живет в плоском мире. Горная цепь состоит из отрезков, соединяющих точки на плоскости, каждая из которых находится строго правее предыдущей (x-координата следующей точки больше, чем у предыдущей). Трассой на горной цепи называется её часть между двумя фиксированными концами отрезков.
Участок, на котором при движении по трассе координата y (высота) всегда возрастает, называется подъемом, величиной подъема называется разность высот между начальной и конечной точками участка. Ниже изображена горная цепь из 7 точек, на ней задана трасса, которая состоит из четырех участков (трасса выделена жирным). Если проходить трассу слева направо, то один из участков является подъемом.
Туристическая компания предлагает на выбор несколько трасс на одной горной цепи. Александр из-за финансовых трудностей может выбрать для поездки только одну из этих трасс. Вы решили помочь ему с выбором. Александру важно для каждой трассы определить суммарную высоту подъемов на ней.
В первой строке входного файла содержится единственное число N — количество точек ломаной, задающей горную цепь (1 ≤ N ≤ 30 000). Далее в N строках содержатся описания точек, каждое из которых состоит из двух целых чисел, xi и yi (1 ≤ xi, yi ≤ 30 000).
В следующей строке находится число M — количество трасс (1 ≤ M ≤ 30 000).
Далее в M строках содержатся описания трасс. Каждое описание представляет собой два целых числа, si и fi, они обозначают номера вершин начала и конца трассы, соответственно (1 ≤ si ≤ N, 1 ≤ fi ≤ N). Начало и конец трассы могут совпадать.
Гарантируется, что во входном файле задана именно горная цепь.
Для каждой трассы выведите одно число — суммарную высоту подъемов на данной трассе.
7 2 1 4 5 7 4 8 2 9 6 11 3 15 3 1 2 6
4
6 1 1 3 2 5 6 7 2 10 4 11 1 3 5 6 1 4 4 2
0 5 4
Развитие химической науки привело к тому, что высшие фуллерены (сложные молекулы углерода в виде шарика или продолговатой трубки) стали недорогими в производстве. Благодаря своим уникальным оптическим свойствам они нашли свое место и в ювелирной промышленности. Ювелирный дом «Кёрл, Крото и Смолли» выпустил уникальную коллекцию украшений из фуллеренов. Украшение продается в виде набора трубок-фуллеренов различной длины, из которых можно составить украшение самостоятельно.
Норма Джин очень любит сложные углеродные соединения и купила себе набор фуллеренов для составления украшений. Ее фирменный стиль состоит в том, чтобы носить украшения, составленные ровно из трех трубок фуллерена, причем в результате должен получаться тупоугольный треугольник. Норма Джин — объект постоянной охоты папарацци, поэтому не может позволить себе дважды появиться на людях с одним и тем же украшением.
Помогите Норме Джин узнать, сколько вечеров она сможет посетить с имеющимся у нее набором фуллереновых трубок. Фуллереновые трубки одинаковой длины считаются различными. Треугольники считаются различными, если они отличаются хотя бы одной трубкой. Треугольники, состоящие из одних и тех же трубок, считаются одинаковыми независимо от порядка трубок.
Первая строка входного файла содержит одно число N (1 ≤ N ≤ 100) — количество фуллереновых трубок в наборе Нормы Джин.
Вторая строка содержит N упорядоченных по возрастанию целых чисел Li (1 ≤ Li ≤ 20 000) — длины трубок.
Выведите одно целое число — количество вечеров, на которые сможет сходить Норма Джин.
4 2 2 3 4
3
Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.
В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.
Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».
По заданному набору доминошек определите, сколько пар «дружных доминошек» можно составить из него. Пары, отличающиеся хотя бы одной доминошкой, считаются различными. По-разному составленная пара из одних и тех же доминошек считается один раз.
В первой строке входного файла содержится натуральное число N — количество доминошек (1 ≤ N ≤ 40 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
2 1 2 2 1
1
5 1 2 2 3 3 1 4 3 4 3
8
Вы никогда не задумывались, почему в Angry Birds у птиц нет крыльев? Тем же вопросом задались разработчики новой игры. В их версии смысл игры прямо противоположен Angry Birds: зеленая свинка стреляет по злым птицам из лазерного ружья (завязка явно не хуже исходной игры).
Птицы в игре представляются точками на плоскости. Выстрел сбивает только ближайшую птицу находящуюся на линии огня. При этом сбитая птица падая сбивает всех птиц, находящихся ровно под ней. Две птицы не могут находиться в одной точке. По заданному расположению птиц необходимо определить, какое минимальное количество выстрелов необходимо, чтобы все птицы были сбиты.
Первая строка входного файла содержит единственное целое число N 1 ≤ N ≤ 1000 — количество птиц.
Следующие N строк содержат по два натуральных числа каждая xi, yi — координаты i-ой птицы (0 < x, y ≤ 109). Свинка находится в точке с координатами (0, 0).
Единственная строка выходного файла должна содержать одно целое число — минимальное количество выстрелов, необходимое для того, чтобы сбить всех птиц.
6 1 1 2 2 3 3 2 1 3 2 3 1
3
6 1 1 2 2 3 3 2 1 3 2 3 4
3
У одного из меломанов, участвующих в подготовке этой олимпиады, любимой группой так и остаётся ABBA (да простят его некоторые участники, предпочитающие что-нибудь «потяжелее»). Соответственно, когда речь заходит о примерах различных алгоритмов на строках, он в первую очередь составляет строки из двух букв a и b.
Собственно из анализа таких примеров и родилась следующая задача. Пусть мы хотим прочитать в строке буквосочетание ab. При этом a и b не обязательно должны стоять подряд, достаточно, чтобы a встречалось в строке раньше, чем b. Как составить строку минимально возможной длины, чтобы это буквосочетание можно было прочитать ровно K способами? Например, в строке abba это буквосочетание можно прочитать дважды, но эта строка не будет самой короткой для K = 2, а в строке abab его можно прочитать три раза, и более короткую строку для K = 3 составить нельзя.
Напишите программу, которая и будет составлять подобную строку минимальной длины для заданного натурального K или будет определять, что сделать это невозможно.
Входные данные содержат только одно натуральное число K (1 ≤ K ≤ 109).
Выведите строку, удовлетворяющую условию задачи, или слово «Impossible», если искомую строку составить невозможно. Если искомых строк минимальной длины несколько, то выведите любую из них.
1
ab
3
abab