З Новим Роком!
Розв'язки третього туру приймаються до 0 годин 21 січня 2008 р.
Задача NewCalc
Недавно Петя приобрел калькулятор фирмы NetOI з индикатором на жидких кристаллах (инженеры фирмы NetOI украли схему этого калькулятора у фирмы NEERC, но впоследствии несколько усовершенствовали). Усовершенствованный калькулятор может работать в системах счисления с любым основанием от 2 до 16 (устанавливается специальным переключателем). Индикатор калькулятора отображает каждую из n цифр с помощью элемента, содержащего семь полосок, каждая из которых может быть либо белой, либо черной. В частности, при отображении цифры «1» черными являются две вертикальные правые полоски. Изображения цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, b, C, d, E и F имеют вид:
Пете интересно, какое максимальное и какое минимальное натуральное n-значное число в p-й системе счисления могут быть отображены на индикаторе его нового калькулятора так, чтобы черными были ровно k полосок.
Напишите программу, которая найдет ответ на Петин вопрос. Учтите при этом, что числа не могут начинаться с нулей.
Технические условия. Программа NewCalc должна прочитать с клавиатуры в одной строке через пробелы три целых числа: n, k и p (1≤n≤1000, n≤k≤10000, 2≤p≤16) — количество цифр, количество черных полосок и основание системы счисления. Программа должна вывести на экран в одну строку искомые минимальное и максимальное числа (разделенные одним пробелом). Выводить следует именно такие цифры, которые использует калькулятор (в частности, цифры сл значениями 11 и 13 — маленькие латинские буквы b и d, цифры со значениями 10, 12, 14 и 15 — большие буквы A, C, E и F). Если указанным способом нельзя представить ни одного натурального числа, следует вывести единственную строку NO SOLUTION.
Примеры
Ввод1: 5 15 10
Вывод1: 10117 97111
Ввод2: 1 3 2
Вывод2: NO SOLUTION
Ввод3: 1 4 15
Вывод3: 4 C
Задача LampsPlus
Дано 2n лампочек, каждая из которых может быть в состоянии «вкл.» и «выкл». Вначале все лампочки в состоянии «выкл». Какая-то лампочка меняет свое состояние на противоположное, так повторяется k раз (k-n – четное число), в результате лампочки 1..n находятся в состоянии «вкл», а лампочки n+1..2n –«выкл». Пусть P – количество таких последовательностей переключений, а L количество таких последовательностей, в которых состояние лампочек n+1..2n не менялось ни разу. Найти P и L
Технические условия. Программа LampsPlus читает с клавиатуры 2 натуральных числа n и k (n<=50, k<=100) в одной строке и выводит одной строкой через пробел числа L и P
Пример
Ввод 2 4
Вывод 8 32
Задача Tetris
Игровое поле для игры Tetris имеет размеры 4*N клеток. Пластинки, которыми оно покрывается только одного вида – такие, как изображено на рисунке. Сколько существует разных способов покрытия игрового поля такими пластинками?
Технические условия. Программа Tetris читает с клавиатуры одно натуральное число N <=100 и выводит единственное число – искомую величину.
Пример
Ввод 4
Вывод 10
Задача Streamer
Стороны прямоугольного листка бумаги обозначено A,R,Z,D. Длина сторон Z і D - a, длина сторон A і R - b сантиметров. На стороне Z, в x сантиметрах от стороны R, размещено точку P, а на стороне D, в y сантиметрах от стороны R, размещено точку Q.
Листок согнули по линии PQ. Найдите площадь, покрывающую согнутый листок.
Технические условия Программа Streamer читает с клавиатуры числа a, b, x, y (a, b, £ 1000) и выводит на экран искомую площадь без округлений.
Пример:
Ввод
5 999 3 3
Вывод
2.9970000000E+3
Задача Treasure
В поисках ранее закопанного клада пиратам пришлось прорыть подземный ход в виде незамкнутой ломаной, все отрезки которой лежат на одной глубине. Клад был найден в конце этой ломаной. Найдите кратчайший путь, которым пираты могут вынести клад на ее начало, то есть к началу туннеля.
Технические условия. Программа Treasure читает с клавиатуры количество отрезков ломаной n (1<=n<=25), а далее - n+1 пару целых чисел, не превосходящих 1000 по абсолютной величине – координаты вершин ломаной в порядке обхода (первая пара – координаты начала ломаной, последняя – конца). Программа выводит на экран единственное действительное число (без округления) – искомый путь.
Пример
Ввод 3 2 2 10 8 10 2 2 8
Вывод 10.000000000
Завдания подготовили А. Коротков, Г. Непомнящий, И. Порубльев, Ю.Пасихов
|
