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

Разбор задачи B. Икебана

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

var i,m,n,h,ans:integer;
  ai,bi:real;
begin
  readln(n,m,h);
  ans:=0;
  for i:=1 to n do
  begin
    readln(ai,bi);
    ai:=ai+bi*(m-1);
    if ai<h then
    begin
      ans:=-1;
      break;
    end;
    if ai>h then
      ans:=1;
  end;
  writeln(ans);
end.

Разбор задачи C. Номер страницы

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

var s:string;
  m,l,k:integer;
begin
  readln(s);
  k:=0;
  l:=length(s);
  for m:=1 to l div 2 do
    if (s[1]<>'0') and (s[m+1]<>'0') and 
      ((m<l-m) or (copy(s,1,m)<=copy(s,m+1,l-m))) then
      inc(k);
  writeln(k);
end.

Разбор задачи A. Летопись

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

uses sysutils;
const mday:array[1..12] of integer=(31,28,31,30,31,30,31,31,30,31,30,31);
var s,a,b,c:string;
    dates:array[1..6] of string;
    k,i:integer;
procedure check(ds,ms,ys:string);
var d,m,y,i:integer;
    fl:boolean;
    newdate:string;
begin
  d:=strtoint(ds); { Переводим из строк в целые числа }
  m:=strtoint(ms); { Функция strtoint определена в стандартном модуле sysutils }
  y:=strtoint(ys);
  if (m>=1) and (m<=12) and (d>=1) and (d<=mday[m]) or { обычная дата или }
     (y>0) and (y mod 4=0) and (m=2) and (d=29) then { 29 февраля високосного года }
  begin
    newdate:=ds+'/'+ms+'/'+ys;
    fl:=true; { Проверяем на дубли }
    for i:=1 to k do
      if newdate=dates[i] then 
        fl:=false;
    if fl then { Дата не дублируется }
    begin { добавляем её в массив dates }
      inc(k);
      dates[k]:=newdate;
    end;
  end;
end;
begin
  readln(s);
  a:=copy(s,1,2); { Выделяем числа }
  b:=copy(s,4,2);
  c:=copy(s,7,2);
  k:=0;
  check(a,b,c); { 6 перестановок }
  check(a,c,b);
  check(b,a,c);
  check(b,c,a);
  check(c,a,b);
  check(c,b,a);
  if k=0 then
    writeln('No such date')
  else
    for i:=1 to k do
      writeln(dates[i]);
end.

Разбор задачи D. Пизанская башня

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

n	1	2	3	4	5
кол-во ходов `m`	1	3	5	9	15

var n,i:integer;
  m:array[1..40]of int64;
begin
  read(n);
  m[1]:=1;
  m[2]:=3;
  for i:=1 to n do
    m[i]:=m[i-2]+m[i-1]+1;
  writeln(m[n]);
end.

var n:integer;
  _nmoves:array[1..40,1..3,1..3] of int64; { для запоминания результата }
function nmoves(n,a,b:integer):int64;
begin
  if _nmoves[n,a,b]=0 then
    if (n=1) or (a=2) then
      _nmoves[n,a,b]:=1
    else
      _nmoves[n,a,b]:=nmoves(n-1,a,6-a-b)+1+nmoves(n-1,6-a-b,b);
  nmoves:=_nmoves[n,a,b]
end;
begin
  read(n);
  writeln(nmoves(n,1,3));
end.

Разбор задачи I. Гири

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

Разбор задачи G. Шпаги

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

type info= 
  record 
    age:integer; { возраст }
    ind:integer; { номер шпаги в исходной последовательности }
  end;
var o:array[1..100000] of info;
  t:info;
  p:array[1..100000] of integer;
  ai,n,k,i:integer;

procedure qsort(l,r:integer);
var i,j,m:integer;
begin
  if l>=r then  exit;
  m:=o[l+random(r-l+1)].age;
  i:=l;
  j:=r;
  while i<=j do
  begin
    while o[i].age>m  do  inc (i);
    while o[j].age<m  do  dec (j);
    if i<=j then
    begin 
      t:=o[i];o[i]:=o[j];o[j]:=t; 
      inc(i); dec(j); 
    end;
  end;
  qsort(l,j);
  qsort(i,r);
end;
begin
  read(n,k);
  for i:=1 to n do
  begin
    read(ai);
    o[i].age:=ai;
    o[i].ind:=i;
  end;
  qsort(1,n);
  ...
end.

p[o[1].ind]:=0; { у самой старой шпаги нет предка }
for i:=2 to n do
begin
  if o[i div 2].age-o[i].age<k then
  begin { неудача }
    writeln(-1);
    halt;
  end;
  p[o[i].ind]:=o[i div 2].ind;
end;
{ выводим ответ }
for i:=1 to n do
  write(' ',p[i]);

Разбор задачи E. Печать

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

Постановка задачи
Есть набор картриджей с параметрами: стоимость и количество страниц, которое может напечатать.
Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно `k` страниц.

Решение
Нам имеет смысл рассматривать не более 200 картриджей
Картридж, у которого отношение стоимости к количеству напечатанных страниц максимально, имеет номер `"opt"`
Картридж с максимальным количеством страниц имеет номер `max`
Выгодно брать картридж `"opt"`, до тех пор когда количество страниц не станет меньше `p_max*p_"opt"`
А для количества страниц до `p_max*p_"opt"` решим стандартную задачу о рюкзаке

Обоснование
Имеет смысл считать только до `p_max*p_"opt"`, так как мы можем получить почти все остатки от деления на `p_"opt"`, не превышая `p_max*p_"opt"`. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.

Автор разбора: Аксёнов Виталий, СПбГУ ИТМО

Разбор задачи F. Квадродерево

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

Постановка задачи
Дано квадродерево на таблице из 0 и 1
Найти минимальное число вершин, которое может остаться, при изменении не более, чем `k` ячеек

Решение
Посчитаем динамику на полном квадродереве, то есть в каждой вершине посчитаем – какое минимальное количество ячеек нужно изменить, чтобы в квадродереве с корнем в этой вершине было ровно `m` вершин

Обоснование
Если таблица имеет размер `n*n` – то количество вершин в квадродереве `O(n^2)`
Каждая такая вершина "пересчитывается" за `O(n^4)`
`T(n)\ =\ O(n^4)\ +\ 4T(n/4)\ =\ O(n^4)`
Итого: `O(n^4)` – время работы программы

Автор разбора: Аксёнов Виталий, СПбГУ ИТМО

Разбор задачи H. Светофор

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

Постановка задачи
Даны 2 односторонние дороги, по которым машины едут к центру
У машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость
Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально

Решение
Для каждой машины надо найти время, когда она доедет до перекрёстка
Это время равно максимуму из её времени "без торможения" и из времен приезда машин, которые находятся ближе к перекрёстку
"Нужные отрезки" – `(k(r+g)+g,\ (k+1)(r+g))` для первой и `(k(r+g),\ k(r+g)+g)` для второй прямой
"Разобьём" время на блоки по `x`
Нам нужно найти такое `g`, что максимум из количества машин на "нужных" отрезках была минимальной
Каждая машина принадлежит какому-то блоку
Возьмём все времена по модулю `x` и отсортируем, а далее воспользуемся методом сканирующей прямой
Изначально, `g\ =\ 0`
2 события:
- Машина с первой прямой успевает на зелёный
- Машина со второй прямой теперь не успевает на зелёный
Для каждой машины мы знаем блок, которому она принадлежит
При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков

Автор разбора: Павел Кунявский, СПбГУ ИТМО