#1652

Кубооктаэдр

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача A ]

Возьмем кубик и приклеим к его граням еще по такому же кубику. В результате получим фигуру, представленную на втором рисунке. К свободным граням полученной фигуры, приклеим еще кубики. На рисунке представлены «кубооктаэдры» степеней 0, 1, 2.

Кубооктаэдром степени N назовем фигуру, полученную в результате N-го доклеивания кубиков. Составить программу, подсчитывающую, количество кубиков для кубооктаэдра N-й степени.

Формат входных данных

На вход дается единственное число – степень кубооктаэдра 0 ≤ N ≤ 100000

Формат выходных данных

Вывести одно число – количество кубиков для кубооктаэдра степени N.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

#1653

Бусинки

Темы: [Деревья] [Обход в ширину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача B ]

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер – целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых фигур не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой.
Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре (на рисунке эти бусинки выделены темным цветом).

Формат входных данных

В первой строке – количество бусинок 1≤N≤2500. В последующих N-1 строках по два целых числа – номера, соединенных бусинок.

Формат выходных данных

Вывести одно число – искомое количество бусинок.

Пример

Входные данные

Выходные данные

7

4 5

6 7

7 4

7 2

1 3

4 1

5

#1654

Лестница

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача C ]

На плоскости дана геометрическая фигура «лестница». Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней «лестницы» треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).

Формат входных данных

В первой строке дано число 0 ≤ N ≤ 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0< x_i, y_i <10⁶ – координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

Формат выходных данных

Файл содержит одну строку: два числа через пробел – высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел.

Примеры

Входные данные

1
5000 199999

Выходные данные

10000.0000 199999.0000

Входные данные

2
1 3
3 1

Выходные данные

0.0000 0.0000

#1655

О ханойских башнях

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача D ]

Имеется три стержня, на один из которых нанизано несколько дисков различного радиуса. Диски расположены так, что на диске с большим радиусом лежит диск с меньшим радиусом (такое правило должно сохраняться всегда). Известна задача «О ханойских башнях», в которой требуется переложить диски с одного стержня на другой оптимальным образом, т.е. за наименьшее число перекладываний.

Существует простое рекурсивное решение данной задачи: * Перекладываем верхние \(n\)-1 диск с начального на промежуточный стержень. * Перекладываем диск \(n\) на последний стержень. * Перекладываем \(n\)-1 диск с промежуточного на последний стержень.

Пример реализации алгоритма на языке Pascal:

Procedure move(n,s,t: integer);
Begin
  If n>1 then move(n-1,s,6-s-t);
  Writeln(s,t);
  If n>1 then move(n-1,6-s-t,t);
End;

а трех стержнях дана правильная раскладка \(N\) дисков (меньший диск лежит на большем). Вам нужно ответить на \(M\) запросов, каждый из которых состоит из двух целых чисел \(s\) и \(t\) – номера стержней. Для каждого запроса требуется определить, является ли данная раскладка промежуточной при перекладывании со стержня \(s\) на \(t\) при оптимальном перекладывании. Раскладка является промежуточной, если она встречается при оптимальном перекладывании со стержня \(s\) на стержень \(t\).

Входные данные

В первой строке дано число 0 ≤ \(N\) ≤ 50000 – количество дисков. Далее записаны \(N\) строк. Каждая строка содержит число – номер стержня, на котором расположен \(i\)-й диск. В следующей строке записано число \(M\) – количество запросов 1 ≤ \(M\) ≤ 6. Далее идет \(M\) строк. Каждая строка содержит пару чисел через пробел 1 ≤ \(s\),\(t\) ≤ 3 (\(s\)≠\(t\)).

Выходные данные

Файл содержит \(M\) строк. В каждой строке содержится слово «YES» (без кавычек), если раскладка дисков является промежуточной при оптимальном перекладывании для \(i\) -го запроса, или слово «NO» (без кавычек) в противном

Примеры

Входные данные

Выходные данные

NO
YES

#1656

Прямоугольники

Темы: [Стек] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача E ]

Дана последовательность N прямоугольников различной ширины и высоты (w_i,h_i). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение , 0 < h_i ≤ 3*10⁴.

Формат выходных данных

Вывести одно число М. Значение M не превосходит 2*10⁹.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные