Подразделы

Другие разделы

Дата и время

15/09/2026 20:32:35

Авторизация

Зарегистрироваться
Восстановить пароль

Разбор задач отборочных командных соревнований школьников 2010

Разбор задачи G. Конфеты

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

Наихудшим вариантом по количеству конфет, при котором у Гомера не будет `K` конфет или более одного сорта, является вариант, когда у Гомера будет по `(K-1)` конфет каждого из `N` сортов. Но если к ним добавить хотя бы еще одну конфету, неважно какого сорта, то цель будет достигнута. Таким образом ответом на задачу будет значение `(K-1)*N+1`.

Разбор задачи A. Потерянная страница

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

Ответ можно найти по формуле

`sum_{i=1}^n\ i\ -\ sum_{i=1}^{n-1}\ p_i`,

где `p_i` – номера собранных страниц. Эту формулу можно еще упростить, вспомнив следующую историю о детстве математика Гаусса.

Школьный учитель математики, чтобы занять первокласников на время, пока он будет занимать с другими учениками, предложил им сосчитать сумму чисел от 1 до 100. Юный Гаусс заметил, что попарные суммы с противоположных концов одинаковы: 1+100=101, 2+99=101 и т.д., и мгновенно получил результат 5050.

Используя эту идею, можно легко найти сумму элементов любой арифметической прогрессии. Если выписать под последовательностью `a_1\ …\ a_n` те же элементы в обратном порядке, то суммы в каждом столбце будут одинаковы и равны `a_1\ +\ a_n`. В сумме этих `n` слагаемых каждый элемент исходной последовательности будет учтен дважды, поэтому результат сложения `(a_1\ +\ a_n)*n` нужно поделить на 2.

`sum_{i=1}^n\ a_i\ =\ {(a_1\ +\ a_n)*n}/2`

После применения формулы для суммы арифметической прогрессии получаем

`{(1\ +\ n)*n}/2\ \ -\ sum_{i=1}^{n-1}\ p_i`

Также для решения этой задачи можно применить сортировку расстановкой, работающую за время `O(n)`, или быструю сортировку, работающую за время `O(n\ log\ n)`. Использование сортировки пузырьком, работающей за время `O(n^2)`, приводит к превышению предела времени в тестах, где `n` велико.

Разбор задачи C. Городской парад

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

Моделируем работу Виггама по регулированию движения платформ. На каждом шаге нужно выбрать одно из трех возможных действий:

Отправить прибывшую платформу на площадь. Это можно сделать только в случае, когда номер прибывшей платформы равен номеру платформы, которую нужно отправить на площадь.
Отправить первую платформу с боковой улицы на площадь. Это можно сделать только в случае, когда номер первой платформы на боковой улице равен номеру платформы, которую нужно отправить на площадь.
Отправить прибывшую платформу на боковую улицу. Это можно сделать только в случае, если есть прибывшие платформы.

Если Виггам не может выполнить ни одно из этих действий, то печатаем сообщение "NO". Если все `N` платформ попали на площадь, печатаем сообщение "YES". Номера платформ на боковой улице нужно хранить в виде очереди.

var q,p:array[1..100] of integer;
    i,pfirst,n,qfirst,qlast:integer;
begin
  read(n);
  for i:=1 to n do
    read(p[i]);
  qfirst:=1; { Индекс первого элемента в очереди }
  qlast:=1; { Индекс первой свободной ячейки в очереди }
  pfirst:=1; { Индекс элемента с номером прибывшей платформой }
  i:=1; { Номер платформы, которую нужно отправлять на площадь }
  while i<=n do
  begin
    if (pfirst<=n) and (p[pfirst]=i) then  
    begin { Отправить прибывшую платформу на площадь }
      inc(pfirst);
      inc(i);
    end
    else if (qfirst<qlast) and (q[qfirst]=i) then
    begin { Отправить первую платформу с боковой улицы на площадь }
      inc(qfirst);
      inc(i);
    end
    else if (pfirst<=n) then
    begin { Отправить прибывшую платформу на боковую улицу }
      q[qlast]:=p[pfirst];
      inc(qlast);
      inc(pfirst);
    end
    else
    begin { Нет больше платформ }
      writeln('NO');
      halt;
    end;
  end;
  writeln('YES');
end.

Разбор задачи F. Резервное копирование

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

На первом этапе алгоритма необходимо отсортировать файлы в порядке уменьшения их размеров, сохраняя исходный порядок в случае одинакового размера. Такая сортировка называется стабильной. Сортировка пузырьком является стабильной, а быстрая сортировка или сортировка выбором – нет. В данном случае количество значений невелико (`N\ ≤\ 1000`), поэтому можно применить сортировку пузырьком, работающую за время `O(N^2)`.

type info=record i,s:longint; end;
var f:array[1..1000] of info; { вместо массива записей можно определить 2 массива }
    tmp:info;
    i,j,N,S,C:longint;
    fl:boolean;
...
  fl:=true;
  while fl do
  begin
    fl:=false;
    for i:=1 to N-1 do
      if f[i].s<f[i+1].s then
      begin
        tmp:=f[i];
        f[i]:=f[i+1];
        f[i+1]:=tmp;
        fl:=true;
      end;
  end;

Далее реализуем второй этап, как описано в задаче. Выравнивание размера файла на размер кластера можно реализовать, например, так:

  cdsize[j]:=cdsize[j]-f[i].s;
  cdsize[j]:=cdsize[j]-cdsize[j] mod C;

Разбор задачи D. Загрузка реактора

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

Для решения этой задачи нужно взять куб из блоков и отсечь от него все лишнее, как говорил Огюст Роден. Лишним в данном случае являются блоки в тех рядах, которые на соответствующих снимках обозначены символом '.'. Если какой-то блок не попадает ни на одном из снимков в пустой ряд, то этот блок нужно оставить, так как в задаче требуется определить максимально возможное количество блоков, находящихся в реакторе.

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

var sn:array[1..3,1..20] of string; { снимки }
    bl:array[1..20,1..20,1..20] of boolean; { куб из блоков }
  i,j,k,kol,n:integer;
...
{ ввод данных }
  readln(n);
  for i:=1 to 3 do
    for j:=1 to n do
      readln(sn[i,j]);
{ заполнение куба }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        bl[i,j,k]:=true;
{ отсечение лишнего }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        if (sn[1,i][j]='.') or (sn[2,i][k]='.') or 
           (sn[3,n-k+1][j]='.') then
          bl[i,j,k]:=false;

После отсечения лишнего могут появиться пустые ряды, находящиеся на снимках в местах, обозначенных символом '#'. Для обнаружения таких новых пустых рядов отметим на снимках символом '+' ряды, в которых есть хотя один блок. Если после таких изменений на снимках останется хоть один символ '#', значит в этом ряду после удаления лишних блоков не осталось ни одного, и, следовательно, на снимках есть противоречия.

  kol:=0;
{ отметка символом '+' непустых рядов и подсчет числа блоков }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        if bl[i,j,k] then
        begin
          sn[1,i][j]:='+';
          sn[2,i][k]:='+';
          sn[3,n-k+1][j]:='+';
          inc(kol);
        end;
{ поиск символов '#' на снимках }
  for i:=1 to 3 do
    for j:=1 to n do
      for k:=1 to n do
        if sn[i,j][k]='#' then
        begin
          writeln(-1);
          halt(0);
        end;
  writeln(kol);

Разбор задачи I. Ксилофон

Тема: вывод формулы
Сложность: средняя

Пусть `N=1`. Рассмотрим треугольники с длиной наибольшей стороны равной `i`. Длина второй по величине стороны `j` может принимать значения от `|__\ {i+3}/2\ __|` до `i-1`, т.е. `|__\ {i-2}/2\ __|` различных значений. Длина самой маленькой стороны может принимать значения от `i-j+1` до `j-1`, т.е. `2*j-i-1` различных значений. Количество возможных треугольников в зависимости от `j` является арифметической прогрессией. Чтобы найти сумму, можно воспользоваться форм

Назад