Задача A. Торт с вишенками

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В кафе «Пингвин» посетителям предлагается фирменный торт, который имеет форму равностороннего треугольника. Перед подачей торт делится на порции. Каждая порция торта также имеет форму равностороннего треугольника, на котором сверху лежит одна вишенка.

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

Повар испек торт площадью S. Определить число вишенок, которое потребуются после деления общего торта на порции максимально допустимой площади.

Формат входного файла

Входной файле содержит целые числа S M.

Формат выходного файла

Выходной файл должен содержать искомое число вишенок.

Ограничения

1 ≤ N ≤ S ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
20 5
4

Задача B. Бег по коридору

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

В начале у игрока нулевой уровень усталости. Каждое перемещение добавляет к текущему уровню усталости единицу. Как только игрок перемещается на пиксель, занятый эликсиром, он выпивает эликсир, и уровень усталости уменьшается на единицу. Таким образом, перемещение на пиксель с эликсиром не увеличивает уровня усталости. Когда игрок покидает клетку, на которой был эликсир, она становится свободной.

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

Вам необходимо написать программу, которая по заданному плану коридора определит минимальный уровень усталости, с которым можно пройти игру.

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

В выходной файл выведите единственное число — минимальный уровень усталости, которого можно достичь, пройдя игру.

Ограничения

2 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
..
.#
1
2
6
....X.
#XXX..
3

Задача C. Числовая последовательность

Автор:Методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

Дима недавно поступил на работу в Научно-исследовательский институт числовых последовательностей. Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей.

Недавно руководитель отдела, где начал работать Дима, столкнулся с весьма интересной последовательностью чисел a1, a2, …, an, …, которая определяется следующим образом: a1 = 0 и каждое последующее число ai+1 (i ≥ 1) определяется как наименьшее натуральное число, большее ai, десятичная запись которого не содержит цифр, представленных в десятичной записи ai. Требуется написать программу, которая заданному n вычисляет величину an.

Формат входного файла

Входной файл содержит целое число n.

Формат выходного файла

Выходной файл должен содержать число an.

Ограничения

1 ≤ n ≤ 500

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
0
2
28
911

Задача D. Разрезанная рамка

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Прямоугольная рамка была разрезана на N кусков. Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка, соединённых под прямым углом.

По данным длинам отрезков требуется восстановить исходную рамку или определить, что это невозможно. Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.

Формат входного файла

Входной файл содержит число кусков N, за которым следуют N пар целых чисел ai bi, описывающих длину двух отрезков "уголка" i-го куска. Если кусок является отрезком, то ai = 0 либо bi = 0.

Формат выходного файла

Выходной файл должен содержать два положительных целых числа W H — ширину и высоту рамки, при этом W ≥ H. Если решения не существует, следует выдать число 1. Если решений несколько, следует выдать решение с максимальным значением W.

Ограничения

1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10
1 1  1 1
1 0  1 0  1 0  1 0
0 2  0 2  0 2  0 2
7 1
2
5
1 1  1 1  1 1  1 1  5 0
-1

0.192s 0.015s 21