Разбор задач командного тура

A. Хлопушки (Морской бой – 2)

Автор задачи: Александр Торопов

Автор разбора: Александр Торопов

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

Соседями клетки являются две соседние клетки по вертикали (номер строки отличается на единицу) и две соседние клетки по горизонтали (номер столбца отличается на единицу). Таким образом, координаты этих клеток есть: (i - 1,j), (i + 1,j), (i,j - 1) и (i,j + 1). Отметим, что соседей у клетки не всегда четыре — например, у угловой клетки всего два соседа. Приведем программную реализацию этого подхода.

Пример программы на Delphi:

readln(n, m);
for i := 1 to n do begin
  readln(s[i]);
end;

ans := 0;

for i := 1 to n do begin
  for j := 1 to m do begin
    if (s[i][j] = ’*’) then begin
          continue;
        end;
        t := 0;
        if ((i = 1) or (s[i - 1][j] = ’.’)) then begin
      inc(t);
        end;
        if ((i = n) or (s[i + 1][j] = ’.’)) then begin
          inc(t);
        end;
        if ((j = 1) or (s[i][j - 1] = ’.’)) then begin
      inc(t);
    end;
        if ((j = m) or (s[i][j + 1] = ’.’)) then begin
      inc(t);
    end;
        if (t = 4) then begin
          inc(ans);
        end;
  end;
end;

writeln(ans);

B. Конфеты (Сбор черники)

Автор задачи: Александр Торопов

Автор разбора: Сергей Поромов

В этой задаче необходимо найти три рядом расположенных куста таких, что сумма количества ягод на них максимальна. При этом необходимо учитывать то, что грядка круглая, и поэтому можно взять, например, последний и два первых куста. Заметим также, что число ягод невелико и для его хранения можно использовать 32-битный целочисленный тип данных (longint в языке Pascal, int в языке C, int в языке Java).

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

Этот алгоритм работает за линейное от n время. Один из способов обрабатывать то, что грядка является круглой, — использовать массив длиной n + 2 и в последние два элемента записать первые два.

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

 
for i := 1 to n do
  read(a[i]);
a[n + 1] := a[1];
a[n + 2] := a[2];
ans := 0;
for i := 1 to n do begin
  if (a[i] + a[i + 1] + a[i + 2] > ans) then begin
    ans = a[i] + a[i + 1] + a[i + 2];
  end;
end;
write(ans);

С. СМС (Антипалиндром)

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

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

Заметим, что число подстрок строки длины n равно 1 + 2 + … + n = n * (n + 1)/2. Это объясняется тем, что строка длины n содержит одну подстроку длины n, две подстроки длины n - 1, …, n подстрок длины 1. Таким образом, время работы решения, основанного на переборе всех подстрок будет пропорционально как минимум n². Такое решение не укладывается в ограничения по времени.

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

Докажем теперь, что если ни один из этих двух случаев не реализуется, то строка, получаемая из s отбрасыванием первого символа не является палиндромом. Итак, строка s является палиндромом, но не все ее символы равны между собой. Обозначим как t строку, получающуюся из s отбрасыванием первого символа. Докажем с помощью метода «от противного», что t не является палиндромом.

Для этого предположим, что t = s₂s₃…s_n является палиндромом. Из этого следует, что ее первый и последний символ равны между собой, то есть s₂ = s_n. Из того, что s равно палиндромом следует, что s₁ =s_n. Таким образом, получаем, что s₁ = s₂ = s_n. Далее, из того, что s является палиндромом так же следует, что s_n-1 = s₂. Значит, s₁ = s₂ = s_n = s_n-1. Из того, что t является палиндромом следует, что s₃ = s_n-1. Значит, цепочка равенств расширяется далее: s₁ = s₂ = s_n = s_n-1 = s₃. Продолжая это рассуждение, получаем, что все символы строки s равны между собой, что противоречит предположению. Значит, доказано, что строка t не является палиндромом.

Это рассуждение приводит нас к следующему решению. Возможны три случая:

• все символы строки s равны между собой — тогда ответ NO SOLUTION;
• строка s не является палиндромом — тогда ответом является сама строка s;
• иначе ответом является строка t, получающаяся из s отбрасыванием первого символа.

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

 
read(s);
n := length(s);

allSame := true;
pali := false;

for i := 2 to n do begin
  if (s[i] <> s[i - 1]) then begin
    allSame := false;
  end;
end;

for i := 1 to n do begin
  if (s[i] <> s[n - i + 1]) then begin
    pali := true;
  end;
end;

if (allSame) then begin
  writeln(’NO SOLUTION’)
end else if (not pali) then begin
  for i := 1 to n - 1 do begin
    write(s[i]);
  end;
end else begin
  writeln(s);
end;

D. Задача (K-перестановки)

Автор задачи: Сергей Мельников

Автор разбора: Антон Феськов

Заметим, что перестановок из девяти чисел относительно немного, их число равно 9! = 362880. Поэтому можно перебрать все перестановки из n чисел и проверить каждую их них, является ли она k-перестановкой.

Приведем фрагмента программы на языке Паскаль.

 
procedure go(pos : integer);
var
  i : integer;
begin
  if (pos = n + 1) then begin
    for i := 1 to n - 1 do begin
      if abs(p[i] - p[i + 1]) > k then begin
        exit;
      end;
    end;
    inc(ans);
    exit;
  end;
  for i := 1 to n do begin
    if (not w[i]) then begin
      w[i] := true;
      p[pos] := i;
      go(pos + 1);
      w[i] := false;
    end;
  end;
end;

Процедура go(pos) перебирает все возможные еще не использованные числа, которые можно поставить на позицию pos в перестановке p, если мы знаем все предыдущие числа. Для того, чтобы эффективно проверять, было использовано число или нет, поддерживается булев массив w, причем w[i] = true если i уже использовано и false иначе. Если выполнено неравенство pos > n, то мы построили какую-то перестановку, осталось проверить, что она является k-перестановкой. Если это так, то увеличиваем ответ — переменную ans. 

E. Шарики (Индикатор)

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

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

Решение этой задачи, в целом, будет таким: в обоих случаях цифры будут приписываться к числу по одной, начиная со старших разрядов.

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

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

За один шаг к числу будет приписываться одна цифра. Для этого необходимо перебрать очередную цифру d. Обозначим число черных полосок в изображении цифры d как black[d]. После приписывания цифры d к существующему числу останется дописать к нему n - 1 цифру, а число полосок, которые должны быть черными в оставшихся разрядах будет равно k -black[d].

Тут необходимо проверить, хватит ли черных полосок на то, чтобы написать оставшиеся цифры. Например, если исходно n = 2, k = 8, а в качестве первой цифры d мы пробуем поставить восьмерку, то на оставшуюся одну цифру остается одна полоска. Так как ни одной цифры, изображаемой с помощью одной полоски, не существует, то восьмерку в качестве старшей цифры поставить нельзя. С другой стороны, если n = 2, k = 10, а в качестве первой цифры выбрать единицу, то на оставшуюся цифру остается восемь полосок. Таких цифр также не существует, поэтому единица первой цифрой быть не может.

Поэтому возникает задача проверки того, может ли быть составлено число, содержащее n цифр и kчерных полосок. Для того, чтобы решить эту подзадачу, заметим, что в изображении одной цифры могут участвовать две, три, четыре, пять, шесть или семь полосок. Наиболее важно тут то, что эти числа заполняют собой отрезок целых чисел от двух до семи. Значит, n чисел из этого множества могут давать в сумме любое число от 2 * n до 7 * n. Таким образом, для решения указанной подзадачи достаточно проверить двойное неравенство 2 * n ≤ k ≤ 7 * n.

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

 
min := ’’;
ck := k;
cn := n;
for i := 1 to n do begin
  st := 0;
  if (i = 1) then begin
    st := 1;
  end;
  for j := st to 9 do begin
    nk := ck - cnt[j];
    if (nk >= 2 * (cn - 1)) and (nk <= 7 * (cn - 1)) then begin
      min := min + chr(ord(’0’) + j);
      ck := nk;
      cn := cn - 1;
      break;
    end;
  end;
end;

Здесь переменная st обозначает цифру, с которой начинается перебор — для старшего разряда st = 1, для всех остальных — st = 0.

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

max := ’’;
ck := k;
cn := n;
for i := 1 to n do begin
  st := 0;
  if (i = 1) then begin
    st := 1;
  end;
  for j := 9 downto st do begin
    nk := ck - cnt[j];
    if (nk >= 2 * (cn - 1)) and (nk <= 7 * (cn - 1)) then begin
      max := max + chr(ord(’0’) + j);
      ck := nk;
      cn := cn - 1;
      break;
    end;
  end;
end;