Мячик на лесенке

Пусть мячик находится на некоторой ступеньке с номером X. Тогда он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3. Если мы введем функцию F(X), которая определяет число маршрутов со ступеньки X до земли, то F(X) = F(X – 1) + F(X – 2) + F(X – 3). Остается просчитать вручную граничные значения: F(1) = 1, F(2) = 2 (очевидно), F(3) = 4 (3–2–1–0, 3–2–0, 3-1–0, 3–0). Все остальное уже сделано в предыдущей задаче. Чтобы не загромождать функцию, можно присваивания граничных значений сделать заранее, тогда отсечение произойдет автоматически:

Function F(X : integer) : longint;

begin

if D[X] = 0 then D[X] := F(x-1) + F(x-2) + F(x-3);

{для X = 1..3, D[X] > 0 изначально}

F := D[X]

end;

Написание итеративной формы также труда не представляет.

к занятию № 2

Конец формы

Паровозики N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью. Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов. Формат входных данных Два числа — 0 < N < 17 и 0 < p < N + 1. Формат выходных данных Одно число — s.

[посмотреть подсказку] Паровозики

Рассмотрим функцию от трех переменных F(X, Y, Z), которая показывает число расстановок при которых Y паровозиков образуют Z групп, причем самый первый паровозик имеет номер X. Для ответа достаточно просуммировать эту функцию по первой переменной. Разберем, чему наша функция равна. Возможны два варианта — первый паровозик образует отдельную группу или тормозит хотя бы один локомотив за собой. В первом случае необходимо суммировать выражения вида F(I, Y – 1, Z – 1) при I < X (действительно, если “наш паровоз вперед летит”, то лидер хвоста должен иметь меньший номер и при этом образуется на одну группу меньше). Во втором случае — F(I, Y – 1, Z) при I > X (лидер имеет больший номер и при этом образуется столько же групп).

function F(x, y, z : byte) : Tcal;

var i : byte; s : Tcal;

begin

if D[x, y, z] = -1 then

begin

s := 0;

for i := 1 to x - 1 do s := s + F(i, y - 1, z - 1);

for i := x + 1 to y do s := s + F(x, y - 1, z);

D[x, y, z] := s

end;

F := D[x, y, z]

end;

Обратите внимание на тип Tcal. Дело в том, что типа LongInt недостаточно, поэтому требуется использование иных средств. В данном случае положение спасает тип Comp (Double тоже подходит).

Граничные условия попробуйте написать самостоятельно. Сделав это, Вы поймете, что написать итеративное решение за время проведения олимпиады практически невозможно (чемпионы не в счет).

Справедливости ради заметим, что задача допускает строгое математическое решение, связанное с подсчетом сочетаний, но оно ненамного эффективнее рассмотренного здесь.

к занятию № 2

Конец формы

к занятию № 2

Конец формы

Плитки У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

К

К

К

С

З

К

К

З

К

С

(буквой К обозначена красная плитка, С — синяя, З — зеленая). После этого Петя заполняет следующую таблицу:

	Красный	Синий	Зеленый
Красный	Y	Y	Y
Синий	Y	N	Y
Зеленый	Y	Y	N

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски. Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски. Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему. (Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска

С

К

З

К

К

З

С

К

К

К

не совпадает с полоской, приведенной в начале условия.)

Формат входных данных Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична. Формат выходных данных Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

Плитки

Прежде всего вспомним задачу “Взрывоопасность”. Идея, положенная в основу ее решения, заработает и здесь. Итак, разбиваем все полоски из плиток на 64 группы (соответственно количеству матриц смежности), нумеруя их следующим образом. Берем все возможные матрицы смежности (всего их 64) и выписываем 6 букв из матриц подряд (то, что ниже главной диагонали, нас не интересует, так как никакой информации не несет). Меняем “Y” на “1”, а “N” — на “0” и получаем двоичный код нашей группы. Каждую из групп дополнительно разобьем на три подгруппы, в зависимости от плитки, лежащей справа. Теперь наращиваем полоску вновь справа. Прописать вручную все 576 (64 группы, 3 подгруппы, 3 наращиваемых цвета) возможных комбинаций невозможно. К счастью, рассматривать группы нет необходимости, если воспользоваться битовой арифметикой. Достаточно рассмотреть всевозможные пары крайних плиток и определить смежность, которую они образуют. Она способна в каждой группе либо превратить “N” в “Y” (если ранее не встречалась), либо ничего не изменить. Определив позицию возможного изменения, создаем маску, в которой все биты равны нулю, кроме изменяемого. Остается только применить полученную маску к каждой группе (путем логического “или”). Не стоит забывать, что все эти операции производятся над длинными числами.

Function Check(i, j : shortint; s : integer) : integer;

var r, k : integer;

begin

if i > j then begin k := j; j := i; i := k end;

if i = 2 then j := j + 2;

if i = 3 then j := j + 3;

r := 1;

for k := 1 to j - 1 do r := r * 2;

Check := s or r; {применяем маску r к группе s}

end;

...

for i := 0 to 63 do

begin

for l := 1 to 3 do

for k := 1 to 3 do

begin

NewS := Check(l, k, i);{определяем новый номер группы}

Add(Na[News][k], A[i][l], Na[NewS][k]);{и добавляем в нее все, что было в старой}

{Na[News][k] := Na[News][k] + A[i][l] — аналог в обычной арифметике}

end

end;

к занятию № 2

Конец формы

От автора сайта А.П. Шестакова: Настоящая публикация подготовлена Евгением Владимировичем Брызгаловым, аспирантом кафедры информатики факультета информатики и экономики ПГПУ, неоднократным участником олимпиад сначала школьников, а затем и студентов по программированию. В 1999-2000 учебном году команда, капитаном которой был Е.В. Брызгалов, вышла в полуфинал международных командных соревнований студентов по программированию АСМ.

 

Конец формы

Конец формы