Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение \(A\), составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение \(B\).
Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.
Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении \(A\), совпадает с набором спичек, используемым в изображении \(B\). Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).
Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений \(A\) и \(B\) и должна найти минимальное количество спичек, которые надо переложить в изображении \(A\), чтобы полученная картинка получалась из \(B\) параллельным переносом.
В первой строке входного файла содержится целое число \(n\) – количество спичек в каждом из изображений (1 ≤ \(n\) ≤ 1000).
В следующих n строках записаны координаты концов спичек на изображении \(A\). Спичка номер \(i\) описывается целыми числами \(x_{1i}\), \(y_{1i}\), \(x_{2i}\), \(y_{2i}\) – координатами ее концов. Следующие \(n\) строк содержат описание изображения \(B\) в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения \(A\).
Все координаты по абсолютной величине не превосходят \(10^4\). Все спички имеют ненулевую длину, то есть \(x_{1i}\) ≠ \(x_{2i}\) или \(y_{1i}\) ≠ \(y_{2i}\).
Выведите в выходной файл минимальное количество спичек, которые следует переложить, чтобы изображение \(A\) совпало с изображением \(B\), с точностью до параллельного переноса.
5 0 0 1 2 1 0 0 2 2 0 2 2 4 0 3 2 4 0 5 2 9 -1 10 1 10 1 9 3 8 1 10 1 8 1 9 -1 8 1 9 3
3
Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из \(h\) уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на \(m\) × \(n\) участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.
Принц может перемещаться с одного участка на другой участок того же уровня, если у этих участков есть общая сторона, и ни один из этих участков не содержит колонну. Это перемещение занимает у Принца 5 секунд.
Полы в лабиринте Джаффара чрезвычайно тонкие, и Принцу не составляет труда сильным ударом ноги проломить пол под собой, если только на соответствующем участке нижнего уровня не находится колонна. Когда пол проламывается, Принц проваливается на один уровень вниз, при этом не перемещаясь в горизонтальной плоскости. Это действие также занимает у Принца 5 секунд. Конечно, если Принц уже находится на самом нижнем уровне, то пол под ним не проломится.
На одном из участков нижнего уровня Принца ждет Принцесса, отказавшаяся выйти замуж за злого Джаффара. Помогите Принцу найти Принцессу, потратив на это как можно меньше времени.
В первой строке входного файла содержатся натуральные числа \(h\), \(m\) и \(n\) – высота и горизонтальные размеры лабиринта (2 ≤ \(h\), \(m\), \(n\) ≤ 50). Далее во входном файле приведены \(h\) блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему.
Каждый блок содержит \(m\) строк, по \(n\) символов в каждой: «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o») обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса.
Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» – в описании самого верхнего уровня, а символ «2» – в описании самого нижнего.
Соседние блоки разделены одной пустой строкой.
В выходной файл выведите минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Поскольку Добро всегда побеждает Зло, гарантируется, что Принц может это сделать.
3 3 3 1.. oo. ... ooo ..o .oo ooo o.. o.2
60
По заданным числам \(a\), \(b\), \(c\) и \(d\), найдите наименьшее натуральное число \(n\), большее \(ac\), которое нельзя представить в виде произведения двух натуральных чисел \(u\) и \(v\), таких что \(a\) ≤ \(u\) ≤ \(b\) и \(c\) ≤ \(v\) ≤ \(d\).
Входной файл содержит одну строку, состоящую из натуральных чисел \(a\), \(b\), \(c\), \(d\) (1 ≤ \(a\) ≤ \(b\) ≤ \(10^6\), 1 ≤ \(c\) ≤ \(d\) ≤ \(10^6\)).
Выведите в выходной файл искомое число \(n\).
1 2 1 2
3
1 2 3 5
7
Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.
Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь следующей таблицей.
Шаблон группы Баллы aa 2 aba 2 aab, abb 2 aaa 3 abac, baca 2 abab 3 aabb 3 abba 4 baaa, abaa, aaba, aaab 3 aaaa 5
В этой таблице символами «a», «b», «c» обозначены различные цифры. Например под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888».
Пользуясь предложенной оценкой, найдите наиболее красивое разбиение заданного номера.
Входной файл содержит одну строку из 7 цифр – заданный телефонный номер.
Выведите в первой строке выходного файла наиболее красивое разбиение номера, а во второй – величину его красоты.
Если разбиений с максимальной величиной красоты несколько, выведите в выходной файл любое из этих разбиений.
8727333
8727-333 5
8827291
88-272-91 4
В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов. Теперь служителей зоопарка интересует, сколькими способами можно выбрать трех животных для участия в выставке.
Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:
1) первый медведь, тигр и лев;
2) первый медведь, тигр и пингвин;
3) первый медведь, лев и пингвин;
4) второй медведь, тигр и лев;
5) второй медведь, тигр и пингвин;
6) второй медведь, лев и пингвин;
7) тигр, лев и пингвин.
В первой строке входного файла содержится натуральное число \(n\) – количество видов животных в городском зоопарке (1 ≤ \(n\) ≤ \(10^5\)).
В каждой из следующих \(n\) строк содержится одно натуральное число – количество животных соответствующего вида. Общее число животных в зоопарке не превышает \(10^5\).
В выходной файл выведите количество способов выбрать трех животных для международной выставки.
4 2 1 1 1
7
3 30000 30000 30000
27000000000000