Разбор решений

A. Будильник
Тема: простая задача

В зависимости от значений введенных `S` и `T` вывести либо разность `T-S` либо `T+12-S`.

var s,t:integer;
begin
  assign(input,'input.txt');
  assign(output,'output.txt');
  reset(input);
  rewrite(output);
  read(s,t);
  if s<=t then writeln(t-s)
  else writeln(t+12-s);
  close(input);
  close(output);
end.

B. Калах
Тема: техническая задача, моделирование

Для хранения текущего состояния игры будем использовать массив `d`:

  d:array[1..2, 1..7] of integer;

Номер игрока, делающего ход, хранится в переменной `h`:

  h:integer;

Инициализируем эти переменные следующим образом:

for s:=1 to 2 do
begin
  for i:=1 to 6 do
    d[s,i]:=3;
  d[s,7]:=0;
end;
h:=1;

Для каждого хода выполняем следующие действия:

var s, { текущая сторона калаха }
    k, { камни в руке }
    p:integer; { номер текущей лунки }
...
{ считываем номер лунки }
read(p);
{ забираем все камни из лунки }
k:=d[h,p];
d[h,p]:=0;
{ начиная со следующей лунки }
inc(p);
s:=h; 
while true do
  begin
    { кладем камень }
    inc(d[s,p]); 
    dec(k);
    { камней не осталось - выходим из цикла }
    if k=0 then break;
    inc(p);
    if (p>7) or (p>6) and (s<>h) { дошли до калаха } then
    begin
      s:=3-s; { Переходим на другую сторону}
      p:=1;
    end;
  end;

Когда камни разложены, проверяем условия на специальные ходы:

if (s=h) and (d[h,p]=1) and (p<7) and (d[3-h,7-p]>0) then
  { положили последний камень в пустую лунку на своей стороне }
  begin
    { перекладываем камни в калах из своей и противоположной лунок }
    d[h,7]:=d[h,7]+d[3-h,7-p]+d[h,p];
    d[h,p]:=0;
    d[3-h,7-p]:=0;
  end;
{ если последний камень попал не в свой калах - передаем ход }
if p<>7 then 
  h:=3-h;

После обработки всех ходов выводим состояние лунок:

for s:=1 to 2 do
  begin
    for i:=1 to 6 do
      write(d[s,i],' ');
    writeln(d[s,7]);
  end;

С. Саванна
Тема: поиск в глубину

Для работы потребуются следующие переменные:

var n, { количество животных }
  d,   { максимальное расстояние между животными одного стада }
  k,   { количество стад }
  i:longint;

  x,y:array[1..1000] of longint; { координаты животных }

  f:array[1..1000] of boolean; { флажки - животное отнесено к какому-то стаду }

Эти переменные инициализируются следующим образом:

read(n,d);
for i:=1 to n do
  begin
    read(x[i],y[i]);
    f[i]:=false;
  end;
k:=0;

Для отнесения животного к какому-то стаду используем рекурсивную подпрограмму:

procedure dfs(i:integer);
var j:integer;
begin
  if f[i] then exit; { уже классифицировали - выходим }
  f[i]:=true; { отмечаем флажком }
  for j:=1 to n do 
    { для всех животных на расстоянии не более D }
    if sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(d) then
      dfs(j); { делаем те же действия }
end;

Теперь для всех непомеченных животных вызываем эту подпрограмму и увеличиваем счетчик стад `k`:

for i:=1 to n do
  if not f[i] then
    begin
      inc(k);
      dfs(i);
    end;

После завершения цикла выводим значение `k`.


D. Возрастающие числа
Тема: динамическое программирование

Все возможные "возрастающие числа" занесем в массив `"num"` в лексикографическом порядке:

type numinf=record val,len:longint; end;
const num:array[1..39] of numinf=(
(val:1;len:2),(val:123;len:4),(val:1234;len:4),
  (val:12345;len:4),(val:123456;len:4),(val:12;len:3),
(val:2;len:2),(val:234;len:4),(val:2345;len:4),
  (val:23456;len:4),(val:234567;len:4),(val:23;len:3),
...
(val:8;len:2),(val:89;len:3),
(val:9;len:2));

Минимальную длину будем получать в массиве `"minlen"`:

  minlen:array[0..1000000] of longint;

который нужно инициализировать следующим образом:

for i:=1 to n do { для значений, которые еще не обработаны }
  minlen[i]:=1000000; { установить достаточно большое число }
minlen[0]:=0; { 0 можно получить с помощью строки нулевой длины }

Теперь, двигаясь по таблице от 0 до `n`, узнаем самую короткую длину разложения числа `i` на возрастающие числа. Используется принцип динамического программирования: из оптимального решения подзадач можно получить оптимальное решение всей задачи.

for i:=0 to n do
  begin
    { добавляем к лучшему способу получения числа i
      все возможные возрастающие числа }
    for j:=1 to 39 do
      begin
        k:=i+num[j].val;
        { получаем новый способ получения числа k }
        if (k<=n) and (minlen[k]>minlen[i]+num[j].len) then
           { если длина этого способа меньше, запоминаем его в массиве }
          minlen[k]:=minlen[i]+num[j].len;
      end;
  end;

Обратная трассировка по массиву `"minlen"`:

s:='';
while n>0 do
  begin
    { рассматриваем возрастающие числа в лексикографическом порядке }
    for j:=1 to 39 do
      begin
        k:=n-num[j].val;
        if (k>=0) and (minlen[k]+num[j].len=minlen[n]) then
          { если с помощью этого числа получается способ,
            дающий нужную минимальную длину, 
            то используем именно это число }
          begin
            { добавляем возрастающее число к строке-результату }
            str(num[j].val,ss);
            if length(ss)<=2 then
              s:=s+ss+'+'
            else
              s:=s+ss[1]+'-'+ss[length(ss)]+'+';
            n:=k; { уменьшаем искомое число на возрастающее число }
            break;
          end;
      end;
  end;
{ выводим строку-результат без последнего символа '+' }
writeln(copy(s,1,length(s)-1));