Подразделы

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

Дата и время

28/09/2022 07:37:40

Авторизация

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

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

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

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

1. Не имеет смысла стричь какой-либо росток бамбука несколько раз. Высота ростка будет определяться последней стрижкой.
2. Стричь бамбук нужно в последний день соревнований, подрезая все ростки бамбука до высоты `h`. Т.е. требуется не более одной стрижки.
3. Высота `i`-го ростка бамбука в последний день соревнований равна `a_i+b_i*(m-1)`. Эта величина может достигать `10^18`, поэтому для вычислений в языке Pascal нужно использовать тип int64, real, double, extended (long long, double, long double в C/C++).
4. Если какой-то росток в последний день соревнований не дорастет до высоты `h`, то выводим `-1`. Если все ростки будут иметь высоту `h`, то выводим 0, иначе выводим 1.
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.

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

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

В задаче нужно найти число способов разбить строку из цифр длиной `l` (`1\ ≤\ l\ ≤\ 200\ 000`) на две непустые подстроки так, чтобы ни одна подстрока не начиналась с 0 и число, соответствующее первой подстроке, было меньше или равно числу, соответствующего второй подстроке.
Число `x` меньше или равно числу `y`, если в числе `x` меньше цифр, чем в числе `y` или – при равенстве количества цифр – строка из цифр числа `x` лексикографически меньше или равна строке из цифр числа `y`.
Достаточно проверить указанные условия для вариантов длины `m` первой подстроки от 1 до `l/2`. Вторая подстрока будет иметь длину `l-m` и начинаться с символа `m+1`.
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.

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

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

Необходимо рассмотреть `3!\ =\ 6` перестановок 3 чисел в дате и выбрать из них те варианты, которые соответствуют реальной дате.
При проверке нужно учитывать, что 2100 год является невисокосным.
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.

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

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

1 способ: вывод рекуррентной формулы
Вручную для `n` от 1 до 5 находим минимальное количество перекладываний.
n12345
кол-во ходов `m`135915
Далее, видим, что зависимость можно описать формулой `m_i\ =\ m_{i-2}+m_{i-1}+1`.
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.
2 способ: запоминающая функция
Чтобы переложить `n` дисков со столбика `a` на столбик `b`, нужно сначала переложить `n-1` диск на столбик `6-a-b`, затем переложить `n`-й диск на столбик `b`, затем все диски со столбика `6-a-b` на столбик `b`. Чтобы повторно не вычислять результат функции количества перекладываний для некоторого набора аргументов (`n`, `a`, `b`), функция должна запоминать в массиве результаты предыдущих вычислений. Размерность массива для запоминания должна совпадать с количеством аргументов функции и областью определения аргументов.
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.

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

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

1. Гири можно разделить на три набора равного веса, если сумма весов гирь делится на 3, т.е. `(sum_{i=1}^n\ i)\ mod\ 3\ =\ {n*(n+1)}/2\ mod\ 3\ =\ 0`. Легко убедиться, что сумма делится на 3 для `n` равных `3*k` или `3*k+2` и не делится для `n` равных `3*k+1`.
2. Нельзя разделить на три набора менее 4 гирь.
3. Любую группу из 6 последовательных чисел `i+1,\ i+2,\ …,\ i+6` можно разделить на три набора равного веса `{i+1,i+6},{i+2,i+5},{i+3,i+4}`. Поэтому можно выделять из гирь подгруппы по 6 гирь, пока число гирь не станет равно 9 и меньше.
4. Набор из гирь 1,2,3,4,5 можно разделить так {1,4},{2,3},{5}. Набор из гирь 1,2,3,4,5,6 можно разделить так {1,6},{2,5},{3,4}. Набор из гирь 1,2,3,4,5,6,7,8 можно разделить так {4,8},{5,7},{1,2,3,6}. Набор из гирь 1,2,3,4,5,6,7,8,9 можно разделить так {7,8},{6,9},{1,2,3,4,5}.

printРазбор задачи 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.
Пояснения к алгоритму быстрой сортировки можно посмотреть в разборе задачи 50. Закраска прямой. Здесь этот алгоритм модифицирован, чтобы сортировать значения по убыванию.
Затем нужно использовать одно из представлений бинарного дерева. Элементы бинарного дерева хранятся в массиве, при этом `i`-й элемент содержит узел дерева, а элементы с номерами `2*i` и `2*i+1` содержат два потомков этого узла. Соответственно, для `i`-го элемента предком будет элемент с номером `⌊i/2⌋`.
Для построения дерева копирования используем жадный алгоритм и будем рассматривать копии шпаг в порядке убывания возраста и цеплять их в качестве потомков к свободным веткам узлов, соответствующих шпагам наибольшего возраста из возможных. Любой другой способ приведет к уменьшению максимума разницы в возрасте между шпагами и их копиями.
Заполнение уровней бинарного дерева будет идти последовательно, в порядке убывания возраста шпаг. Фактически после сортировки элементы в массиве уже образуют такое дерево. Остается только проверить, что для всех `i` от 2 до `n` выполняется `"age"_{i/2}-"age"_i\ ≥\ k`.
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]);

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

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

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

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

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

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

printРазбор задачи 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)` – время работы программы

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

printРазбор задачи 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 события:
- Машина с первой прямой успевает на зелёный
- Машина со второй прямой теперь не успевает на зелёный
Для каждой машины мы знаем блок, которому она принадлежит
При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков

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