ЛШ олимпиада 2011 - Инкубатор Бабы Яги

Задача D. Инкубатор Бабы Яги ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

У Бабы Яги в избушке на курьих ножках есть инкубатор, в котором появляются куры с различным количеством ног. Ног может быть от одной до шести. Каждый день в инкубаторе появляется ровно одна курица.

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

Сотрудники института собрали статистические данные. В течение нескольких дней они записывали количество ног у появившейся курицы.

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

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

Входной файл содержит целое число N, за которым следуют N целых чисел от 1 до 6 — результаты измерений количества ног у кур в течение N дней.

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

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

Если решений несколько, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`12 3 1 1 1 2 1 3 2 2 5 6 2`	`1 3 6 0 0 0`
2	`10 3 6 3 6 2 3 2 6 3 2`	`0 2 3 0 0 4`

Разбор

Будем решать задачу по очереди для одноногих, двуногих, трёхногих, четырёхногих, пятиногих и шестиногих кур. Будем просматривать исходный массив. Переменная x будет хранить индекс последнего встретившегося числа, равного текущему количеству ног l. Переменная px будет хранить индекс предпоследнего встретившегося числа, равного текущему количеству ног. Переменные x и px легко обновляются:

if (a[i] = l) then
begin
  px := x;
  x := i;
end;

Тогда количество дней между последовательными появлениями кур с определённым количеством ног равно x-px. Осталось подсчитать, сколько раз встречается каждое возможное количество дней между последовательными появлениями кур с таким количеством ног. Для этого заполним массив cnt. А затем найдём максимум в этом массиве.

program incubator;
const
  MAX_N = 1000;
var
  a: array[1..MAX_N] of integer;
  cnt: array[1..MAX_N-1] of integer;
  n: integer;
  x, px: integer;
  max, max_i: integer;
  i, l: integer;
begin
  read(n);
  for i := 1 to n do
    read(a[i]);

  for l := 1 to 6 do
  begin
    for i := 1 to n-1 do
      cnt[i] := 0;
    x := 0;
    px := 0;
    for i := 1 to n do
    begin
      if (a[i] = l) then
      begin
        px := x;
        x := i;
        if ((x <> 0) and (px <> 0)) then
          inc(cnt[x-px]);
      end;
    end;
    max := 0;
    for i := 1 to n-1 do
    begin
      if (cnt[i] > max) then
      begin
        max := cnt[i];
        max_i := i;
      end;
    end;
    if (max = 0) then
      write(0, ' ')
    else
      write(max_i, ' ');
  end;
end.