Разбор задач командного тура XV чемпионата СыктГУ по программированию

XV Открытый чемпионат СыктГУ по программированию. 

Командный тур. 19 апреля 2014 год

Задачи A – F контеста были взяты с диска «Программируй с чемпионами. Интернет-олимпиады 2008-2009 года. Базовый уровень». Новые формулировки сделаны Н.К.Поповой  За оригинальными условиями рекомендую обратиться к сайту Олимпиады по информатике

Источником задач G, H  была книга "Казанский турнир по программированию" под редакцией Д.Г. Хохлова (Казань: Изд-во Казан. гос. техн. ун-та, 2010). Новые формулировки, тесты подготовлены Н.О.Котелиной.

Тексты разбора задач взяты в оригинальной редакции.

A. Ключ

Лимит времени 1000/2000/2000/2000 мс.  Лимит памяти 65000/65000/65000/65000 Кб. 

Лёша — весьма продвинутый молодой домовой. Живет он в квартире вполне современной колдуньи. Компьютер, телевизор, телефон… Больше всего Лёше нравится серфинг – в Интернете так много советов по домоводству. Но колдунья поставила пароль на компьютер, и каждый день меняет его. На компьютерном столе колдунья оставляет листочек с двумя числами n и p. Лёша знает алгоритм получения ключа, с помощью которого можно восстановить пароль.

Алгоритм. Из всех наборов натуральных чисел рассматриваются те, которые состоят из n элементов, а их произведение равно p. Ключ равен наибольшей из возможных сумм элементов такого набора.

Например, существует два набора из трех натуральных чисел, произведение которых равно четырем: 1, 2, 2 и 1, 1, 4. Сумма элементов первого набора равна пяти, а второго — шести, следовательно, ключ равен шести.

Помогите Лёше вычислить ключ.

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

Первая строка входного файла два целых числа n и p (1 ≤ n, p ≤ 1000).

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

В выходной файл выведите искомый ключ.

Пример входного и выходного файлов

input	output
2 2	3
3 4	6

Разбор задачи «Ключ»

Автор задачи: Владимир Ульянцев

Автор разбора: Антон Банных

Сначала решим задачу для наборов из двух чисел (n = 2). Докажем, что ответом для данного p будет p + 1, то есть максимальную сумму имеет набор (1, p). Действительно, пусть оптимальным является набор (a, b), где 2 ≤ a ≤ b, a × b = p. Тогда a + b  ≤  2 × b  ≤   a × b  =  p < p + 1.

Аналогично для n > 2 можно показать, что ответом является p + n - 1. Для этого в оптимальном наборе (a₁, a₂, …, a_n) будем последовательно заменять соседние пары чисел a_i, a_i+1 на пары (1, a_i × a_{i + 1}), не изменяя произведение и не уменьшая сумму, пока не получим набор (1, 1,...,p).

Фрагмент решения на языке Паскаль.

read(n, p);
writeln(p + n - 1);

Время работы алгоритма — O(1). 

 

B. Заклинание

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

Сильно рассердил молодую ведьму один наглый леший, и она его послала. Уж послала, так послала… Послала его заклинанием, составленным из букв N, E, S, W. А надо сказать, что лес вокруг избы колдуньи бесконечно простирается во всех направлениях и поделен просеками на кварталы. И каждая буква из заклинания посылает несчастного лешего (а не хами ведьме!) из квартала в квартал:

• перейти в следующий квартал на север — N;
• перейти в квартал на юг — S;
• перейти в квартал на запад — W;
• перейти в квартал на восток — E.

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

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

Первая строка входного файла содержит заклинание. Оно состоит только из символов N, S, W, E. Длина строки положительна и не превосходит 1000 символов.

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

В выходной файл выведите число кварталов, в которых леший побывает более одного раза.

Пример входного и выходного файлов

input	output
NWSE	1
NEWS	2

Разбор задачи «Робот»

Автор задачи: Федор Царев

Автор разбора: Федор Царев

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

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

Можно создать двумерный массив целочисленного типа field (field: array[1..2001, 1..2001] of integer), который будет соответствовать полю. Каждый элемент этого массива соответствует некоторой клетке поля, а его значением будет число посещений роботом этой клетки.

Для вычисления ответа после окончания моделирования работы программы необходимо найти число элементов массива field, значения которых больше единицы.

Приведем программу (Попова Н.К. - для задачи "Заклинание"), реализующую этот подход.

var r, c, i, a, ans: integer;

nm, nm1: string;

ch: char;

field: array[-1000..1000]of array[-1000..1000] of integer;

begin

    fillchar(field,sizeof(field),0);

    r:= 0; c:=0;

    while not eof do begin

       inc(field[r][c]);

       read(ch);

       case ch of

       'N': dec(r);

       'S': inc(r);

       'W': dec(c);

       'E': inc(c);

       end;

    end;

    inc(field[r][c]);

       a:=0;

       for r:=-1000 to 1000 do

       for c:=-1000 to 1000 do

       if field[r][c] > 1 then inc(a);

       writeln(a);

end.

Второй подход основан на идее, схожей с идеей решения задачи о нахождении числа различных элементов в массиве. Для этого создается массив посещенных клеток (каждая клетка, как и раньше, задается двумя числами — ее координатами). После этого указанный массив упорядочивается по возрастанию первых координат клеток (при их равенстве — по возрастанию вторых координат).

Приведем фрагмент программы, реализующий этот этап решения.

readln(s);
r := 0;
c := 0;
n := length(s);
p := 1;
for i := 1 to n do begin
  a[p][1] := r;
  a[p][2] := c;
  inc(p);
  ch := s[i];
  if (ch = ’L’) then begin
    c := c - 1;
  end else if (ch = ’R’) then begin
    c := c + 1;
  end else if (ch = ’U’) then begin
    r := r - 1;
  end else if (ch = ’D’) then begin
    r := r + 1;
  end;
end;
a[p][1] := r;
a[p][2] := c;
inc(p);

for i := 1 to p do begin
  for j := i + 1 to p do begin
    if (a[j][1] < a[i][1]) or
       ((a[j][1] = a[i][1]) and (a[j][2] < a[i][2])) then begin
      t := a[i][1];
      a[i][1] := a[j][1];
      a[j][1] := t;

      t := a[i][2];
      a[i][2] := a[j][2];
      a[j][2] := t;
    end;
  end;
end;

Здесь двумерный массив a хранит координаты клеток, посещенных роботом — элементы a[i][1] хранят номера строк, в которых находятся эти клетки, а a[i][2] — номера столбцов. Также отметим, что здесь выбор начального положения робота не важен, так как не происходит обращения к элементам массива с номерами, равными координатам клетки.

Заметим, что если робот k раз посетил некоторую клетку, то в этом массиве координаты этой клетки будут присутствовать также ровно k раз, причем они будут занимать несколько подряд идущих элементов. Используя это, можно найти ответ на задачу – для этого необходимо выделить такие отрезки одинаковых клеток, и найти число отрезков, длина которых превышает единицу.

Приведем программную реализацию этого этапа.

ans := 0;
i := 1;
while (i < p) do begin
  j := i;
  while (j < p) and (a[i][1] = a[j][1]) and (a[i][2] = a[j][2]) do begin
    inc(j);
  end;
  if (j - i > 1) then begin
    inc(ans);
  end;
  i := j;
end;

Здесь переменная i соответствует началу очередного отрезка, а переменная j используется для определения его конца. На каждой итерации она изначально равна i, а затем увеличивается до тех пор, пока не будет найден элемент, содержащий клетку, не равную a[i]. Его обнаружение соответствует тому, что найдено начало нового отрезка. В этом случае длина текущего отрезка сравнивается с единицей, и, при необходимости, увеличивается значение переменной ans, используемой для вычисления ответа на задачу. 

C. Конгруэнтная последовательность

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

Скучно Водяному в его болотах. Вспомнил он учебу в Универе, занудные лекции профессоров и, особенно, лекцию по линейному конгруэнтному методу получения псевдослучайных последовательностей. И, чтобы скоротать время, начал выписывать последовательности чисел. Целыми днями он выписывает их на бересте. Интереснее всего ему показалась последовательность чисел, заданная следующими соотношениями:

Здесь x, y, z и w — некие натуральные числа, которые первыми пришли Водяному на ум. Операция mod – это операция вычисления остатка от целочисленного деления.
Не один и не два, а три дня Водяной выписывал свою последовательность и, наконец, понял, что выписал n чисел и пошел к Лешему – показывать числа. А Леший возьми и спроси его, какое число является k-ым по порядку, если эту последовательность упорядочить по неубыванию. И тут на Водяного напала лень, поэтому он обратился к Вам за помощью. Ответьте на вопрос Лешего.

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

В первой строке находятся четыре числа x, y, z и w. Эти числа положительны и не превосходят 10000. Во второй строке находятся два целых числа n и k (1 ≤ k ≤ n ≤ 100000).

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

В выходной файл выведите ответ на вопрос Лешего.

Пример входного и выходного файлов

input	output
1 1 100 2 5 2	3
1 1 100 200 3 2	2

Разбор задачи «Последовательность»

Автор задачи: Сергей Поромов

Автор разбора: Федор Царев

Во-первых, заметим что так как по условию n ≤ 10⁵, то все элементы последовательности могут быть достаточно быстро вычислены. Это можно сделать, например, так.

read(x, y, z, w);
read(n, k);
a[1] := w;
for i := 2 to n do begin
  a[i] := (x * a[i - 1] + y) mod z;
end;

После выполнения этого фрагмента программы массив a будет заполнен теми числами, которые Вася записал на полях своей тетради. Теперь заметим, что последнее действие, которое выполняется при вычислении очередного элемента a[i] (для i > 1), — это взятие остатка от деления на z. Это означает, что все элементы массива a, начиная со второго и до последнего, находятся в промежутке от 0 до z - 1. Из этого и из того, что w по условию не превосходит 10000, следует, что все элементы массива a находятся в промежутке от 0 до 10000.

Воспользуемся идеей, сходной с идеей сортировки «подсчетом», — для каждого из чисел от 0 до 10000 найдем, сколько раз оно встречается в массиве a.

for i := 1 to n do begin
  inc(cnt[a[i]]);
end;

После выполнения этого фрагмента программы в каждый элемент cnt[i] массива cnt будет содержать число вхождений числа i в массив a. Для того, чтобы теперь найти ответ на задачу, будем последовательно от 0 в возрастающем порядке перебирать натуральные числа (до 10000) и для каждого из них проверять, является оно k-ым в порядке неубывания или нет.

Рассмотрим некоторое целое число b (0 ≤ b ≤ 10000). Рассмотрим все числа b, такие что в массиве a количество чисел, не превосходящих b, больше либо равно k. Минимальное из них является ответом на задачу. Это же условие можно записать следующим образом.

Непосредственная программная реализация этой формулы может оказаться недостаточно эффективной для решения задачи, так как будет требовать порядка 10000² = 10⁸ операций.

Заметим, что соответствующие суммы для b и для (b + 1) отличаются на одно слагаемое. Поэтому пересчет этой суммы можно производить за O(1). Приведем фрагмент программы, реализующий этот этап решения задачи.

s := 0;
for b := 0 to 10000 do begin
  s := s + cnt[b];
  if (s >= k) then begin
     writeln(b);
     break;
  end;
end;

Заметим, что при такой реализации автоматически получается то, что будет найдено минимальное b. Это обеспечивается тем, что как только требуемое число b находится, так сразу происходит выход из цикла с помощью оператора break. 

D. Прудоны

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

Реки, ручьи, озера, протоки, каналы, бобровые запруды образуют сложнейшую водную сеть, разумными обитателями которой являются русалки и водяные. В языке русалок много слов для обозначения водоемов. Мы будем называть водоемы прудами и каналами. В прудах живут, каналами путешествуют из одного пруда в другой. Всего в сети n прудов и m каналов. К некоторым прудам ведет только один канал, а другие соединены между собой многими каналами. В таких прудах кипит жизнь, там образуются прудоны. Пруд называют прудоном k-го уровня, если к нему ведут k каналов.

Кто-то любит сельскую тишину и покой, другим нравится жить в прудонах. Молодая семья Водяных хочет жить в прудоне, уровень которого не ниже k . По заданному описанию водной сети найдите все подходящие прудоны.

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

Первая строка входного файла содержит число n прудов (1 ≤ n ≤ 10000) и число m каналов (0 ≤ m ≤ 100000). Каждая из последующих m строк описывает один канал и содержит два числа u и v (1≤ u, v ≤ n, u ≠v) — номера прудов, соединенных каналами. Последняя строка входного файла содержит целое число k (1 ≤ k ≤ 10000). Каждый канал упоминается во входном файле не более одного раза.

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

В первой строке выведите число c прудонов. Во второй строке выведите их номера в порядке возрастания.

Пример входного и выходного файлов

input	output
2 1 1 2 1	2 1 2
4 3 1 2 1 3 1 4 3	1 1

Разбор задачи «Транспортные узлы»

Автор задачи: Федор Царев

Автор разбора: Федор Царев

Формулировка этой задачи на языке теории графов такова. Задана граф, содержащий n вершин (соответствуют городам) и m ребер (соответствуют дорогам). Необходимо найти все вершины этого графа, степень которых больше либо равна k. Напомним, что степенью вершины называется число инцидентных ей ребер.

Несмотря на такую «графовую» формулировку задачи, для ее решения не требуется знание каких-либо специальных алгоритмов. Необходимо вычислить степени всех вершин, а затем найти вершины, удовлетворяющие указанном свойству.

Для вычисления степеней вершин создадим массив deg, i-ый элемент которого deg[i] будет содержать степень вершины i. Для заполнения этого массива при чтении очередного ребра uv необходимо увеличить на единицу значение deg[u] и deg[v].

Далее, необходимо найти число вершин со степенью хотя бы k и номера таких вершин.

Приведем программную реализацию этого алгоритма.

read(n, m);
for i := 1 to m do begin
  read(u, v);
  inc(deg[u]);
  inc(deg[v]);
end;
read(k);
cnt := 0;
for i := 1 to n do begin
  if (deg[i] >= k) then begin
    inc(cnt);
  end;
end;
writeln(cnt);
for i := 1 to n do begin
  if (deg[i] >= k) then begin
    write(i, ’ ’);
  end;
end;
writeln;

Время работы этого алгоритма составляет O(n + m). 

E. Гламурия

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

В крупнейшем прудоне водяных и русалок поселился колдун с учениками и занялся промышленным производством гламурии, сильно увеличивающей привлекательность русалок. Один из важнейших ингредиентов гламурии – икра попугайной жабы. Для каждой дозы гламурии нужна одна икринка. К сожалению, икра поступает очень неравномерно. Колдун опасается, что его “защекотят до икоты и на дно уволокут”, если спрос не будет удовлетворен. К счастью, колдун заметил, что после использования на стенках икринки еще остается некоторое количество ценного секрета. Силами учеников было построено магическое устройство, которое из m использованных икринок производит k новых (магия жизни!). Полученные таким образом икринки совершенно идентичны натуральным икринкам и также могут быть переработаны.
Колдун хочет узнать, сколько доз гламурии можно изготовить из каждой из n партий икринок, которые остались на складе. Вам поручается исследовать данный вопрос.

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

В первой строке входного файла содержатся целые числа n, m, k (1 ≤n ≤ 1000, 1 ≤k < m ≤ 1000000). Во второй строке входного файла содержится n целых чисел ai — число натуральных икринок в i-й партии (1 ≤ ai ≤ 1000000 ).

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

Для каждого числа ai выведите отдельной строкой количество икринок, которое можно произвести из i-й партии, используя магию жизни.

Пример входного и выходного файлов

input	output
2 6 1 36 30	43 35
1 5 2 11	17

Разбор задачи «Производство деталей»

Автор задачи: Владимир Ульянцев

Автор разбора: Антон Банных

Предположим, что нам известна оптимальная стратегия использования капсул. Заметим, что если в какой-то момент часть капсул нужно пустить на переработку, то детали из них можно производить непосредственно перед переработкой. Применяя это рассуждение, можно объединить процесс переработки и изготовления деталей и получить неделимую операцию: взять m полных капсул, произвести m деталей и получить k полных капсул. Кроме того, из полной капсулы можно произвести деталь, а использованную капсулу выбросить.

Теперь применим метод динамического программирования. Пусть d[i] — максимальное число деталей, которое можно получить из i капсул при фиксированных m и k. Очевидно, что d[0] = 0. Из предыдущих рассуждений следует, что при i < m d[i] =d[i - 1] + 1, а при i >= m d[i] = max(d[i - 1] + 1,d[i - m + k] + m).

Вычислим значения массива d для всех возможных a_i (по условию задачи a_i ≤ 10⁶), после чего ответим на все запросы просто обратившись к d[a_i].

Фрагмент решения, на языке Паскаль:

 
read(n, m, k);
d[0] := 0;
for i := 1 to 1000000 do begin
        d[i] := d[i - 1] + 1;
        if (i >= m) then
                d[i] := d[i - m + k] + m;
end;
for i := 1 to n do begin
        read(a);
        write(d[a], ’ ’);
end;

Время работы алгоритма есть O(max(a_i)) (по условию задачи max(a_i) = 10⁶).

Особо отметим, что при некоторых значениях параметров m и k ответ для больших a_i превышает максимальное допустимое значение 32-битного типа. Например, при m = 100000, k = 99999 из 10⁶ капсул можно получить 90000199999 деталей. Оценить сверху ответ можно как m × max(a_i), что при данных ограничениях составляло порядка 10¹². Это показывает, что для хранения значений d[i] необходимо использовать 64-битный тип данных. 

F. Телепортация

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

Передвижение между прудонами по каналам – это приятное, но очень медленное путешествие. Те, кто торопится, перемещаются телепортами. Перед телепортацией маг изучает интерференционную картину в виде концентрических колец, которая показывает максимумы и минимумы возмущения магического поля, и строит модель переноса. Модель простая. На плоскости строится система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны1, 2, 3, …. Также на плоскости рисуется отрезок, концы которого находятся в телепортах с координатами (x1, y1 ) и (x2, y2). Маг-телепортист рассчитывает стоимость телепортации, учитывая число общих точек этого отрезка и указанной системы окружностей.

Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

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

Первая строка входного файла содержит четыре целых числа: x1, y1, x2 и y2. Эти числа не превосходят 1000 по абсолютной величине. Заданный отрезок имеет ненулевую длину.

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

В выходной файл выведите ответ на задачу.

Пример входного и выходного файлов

input	output
1 1 2 1	1
1 2 2 1	0

Разбор задачи «Отрезок и окружность»

Автор задачи: Владимир Ульянцев

Автор разбора: Антон Ахи

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

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

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее.

Const
 eps = 1e-9;
Var
 x1, y1, x2, y2 : longint;
 a, b, d : double;
 ans : longint;

begin
 reset(input, ’circles.in’);
 rewrite(output, ’circles.out’);
 read(x1, y1, x2, y2);
 d := abs((y2 * x1 - x2 * y1) /
      sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
 a := sqrt(x1 * x1 + y1 * y1);
 b := sqrt(x2 * x2 + y2 * y2);
 ans := 0;
 if (x1 * x1 + y1 * y1 - x2 * x2 - y2 * y2
  + (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) < 0) or
   (-x1 * x1 - y1 * y1 + x2 * x2 + y2 * y2
  + (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) < 0) then
 begin
  ans := ans + trunc(max(a, b) + eps) - trunc(min(a, b) - eps);
 end else
 begin
  ans := ans + trunc(a + eps) - trunc(d - eps);
  ans := ans + trunc(b + eps) - trunc(d - eps);
  if (abs(round(d) - d) < eps) and (abs(d) > eps) then
  begin
   dec(ans);
  end;
 end;
 writeln(ans);
 close(Input);
 close(Output);
end.

Здесь d — расстояние до прямой, которая содержит отрезок, a и b — расстояния до концов отрезка. 

G. Цеккендорф

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

«Тяжело в учении – зато легко в бою», - так говорят в семье маленькой ведьмы Алисы. Действительно, магия – дело непростое, например, Алиса никак не может наколдовать 10000 конфет, как бы ни старалась! На днях в школе ведьм на занятии по основам магии Алиса проходила тему «Знаменитые формулы заклинаний» и узнала, как использовать натуральные числа в заклинаниях. Оказывается, знаменитый маг Цеккендорф доказал такую теорему: «Каждое натуральное число N имеет единственное представление в виде суммы чисел Leonardo Pisano, в которой два соседних числа Leonardo Pisano никогда не используются», и чтобы создать N предметов, надо получить это представление числа N. Алиса хочет создать N конфет. Помогите Алисе.

Дано натуральное число N. Представить его в виде суммы

N=F_k1+F_k2+ ... +F_kr,

где F_i – число Leonardo Pisano, и в этой сумме нет двух рядом стоящих чисел из последовательности Leonardo Pisano и одинаковых чисел из этой последовательности (k1

Справка для тех, кто не знаком с числами Leonardo Pisano:

n	1	2	3	4	5	6	7
Fn	1	1	2	3	5	8	13

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

Входной файл содержит одно натуральное число N (1 ≤ N ≤ 10¹⁸).

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

Выходной файл должен содержать несколько чисел Leonardo Pisano, дающих в сумме число N. Все числа должны быть разделены пробелами и выписаны в порядке возрастания.

Пример входного и выходного файлов

input	output
2	2

Разбор задачи «Теорема Цеккендорфа»

Представление  N = F_k1 + F_k2 + … + F_kr, где F_i - число Фибоначчи, всегда можно найти "жадным алгоритмом": в качестве F_k1 выбирается наибольшее число Фибоначчи F_k1 ≤ N, затем в качестве F_k2 выбирается наибольшее число F_k2 ≤ N - F_k1и так далее.

Так как числа натуральные и последовательность чисел убывающая, то процесс конечен.

Для ускорения работы можно получить с помощью элементарной программы таблицу первых 90 чисел Фибоначчи и включить таблицу в программу (Котелина Н.О.).

#include

#include
#include
 #include
using namespace std;

long long f[90]={1,1,2,3,5,8,13,21,34,55,
89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,
28657,46368,75025,121393,196418,317811,
514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,
39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,
1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,
53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,
956722026041,1548008755920,2504730781961,4052739537881,6557470319842,
10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,
117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,
1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,
14472334024676221,23416728348467685,37889062373143906,61305790721611591,
99194853094755497,160500643816367088,259695496911122585,420196140727489673,
679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120};
//---------------------------------------------------------------------------
void fib(long long n){
vector a(90);
cin>>n;
int  r=0;
int i;
do  {
i=sizeof(f)/sizeof(long long)-1;
while (f[i]>n&&i>0) i--;

a[r]=f[i]; r++;
if (f[i]==n)
break;
else
n-=f[i]; }
while (n>0);

for (int t = r-1; t>=0; t--) {
cout< }
}

int main()
{
long long a;
cin>>a;
fib( a);
return 0; 

 _}

 H. Трубопровод

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

С целью снижения экологической нагрузки на каналы, грузы перемещают по трубопроводу. Проблема в том, что контейнеры с грузами нужно переставить так, чтобы в каждом прудоне их можно было отцепить. Для решения этой проблемы построена мощная трансферная зона, позволяющая переставить контейнеры в требуемом порядке. Кортеж, содержащий n контейнеров (1≤n≤50), приближается к трансферу справа. Требуется переставить контейнеры так, чтобы слева на выходе сформировался кортеж с заданным порядком номеров p1, p2,…,pn. Конечный кортеж перемещается влево.

Робот-автомат может выполнять всего четыре операции:
A. Перемещение контейнера из начального кортежа в трансфер справа.
B. Перемещение контейнера с левой стороны трансфера в конечный кортеж.
C. Перемещение контейнера из начального кортежа в трансфер слева.
D. Перемещение контейнера с правой стороны трансфера в конечный кортеж.

Все операции выполняются поочередно. Трансфер вмещает 621615 контейнеров.

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

В первой строке входного файла содержится натуральное число n (1 ≤ n ≤ 50), за которым следуют числа. Во второй строке входного файла содержится n целых чисел p1, p2,…,pn, которые образуют перестановку целых чисел от 1 до n.

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

Выходной файл должен содержать в первой строке слово «NO», если требуемый кортеж получить невозможно. В противном случае в первой строке выводится слово «YES», а вторая строка содержит без пробелов последовательность из букв A, B, C и D, определяющую операции для получения этой перестановки. Если решений несколько, то вывести любое из них.

Пример входного и выходного файлов

input	output
3 1 3 2	YES ADACBB
5 5 1 3 2 4	NO

Разбор задачи «Вагоны»

Данная задача поставлена Дональдом Кнутом в его знаменитой книге "Искусство программирования", том 1. Он ссылается на малодоступную статью Р.Тарьяна, в которой приведен алгоритм, выясняющий возможность получения данной перестановки за линейное число O(n) шагов.

Можно предложить следующий простой линейный по времени алгоритм решения этой задачи. По заданной перестановке (p[1], ..., p[n]) получим обратную перестановку q[p[i]] = i - очередность p[i] на выходе разъезда, обладающую свойством p[q[i]] = i. 

В дек вместо номеров поступающих вагонов i будем помещать номера этих вагонов на выходе разъезда q[i].

Пусть i1< i2 < i3 < i4 < i5/ Заданная перестановка  (p[1], ..., p[n]) невозможна тогда и только тогда, когда внутри дека оказывается вагон, путь которого к правому и левому выходу закрывают вагоны с большей очередностью, выезжающие из дека после него, то есть в деке возникает условие тупика:

                                                                  q[i2]> ... q[i1]....< q[i3].                                          (1)

Все вагоны смогут выехать налево, если их размещать в деке по возрастанию очередности выезда слева направо (можно -наоборот: справа налево - симметричное решение):
                                                                    q[il] < ... < q[ik].                                                     (2)
В ситуации (2) можно без тупика поместить любой вагон: либо слева, если его очередь меньше q[il], либо справа, избегая тупиковой ситуации (1).
В качестве примера рассмотрим перестановку для n = 5:
i       =  1   2   3   4   5 

p[i] = 5   1  3   2  4
q[i] = 2   4  3   5  1
Первым при i = 1 поместим q[i] = q[l] = 2. Для i = 2 поместим q[2] = 4 > q[l] в дек справа. Дек будет содержать: 2, 4.
При i = 3, q[3] = 3 нельзя помещать слева — закроется выход вагона с очередностью 2. Придется поместить правее 4 - условие (2) не удалось сохранить - дек: 2, 4, 3.
Возможность выезда сохраняется, но возникла более опасная, чем (2), ситуация:

                                                          q[i1] < ...< q[i2] > q[i3]                                                     (3)
Ситуация (3) сохраняется, пока приходят вагоны с такой очередностью q[i4], что q[i4] < q[1] - поместим слева, или q[il] < q[i4] < q[i3] - поместим справа.
В ситуации (3) тупик возникнет при поступлении вагона с такой очередностью q[i4], что q[i4] > q[il], q[i4] > q[i3]. Перестановка невозможна.
Для перестановки (p[il], p[i2], p[i3], p[i4], p[i5]) при условии

                              q[i5] < min (q[i1], q[i2], q[i3], q[i4]),

                              (q[i3] - q[i1])(q[i3] - q[i2]) <0 nbsp="" p="">

                               q[i4] > min (q[i1], q[i2]), q[i4] > q[i3]
тупик неизбежен при любой стратегии. Наш «жадный» позволяет максимально долго его избегать.
В программе для моделирования разъезда реализуем дек -  двустороннюю очередь (или двусторонний стек) в виде кольцевого вектора d с запоминанием количества элементов kd и двумя указателями: индексами b - первого и e - последнего элемента.

Приведем программу (Н.О. Котелина)

const nmax=250; tmax=2*nmax;
var n,i,j:integer;
p,q:array[0..nmax] of integer;
t:array[1..tmax] of char;
it:integer;
d:array[0..nmax] of integer;
b,e,kd:integer;
ok:boolean;
iqmin,iqmax:integer;
procedure D_in;
begin
 inc(it); t[it]:='A';
 if e d[e]:=q[j]; inc(kd);
 inc(j);
end;
procedure in_D;
begin
 inc(it);
 t[it]:='C';
 if b>0 then dec(b) else b:=n;
 d[b]:=q[j]; inc(kd);
 inc(j);
end;
begin
 read(n);
 for i:=1 to n do begin
  read(p[i]);  q[p[i]]:=i;
 end;
 ok:=true; it:=0;
 b:=1; e:=0; kd:=0;
 i:=1; j:=1;
 while ok and ((i<=n)or (j<=n)) do begin
  if kd=0 then begin
   d_in;
   Iqmin:=b; Iqmax:=b;
  end else
  if (i=d[b]) then begin
   inc(it); t[it]:='B';
   if b   inc(i); dec(kd);
   if kd>0 then
    if d[b]  end
  else if (i=d[e]) then begin
   inc(it); t[it]:='D';
   if e>0 then dec(e) else e:=n;
   inc(i); dec(kd);
   if kd>0 then
    if d[b]  end
  else if q[j]   if Iqmin=e then begin
    D_in; Iqmin:=e;
   end else begin
    in_D; Iqmin:=b;
   end
  end
  else if q[j]>d[Iqmax] then begin
   if Iqmax=e then begin
    D_in; Iqmax:=e;
   end
   else if Iqmax=b then begin
    in_D; Iqmax:=b;
   end else ok:=false;
 end
 else begin
  if (Iqmin=b) and (q[j]   D_in
  else if (Iqmin=e) and (q[j]  in_D
  else ok:=false;
 end;
end;
if ok then begin
 writeln('YES');
 for i:=1 to 2*n do write(t[i]);
end else
 write('NO');
 writeln;
end.