Разбор задач

A. Семь гномов

Тема: перебор, моделирование
Сложность: средняя

В задаче требуется найти такую перестановку `Q_i` чисел от 1 до 7, которая дает минимальный суммарный недосып.

Сначала рассмотрим способы гнерации всех перестановок чисел от 1 на 7. На 1-е место можно поставить любое из 7 чисел, на 2-е – одно из оставшихся 6 чисел, на 3-е – одно из оставшихся 5 чисел, и т.д. Соответствующая часть программы может выглядеть так:

var q:array [1..7] of integer;
...
for q[1]:=1 to 7 do
  for q[2]:=1 to 7 do
    if q[2]<>q[1] then
      for q[3]:=1 to 7 do
        if (q[3]<>q[1]) and (q[3]<>q[2]) then
          for q[4]:=1 to 7 do
             if (q[4]<>q[1]) and (q[4]<>q[2]) and (q[4]<>q[3]) then
               for q[5]:=1 to 7 do
                 if (q[5]<>q[1]) and (q[5]<>q[2]) and 
                    (q[5]<>q[3]) and (q[5]<>q[4]) then
                   for q[6]:=1 to 7 do
                     if (q[6]<>q[1]) and (q[6]<>q[2]) and 
                        (q[6]<>q[3]) and (q[6]<>q[4]) and (q[6]<>q[5]) then
                       for q[6]:=1 to 7 do
                          if (q[7]<>q[1]) and (q[7]<>q[2]) and 
                            (q[7]<>q[3]) and (q[7]<>q[4]) and
                            (q[7]<>q[5]) and (q[7]<>q[6]) then
                            {В массиве q получили перестановку}

Для упрощения программы можно завести массив флажков, в котором отмечать те числа, которые уже используются, и организовать выполнение вложенных циклов с помощью рекурсии:

var q:array [1..7] of integer;
  used:array [1..7] of boolean;
  i:integer;
procedure rec(i:integer);
var j:integer;
begin
  if i>7 then
  begin
    {В массиве q получили перестановку}
    exit;
  end
  for j:=1 to 7 do
    if not used[j] then
    begin
      used[j]:=true;
      q[i]:=j;
      rec(i+1);
      used[j]:=false;
    end;
end;  
...
for i:=1 to 7 do
  used[i]:=false;
rec(1);

Существует немного более сложный, но более эффективный способ генерации перестановок. Генерация начинается с последовательности 1, 2, …, 7. На `i`-м шаге число, стоящее на `i`-м месте меняется с одним из чисел, стоящих на местах с `i`-го по 7-ое и рекурсивно выполняется (`i`+1)-й шаг. По окончании шага нужно восстановить состояние массива на начало шага.

var q:array [1..7] of integer;
  i:integer;
procedure rec(i:integer);
var j,t:integer;
begin
  if i>7 then
  begin
    {В массиве q получили перестановку}
    exit;
  end
  for j:=i to 7 do
  begin
    t:=q[i];
    q[i]:=q[j];
    q[j]:=t;
    rec(i+1);
  end;
  t:=q[i];
  for j:=i+1 to 7 do
    q[i-1]:=q[i];
  q[7]:=t;
end;  
...
for i:=1 to 7 do
  q[i]:=i;
rec(1);

После получения перестановки нужно промоделировать, как будут просыпаться гномы. В массив `S_i` поместим на сколько минут раньше проснется гном, спящий на `i`-м месте.

for i:=1 to 7 do
  s[q[i]]:=c[i]*abs(p[i]-q[i]);

Когда гном просыпается он будит также всех гномов, лежащих ближе к выходу. Гном не может спать дольше гномов, спавших глубже в штреке, поэтому при просмотре массива `S_i` справа налево находим максимум. Суммарное время недосыпа можно вычислить так:

sum:=0;
m:=0;
for i:=7 downto 1 do
begin
  if s[i]>m then
    m:=s[i];
  sum:=sum+m;
end;

Среди сумм недосыпа находим минимум и запоминаем перестановку, при которой он достигается. После обработки всех перестановок выводим перестановку, минимизирующую суммарный недосып.

B. Очередь

Тема: моделирование, цикл, поиск максимума
Сложность: простая

Считываем тест посимвольно до конца строки. Если введен символ '+', увеличиваем счетчик на 1. Если введен символ '-', уменьшаем счетчик на 1. После изменения счетчика проверяем, не стало ли его значение больше достигнутого ранее максимума.

var k,m:integer;
  ch:char;
begin
  while not eoln do
  begin
    read(ch);
    if ch='+' then
      inc(k)
    else
      dec(k);
    if m<k then m:=k;
  end;
  writeln(m);
end.

C. Високосный год

Тема: логические операции and/or, условный оператор
Сложность: простая

var n:integer;
begin
  read(n);
  if ((n mod 4)=0) and ((n mod 100)<>0) or ((n mod 400)=0) then
    writeln('Yes')
  else
    writeln('No');
end.

D. Гномья нумерация

Тема: динамическое программирование
Сложность: средняя

Решить эту задачу можно несколькими способами. Первый способ – динамическое программирование. Храним в таблице kol минимальное число слагаемых для получения числа `i`, а таблице how – какое слагаемое было использовано для получения числа `i` оптимальным образом. Первоначально все элементы массива kol содержат какое-то большое число, например, 1000. Массив gnome содержит гномьи слагаемые.

var gnome:array[1..54] of integer;
    kol,how:array[0..1000000] of integer;
...
for i:=0 to 1000000 do
  kol[i]:=1000;

Тогда заполнить массивы kol и how можно следующим образом:

kol[0]:=0;
for i:=0 to 1000000 do
  for j:=1 to 54 do
  begin
    k:=gnome[j]+i;
    if k<=1000000 then
      if kol[i]+1<kol[k] then
      begin
        kol[k]:=kol[i]+1;
        how[k]:=gnome[j];
      end;
  end;

Второй способ – использование запоминающей функции. Чтобы определить, сколько слагаемых потребуется для представления числа `i`, нужно найти вариант с минимальным числом слагаемых после вычитания из `i` одного из гномьих слагаемых. Чтобы повторно не решать одну и ту же задачу, результат расчета запоминаем в массивах kol и how. Вычисление функции, определяющей минимальное число слагаемых, выполняется только в том случае, если оно ранее для числа `i` не выполнялось.

function minkol(i:integer):integer;
var j,k:integer;
begin
  if kol[i]=1000 then
  begin
    if i=0 then
      kol[i]:=0
    else
    begin
      for j:=54 downto 1 do
        if gnome[j]<=i then
        begin
          k:=minkol(i-gnome[j]);
          if k+1<kol[i] then
          begin
            how[i]:=gnome[j];
            kol[i]:=k+1;
          end;
        end;
    end;
  end;
  minkol:=kol[i];
end;

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

var q:array[0..1000000] of integer;
  q1,q2:integer;
...
q1:=0;
q2:=1;
q[0]:=0;
kol[0]:=0;
while q1<q2 do
begin
  i:=q[q1];
  inc(q1);
  for j:=1 to 54 do
  begin
    k:=gnome[j]+i;
    if (k<=1000000) and (kol[k]=1000) then
    begin
      kol[k]:=kol[i]+1;
      how[k]:=gnome[j];
      q[q2]:=k;
      inc(q2);
    end;
  end;
end;

Сумма выводится с использованием массива how, который заполняется во всех трех способах:

write(n,'=');
while n>0 do
begin
  write(how[n]);
  n:=n-how[n];
  if n>0 then write('+');
end;
writeln;

E. Гномий язык

Тема: работа со строками
Сложность: ниже среднего

Проходим по строке, если встречается гласная, и это не первая гласная в слове, проверяем, какая буква стоит перед ней (так как это не первая гласная, то какая-то буква перед ней точно есть). Если согласная, но не 'h', то вставляем перед ней '-'. Если буква 'h' – смотрим предыдущую букву (аналогично, так как это не первая гласная, перед 'h' должна быть ещё буква), в случае гласной вставляем '-' перед 'h', в случае согласной – перед предыдущей буквой. При вставке символа '-' для перехода к следующей букве увеличиваем индекс `i` не на 1, а на 2.

var s:string;
  i,n:integer;
begin
  readln(s);
  i:=1;
  n:=0;
  while i<=length(s) do
  begin
    if pos(s[i],'aeiou')>0 then
    begin
      inc(n);
      if n>1 then
      begin
        if s[i-1]='h' then
        begin
          if pos(s[i-2],'aeiou')>0 then
            insert('-',s,i-1)
          else
            insert('-',s,i-2);
          inc(i);
        end
        else if pos(s[i-1],'aeiou')=0 then
        begin
          insert('-',s,i-1);
          inc(i);
        end;
      end;
    end;
    inc(i);
  end;
  writeln(s);
end.

F. Сокровища Казад Дума

Тема: поиск в ширину, двоичное кодирование
Сложность: выше среднего

Текущее состояние комнаты можно представить как целое число из `N` x `N` бит, если валун находится в `(i,j)`-й клетке комнаты, то `((i-1)*N+j-1)`-й бит в этом числе установлен в 1, иначе – в 0. Для преобразования из позиции в число и обратно можно использовать следующие подпрограммы:

type position=array[1..4,1..4]of char;

function encode(const pos:position):integer;
var i,j,k,p:integer;
begin
  p:=0;
  k:=1;
  for i:=1 to n do
    for j:=1 to n do
    begin
      if pos[i][j]='@' then
        p:=p or k;
      k:=k*2;
    end;
  encode:=p;
end;
procedure decode(p:integer; var pos:position);
var i,j,k:integer;
begin
  k:=1;
  for i:=1 to n do
    for j:=1 to n do
    begin
      if (p and k)<>0 then
        pos[i][j]:='@'
      else
        pos[i][j]:='.';
      k:=k*2;
    end;
end;

Далее можно воспользоваться алгоритмом поиска в ширину. В массиве q хранится очередь из позиций, которые нужно обработать, q1 – индекс первого элемента в очереди, q2 – индекс первого свободного элемента. В массиве h записываем количество ходов, которое необходимо, чтобы получить эту позицию из начальной. Если позиция i еще не была достигнута, в h[i] храним `-1`.

const undef=-1;
var q,h:array[0..65535]of integer;
    pos:position;
    n,p,i,j,st,fn,q1,q2:integer;
...
procedure movestone(i1,j1,i2,j2:integer);
var np:integer;
begin
  if (i2<1) or (i2>n) or (j2<1) or (j2>n) then exit;
  if pos[i2][j2]<>'.' then exit;
  pos[i2][j2]:='@'; {двигаем валун}
  pos[i1][j1]:='.';
  np:=encode(pos);
  if h[np]=undef then {позиция ранее не достигалась } 
  begin {добавляем ее в очередь}
    h[np]:=h[p]+1;
    q[q2]:=np;
    inc(q2);
  end;
  pos[i2][j2]:='.'; {двигаем валун обратно}
  pos[i1][j1]:='@';  
end;
procedure readpos;
var i,j:integer;
begin
  for i:=1 to n do
  begin
    for j:=1 to n do
      read(pos[i][j]);
    readln;
  end;
end;
...
begin
  readln(n)
  readpos(pos);
  st:=encode(pos);
  readpos(pos);
  fn:=encode(pos);
  for i:=0 to 65535 do
    h[i]:=undef;
  h[st]:=0;
  q[0]:=st;
  q1:=0;
  q2:=1;
  while q1<q2 do
  begin
    p:=q[q1];
    inc(q1);
    decode(p,pos);
    for i:=1 to n do
      for j:=1 to n do
      if pos[i][j]='@' then
      begin {пытаемся сдвинуть валун во всех направлениях}
        movestone(i,j,i-1,j);
        movestone(i,j,i+1,j);
        movestone(i,j,i,j-1);
        movestone(i,j,i,j+1);
      end;
  end;
  writeln(h[fn]);
end.

G. Головоломка

Тема: геометрия, графы
Сложность: высокая

Сначала проверяем, не находится ли конечное положение монеты слишком близко к одной из других монет. Если `(D_i-D_1)/2` больше или равно расстоянию между центром `i`-й монеты и конечным положением 1 первой монеты, то выводим "NO" и завершаем выполнение программы.

Далее рассмотрим все пары монет, если расстояние между ними не позволяет провести между ними первую монету, то рисуем отрезок, соединяющий центры этих монет. Если расстояние между монетой и стенкой коробки не позволяет провести первую монету между ней и стенкой, рисуем перпендикуляр из центра монеты на соответствующую стенку.

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

Реализацию этого алгоритма можно найти в задаче 5 областной олимпиады школьников по информатике 2005 года.

H. Покраска забора

Тема: дерево максимумов, сортировка или списки
Сложность: высокая

Сначала нужно отсортировать начала и концы отрезков, соответствующей попытке гнома покрасить забор. В C/C++ можно использовать стандартную функцию qsort/sort, в Pascal нужно либо написать эту функцию самостоятельно, либо реализовать более простой алгоритм сортировки расстановкой. Значения с одинаковым ключом храним в виде списков.

var 
  sl:array [1..100001] of integer; 
  tries:array [1..100000] of record
    color:char; 
    i,j:integer;
    nexti,nextj:integer;
  end;
  N,M,i,j,k,p:integer;
...
readln(N,M);
for i:=1 to M do
begin
  readln(tries[i].color,tries[i].i,tries[i].j);
  tries[i].nexti:=sl[tries[i].i];
  sl[tries[i].i]:=i;
  tries[i].nextj:=sl[tries[i].j+1];
  sl[tries[i].j+1]:=i;
end; 

Далее используем дерево максимумов, в котором в ячейке `i` хранится максимальное из чисел в ячейках `2*i` и `2*i+1`. Неиспользуемые ячейки дерева помечаются значением 0. Листья дерева располагаются все на одном уровне и начинаются с ячейки 131072 (`=2^17`, первая степень двойки большая `10^5`). При обработке начала `k`-й попытки гнома покрасить забор, значение `k` в помещается ячейку (131071+`k`), при обработке конца попытки – в эту ячейку помещается 0.

var maxtree:array[1..262144] of integer;
...
for i:=1 to N do
begin
  j:=sl[i];
  while j<>0 do
  begin
    k:=j+131071;
    if tries[j].i=i then
      maxtree[k]:=j
    else      
      maxtree[k]:=0;
    while k>1 do
    begin
      p:=k div 2;
      if maxtree[2*p]>maxtree[2*p+1] then
        maxtree[p]:=maxtree[2*p]
      else
        maxtree[p]:=maxtree[2*p+1];
      k:=p;
    end;
    if tries[j].i=i then
      j:=tries[j].nexti
    else
      j:=tries[j].nextj;
  end;
  if maxtree[1]=0 then
    write('.')
  else
    write(tries[maxtree[1]].color);
end;
writeln;

В C++ вместо дерева максимумов можно использовать стандартный класс set.