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

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

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

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

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

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. Резервное копирование

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. Ксилофон

Разбор задачи K. Очистка озера

var q:array[1..10000] of record i,j:integer; end;
  dist:array[1..2,1..100,1..100] of integer;
  map:array[1..100] of string;
  q1,q2,n,m,r,c,d,e:longint;
{ выполнение хода в клетку (r,c), её достигли за di шагов из начальной позиции }
procedure move2(d,r,c,di:integer);
begin
  if (r<1) or (r>n) or (c<1) or (c>m) then {нельзя} exit;
  if map[r][c]='#' then {нельзя} exit;
  if dist[d,r,c]>=0 then {уже были} exit;
  dist[d,r,c]:=di;
  { добавляем в очередь }
  q[q2].i:=r;
  q[q2].j:=c;
  inc(q2);
end;
procedure flood(r,c,d:integer);
var i,j,di:integer;
begin
  for i:=1 to n do
    for j:=1 to m do
      dist[d,i,j]:=-1; { отмечаем, что не были }
  q1:=1; { очередь пуста }
  q2:=1;
  move2(d,r,c,0); { помещаем в очередь стартовую позицию }
  while q1<q2 do { очередь не пуста }
  begin
    { берем первое значение из очереди }
    i:=q[q1].i;
    j:=q[q1].j;
    inc(q1);
    di:=dist[d,i,j]+1;
    { ходим во всех возможных направлениях }
    move2(d,i+1,j,di);
    move2(d,i-1,j,di);
    move2(d,i,j+1,di);
    move2(d,i,j-1,di);
  end;
end;
...
  flood(d,e,1);
  flood(r,c,2);

• робот не может дойти до подъемника (т.е. `"dist"[1,r,c]\ <\ 0`);
  
• все клетки, в которые может попасть робот, пусты, кроме клетки с подъемником.

Разбор задачи H. Сдача

• 0 монет номиналом `b_j`: способ сдать сумму `i` монетами номиналом `b_1,\ …,\ b_{j-1}`;
  
• 1 монета номиналом `b_j`: `b_j\ +` способ сдать сумму `i-b_j` монетами номиналом `b_1,\ …,\ b_{j-1}`;
  
• …
  
• `k=\ ⌊\ i//b_j\ ⌋` монет номиналом `b_j`: `k*b_j\ +` способ сдать сумму `i-k*b_j` монетами номиналом `b_1,\ …,\ b_{j-1}`.

const mysize=25;
type mylong=array[1..mysize] of integer;
{ сложение длинных целых чисел }
procedure add(var a,b:mylong);
var i,p:integer;
begin
  p:=0; { перенос }
  for i:=1 to mysize do
  begin
    p:=p+a[i]+b[i];
    b[i]:=p mod 10;
    p:=p div 10;
  end;
end;
{ вывод длинных целых чисел }
procedure print(var a:mylong);
var i:integer;
    flg:boolean;
begin
  flg:=false; { была ненулевая цифра? }
  for i:=mysize downto 1 do
  begin
    if a[i]<>0 then
      flg:=true;
    if flg or (i=1) then
      write(a[i]);
  end;
end;

var T:array[0..10000] of mylong;
    b:array[1..10] of integer;
    i,j,n,s:integer;
...
  read(s,n);
  for i:=1 to n do
    read(b[i]);
  T[0][1]:=1;
  for j:=1 to n do
    for i:=b[j] to s do
      add(T[i-b[j]],T[i]);
  print(T[s]);

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

Известный российский математик Я.И.Перельман в своей книге «Занимательная арифметика» описал русский народный способ умножения. Сущность его в том, что умножение двух чисел сводится к ряду последовательных делений одного числа пополам при одновременном удвоении другого числа. Например: нужно умножить 32 на 13. Это записывается таким образом:

`32*13`

`16*26`

`8*52`

`4*104`

`2*208`

`1*416`

Деление пополам продолжают до тех пор, пока в частном не получится 1, параллельно удваивая другое число. Последнее удвоенное число и дает искомый результат. Способ основан на том, что произведение не изменяется, если один множитель уменьшить вдвое, а другой вдвое же увеличить. А в результате многократного повторения этой операции получается искомое произведение: `32*13\ =\ 1*416`.

Если приходится делить нечетное число пополам, то в этом случае от нечетного числа откидывается единица и остаток уже делится пополам; но зато к последнему числу правого столбца нужно будет прибавить все те числа этого столбца, которые стоят против нечетных чисел левого столбца: сумма и будет искомым произведением. Практически это делают так, что все строки с четными левыми числами зачеркивают; остаются только те, которые содержат налево нечетное число. Пример:

`19*17`

`9*34`

`4*68`

`2*136`

`1*272`

Сложив незачеркнутые числа, получаем правильный результат: `17\ +\ 34\ +\ 272\ =\ 323`.

Обоснованность приема станет ясна, если принять во внимание, что

`19*17\ =\ (18\ +\ 1)*17\ =\ 18*17\ +\ 17`

`9*34\ =\ (8\ +\ 1)*34\ =\ 8*34\ +\ 34`, и так далее.

Ясно, что числа 17, 34 и т.п., утрачиваемые при делении нечетного числа пополам, необходимо прибавить к результату последнего умножения, чтобы получить произведение.

У некоторых английских авторов этот способ умножения описывается под названием «русский крестьянский способ». В Германии крестьяне также пользуются им и называют его «русским».

Не исключено, что этот способ дошел до нас из Египта. Одним из основных источников сведений о древнеегипетской математике является папирус, купленный в Луксоре шотландским антикваром Александром Генри Риндом, который сейчас хранится в Британском музее. Папирус был найден в металлическом футляре. В развернутом виде имеет 5.5 м длины при 32 см ширины. Он представляет собой собрание решений 84 задач, имеющих прикладной характер. Папирус относится примерно к 2000-1700 г. до н.э. и представляет собой копию еще более древней рукописи, переписанную писцом Ахмесом. В папирусе используется иератическая система обозначений чисел – условные знаки, которые произошли из иероглифов в результате упрощений и стилизации. В нем есть четыре примера умножения, выполненные по способу, живо напоминающему наш народный русский способ. Вот один из них:

Что означает следующее:

  9 1 /

18 2

36 4

72 8 /

= 81

Косая черта справа от строки указывает на то, что левое число будет добавлено к результату. Из этого примера видно, что египтяне пользовались приемом умножения, довольно сходным с нашим народным.

function powModM(A:int64; P:longint):longint;
var R:int64;
begin
  R:=1;
  while p>0 do
  begin
    if P mod 2=1 then
      R:=(R*A) mod M;
    A:=(A*A) mod M;
    P:=P div 2;
  end;
  powModM:=R;
end;

var i,j,A0,B,P,N,M:longint;
    step,A:array[0..100000] of longint;
...
  for i:=0 to M-1 do
    step[i]:=-1;
  i:=0;
  A[0]:=A0 mod M;
  while (i<N) and (step[A[i]]<0) do
  begin
    step[A[i]]:=i;
    A[i+1]:=(powModM(A[i],P)+B) mod M;
    inc(i);
  end;
  if i<N then
  begin
    j:=step[A[i]];
    i:=(N-j) mod (i-j) + j;
  end;
  writeln(A[i]);

  A[0]:=A0 mod M;
  for i:=1 to M do
    A[i]:=(powModM(A[i-1],P)+B) mod M;
  if N<=M then
    writeln(A[N])
  else
  begin
    j:=M-1;
    while A[j]<>A[M] do
      dec(j);
    writeln(A[(N-j) mod (M-j) + j]);
  end;

Разбор задачи E. Сигнальная система

и

• Отрезок `(x,y_3)-(x,y_4)` находится за пределами полосы, где находится отрезок `(x_1,y_1)-(x_2,y_2)`, т.е. `x\ <\ x_1` или `x\ >\ x_2`. Отрезки не пересекаются.
  
• Отрезок `(x_1,y_1)-(x_2,y_2)` также является вертикальным, т.е. `x_1\ =\ x_2\ =\ x`. Тогда отрезки пересекаются, если `y_4\ ≥\ y_1` и `y_3\ ≤\ y_2`.
  
• Отрезок `(x,y_3)-(x,y_4)` находится в полосе, где находится отрезок `(x_1,y_1)-(x_2,y_2)`. Используя подобие треугольников, найдем на отрезке `(x_1,y_1)-(x_2,y_2)` точку с абсциссой `x`: `y\ =\ y_1\ +\ {(y_2-y_1)*(x-x_1)}/{x_2-x_1}`. Отрезки пересекаются, если `y_3\ ≤\ y` и `y\ ≤\ y_4`. Чтобы избавиться от погрешностей вычислений, можно домножить все ординаты на `x_2-x_1` и проверять условие `y_3*(x_2-x_1)\ ≤\ y_1*(x_2-x_1)\ +\ (y_2-y_1)*(x-x_1)\ ≤\ y_4*(x_2-x_1)`.

procedure swap(var a,b:longint);
var t:longint;
begin
  t:=a;
  a:=b;
  b:=t;
end;
function iscross(x1,y1,x2,y2,x,y3,y4:longint):boolean;
var y:longint;
begin
  if x1>x2 then
  begin
    swap(x1,x2);
    swap(y1,y2);
  end;
  if y3>y4 then
    swap(y3,y4);
  if (x<x1) or (x>x2) then
  begin { 1 случай }
    iscross:=false;
    exit;
  end;
  if x1=x2 then
  begin { 2 случай }
    if y1>y2 then
      swap(y1,y2);
    iscross:=(y4>=y1) and (y3<=y2);
    exit;
  end;
  { 3 случай }
  y:=y1*(x2-x1)+(y2-y1)*(x-x1);
  iscross:=(y3*(x2-x1)<=y) and (y<=y4*(x2-x1));
end;

const inf:extended=1e100;
var dist:array[1..102,1..102] of extended;
    can:array[1..102,1..102] of boolean;
...
{ составление матрицы с расстояниями }
  for i:=1 to n2 do
  begin
    for j:=i to n2 do
    begin
      can[i,j]:=canlight(i,j);
      if can[i,j] then
        dist[i,j]:=1e6+sqrt(sqr(point[i].x-point[j].x)+sqr(point[i].y-point[j].y))
      else
        dist[i,j]:=inf;
      can[j,i]:=can[i,j];
      dist[j,i]:=dist[i,j];
    end;
  end;
{ поиск кратчайших путей между всеми парами вершин }
  for k:=1 to n2 do
    for i:=1 to n2 do
      for j:=1 to n2 do
        if dist[i,k]+dist[k,j]<dist[i,j] then
           dist[i,j]:=dist[i,k]+dist[k,j];

Разбор задачи J. Пластинки

• Одиночная пластинка или несколько пластинок стопкой. Нужно проверить центр круга `(X_i,Y_i)`. Количество точек такого типа равно `N`.
  
• Одна пластинка накладывается на другую, при этом центр другой пластинки невидим. Нужно проверить точку, которая находится на расстоянии `R+ε` от центра первой пластинки по направлению к центру другой пластинки. Для нахождения координат точки нужно "масштабировать" вектор, соединяющий центры кругов – привести его к единичному, поделив обе координаты вектора на его длину, затем умножить координаты на новую длину. Координаты точки будут равны `(X_i+(X_j-X_i)*(R+ε)/D_{ij},\ Y_i+(Y_j-Y_i)*(R+ε)/D_{ij})`, где `j<i`, `D_{ij}` – расстояние между центрами пластинок `i` и `j`, `0\ <\ D_{ij}\ ≤\ R`, `ε=10^{-6}`. Количество точек такого типа не превышает `N*(N-1)/2`.
  
• Пластинку накрывает две или больше пластинок. Видимая часть накрытой пластинки представляет собой "многоугольник", образованный дугами краев накрывающих пластинок и, возможно, края самой пластинки. Нужно проверить 2 точки, лежащие на расстоянии `ε` от двух точек пересечения краев накрывающих пластинок. Для нахождения координат точек выполняем поворот на `90°` и `-90°` и масштабирование вектора, соединяющий центры кругов. Расстояние `P` от точек пересечения до середины отрезка, соединяющего центры кругов, равно `sqrt(R^2\ -\ D_{ij}^2/4)`. Середина отрезка между центрами кругов имеет координаты `((X_j+X_i)/2,\ (Y_j+Y_i)/2)`. Координаты точек равны `((X_j+X_i)/2\ -\ (Y_j-Y_i)*(P+ε)/D_{ij},\ (Y_j+Y_i)/2\ +\ (X_j-X_i)*(P+ε)/D_{ij})` и `((X_j+X_i)/2\ +\ (Y_j-Y_i)*(P+ε)/D_{ij},\ (Y_j+Y_i)/2\ -\ (X_j-X_i)*(P+ε)/D_{ij})`, где `j<i`, `0\ <\ D_{ij}\ ≤\ 2*R`, `ε=10^{-6}`. Количество точек такого типа не превышает `N*(N-1)`.