           Белорусская олимпиада школьников по информатике.
                 Витебск, 28 марта - 1 апреля, 1994.
                             Первый день.

                             1. Карточки.
     Есть N  карточек.  На  каждой из них черными чернилами написан ее
уникальный номер - число от 1 до N.  Также на каждой карточке красными
чернилами написано еще одно целое число,  лежащее в промежутке от 1 до
N (некоторыми одинаковыми "красными" числами могут помечаться несколь-
ко карточек).
     Например, N=5, 5 карточек помечены следующим образом:
                      ┌──┬──┬──┬──┬──┐
     "черное" число   │ 1│ 2│ 3│ 4│ 5│
                      ├──┼──┼──┼──┼──┤
     "красное" число  │ 3│ 3│ 2│ 4│ 2│
                      └──┴──┴──┴──┴──┘
     Необходимо выбрать из данных N карточек максимальное число карто-
чек  таким образом,  чтобы множества "красных" и "черных" чисел на них
совпадали.
     Для примера выше это будут карточки с "черными" номерами 2,  3, 4
(множество красных  номеров,  как  и  требуется  в  задаче,  то  же  -
{2,3,4}).
     ВВОД:
          <N=> N, N<=50
          <"Черный" номер 1, "красный" -> "красное"_число_1
                              ......
          <"Черный" номер N, "красный" -> "красное"_число_N
     ВЫВОД:
          <В выбранном множестве элементов> количество_элементов S
          <"Черные" номера выбранных карточек> a1, ..., aS

                              2. Арбузы.
     В ряд лежат N арбузов,  пронумерованных от 1 до N.  Нам известно,
что:
     1) массы первого и N-го арбузов m(1) и m(N) соответственно;
     2) масса  i-го  арбуза m(i) есть среднее арифметическое масс двух
соседних арбузов, увеличенное на d:
                      m(i)=d+(m(i-1)+m(i+1))/2;
     По введенным m(1), m(N), N, d и j найти m(j).
     Ограничение: N<200.
     Необходимо, в рамках формулировки задачи,  предусмотреть проверку
корректности данных программы.

                          3. Удалите цифры.
     Вводятся N и s.
     Задано натуральное число N из K>s цифр (K не вводится). Составить
алгоритм,  определяющий,  какие s цифр удалить, чтобы оставшиеся цифры
составили  наименьшее число.  Выдать в порядке возрастания номера уда-
ленных цифр. Цифры пронумерованы слева направо, нумерация начинается с
единицы.
     Пример. N=2435, s=1. Если удалить вторую цифру (4), получим число
235. Это и есть наименьшее число (остальные: 435,245,243).
     Число N представляется следующим образом:
     Задается количество  строк ввода p,  в каждой строке по два числа
ai и bi,  ai<=60000, bi состоит из не более чем 60 цифр. ai указывает,
сколько раз в числе встречается группа цифр bi. p<30.
     N=(a1) b1 ... (ap) bp.
     Например, если
      p=3
      a1=3  b1=123
      a1=1  b1=0
      a1=2  b1=09
     то N=12312312300909
.
           Белорусская олимпиада школьников по информатике.
                 Витебск, 28 марта - 1 апреля, 1994.
                             Второй день.

               1. Знаменитость (Теоретическая задача).
     Пусть группа  состоит из N человек.  Назовем одного из этих людей
знаменитостью, если он не знает никого из оставшихся, а его знают все.
Задача состоит в том, чтобы в этой группе определить знаменитость (ес-
ли она там есть).  При этом разрешается задавать только  вопросы  вида
"Извините,  знаете ли Вы вон того человека?". (Предполагается, что все
ответы правдивы,  и что даже знаменитость ответит на  поставленный  ей
вопрос).
     Найти минимальное необходимое число вопросов,  которое  надо  за-
дать, и описать алгоритм опроса.
     Входные данные:  матрица C[i,j], такая что C[i,j]=1, если i знает
j, и C[i,j]=0 иначе.

                            2. Расписание.
   В нулевой момент времени мастеру одновременно  поступает  N  работ.
Работы  пронумерованы от 1 до N.  Для каждой работы i заранее известно
следующее:
   1) время выполнения работы ti, кратное суткам,
   2) штраф сi за каждые сутки ожидания работы i до момента начала  ее
выполнения.
   Одновременно может выполняться только одна работа,  и  если  мастер
приступает  к выполнению некоторой работы,  то он продолжает выполнять
ее, пока не закончит.
   Таким образом,  суммарный штраф, который надо будет уплатить, выра-
жается следующим образом:
   Штраф равен сумме сi*(время начала выполнения работы i) по всем i.
   Найти такой порядок выполнения работ,  чтобы штраф  оказался  мини-
мальным.
   Ввод:
   <N=> N, N<100,
   <Работа 1: время выполнения t1 и штраф c1> t1, c1
                               ....
   <Работа N: время выполнения tN и штраф cN> tN, cN
   Вывод:
   <Минимальный суммарный штраф=> Штраф
   <Порядок выполнения работ:> номера работ в порядке выполнения

   Пример: N=3
   t1=4    c1=1
   t2=1    c2=1
   t3=10   c3=3
   Минимальный суммарный штраф=14
   Порядок выполнения работ: 2,3,1.

                          3. Прямоугольники.
   Написать программу, отвечающую на вопрос, можно ли из N данных пря-
моугольников Пi размеров (ai,bi), i=1,...,N, сложить один большой пря-
моугольник П размера (a,b).  Нижний левый угол большого прямоугольника
имеет координату (0,0),  стороны параллельны осям координат; маленькие
прямоугольники можно поворачивать,  но так, чтобы их стороны после по-
ворота оставались параллельны осям координат. При составлении П прямо-
угольники Пi могут быть использованы не все.  Прямоугольники Пi не пе-
рекрываются.
   Ограничения: N<8, a,b,ai,bi - целые числа.
   Ответ выдать в виде 'да' - 'нет', и в случае 'да' необходимо выдать
для  каждого прямоугольника Пi,  образующего П,  координату его левого
нижнего и правого верхнего углов и его номер i.
.
         Белорусская олимпиада школьников по информатике.
               Витебск, 28 марта - 1 апреля, 1994.
                     Первый день. Решения.

                           1. Карточки.
     Зададим нумерацию карточек с помощью массива F. Пусть на i-ой
карточке написана  пара:  "черный"  номер  i,  "красный"  -  F[i].
Пусть C[i] - счетчик,  показывающий,  сколько раз число i встреча-
ется среди "красных".
     Если какого-то числа i нет среди "красных" (т.е.  C[i]=0), то
его нет и в искомом множестве.  Следовательно, можно не рассматри-
вать  далее (выбросить) карточку с соответствующим "черным" числом
i (и "красным" F[i]).  Удаляем i из  множества  "черных"  чисел  и
уменьшаем соответствующий счетчик С[F[i]] на 1. Если число C[F[i]]
стало равно 0, то числа C[F[i]] нет среди "красных", и мы можем не
рассматривать далее карточку с "черным" номером C[F[i]], и т.д.

const N1=10;
type mas=array[1..N1] of integer;
var F: mas;
    N,i: integer;

     procedure mapping(F: mas);
     var C: mas;
         j: integer;
         Stack: array [0..N1] of integer;
     begin
        Stack[0]:=0;
        for j:=1 to N do C[j]:=0;
        for j:=1 to N do C[F[j]]:=C[F[j]]+1;
        for j:=1 to N do
           if C[j]=0
           then begin Stack[0]:=Stack[0]+1;
                      Stack[Stack[0]]:=j
                end;
        while  Stack[0]<>0 do { while Stack is not empty }
           begin
             j:=Stack[Stack[0]]; { remove i from the top of Stack }
             Stack[0]:=Stack[0]-1;
             C[F[j]]:=C[F[j]]-1;  { decrease counter }
             if C[F[j]]=0 then begin Stack[0]:=Stack[0]+1;
                                     Stack[Stack[0]]:=F[j]
                               end;
           end;
        for i:=1 to N do
           if C[i]<>0 then writeln(i,' in set');
     end;

begin
 write('N=');  readln(N);
 for i:=1 to N do
  begin
    write('"чеpный" номеp ',i,', "кpасный" -');
    readln(F[i]);
  end;
 mapping(F);
end.
(По материалам журнала "Communications of the ACM")

                       2. Арбузы (С.Волченков).
     В рамках формулировки задачи под корректностью  данных  программы
понимается то,  что вес каждого арбуза m(i) должен быть  положительным
числом. Мы знаем m(1) и m(n). Пусть действительные веса арбузов в ряде
m(i). Будем обозначать текущие вычисляемые массы m'(i). Зададим произ-
вольное m'(2) - вес второго арбуза. Пусть m'(2)-m(2)=s, m'(1)=m(1) и
                     m'(i)=d+(m'(i-1)+m'(i+1))/2,
Тогда, так как
                      m(i)=d+(m(i-1)+m(i+1))/2,
то
                     m(i+1)=-2*d+2*m(i)-m(i-1),
                    m'(i+1)=-2*d+2*m'(i)-m'(i-1),
и
        m'(3)-m(3)=[-2*d+2*m'(2)-m'(1)]-[-2*d+2*m(2)-m(1)]=2s
        m'(4)-m(4)=[-2*d+2*m'(3)-m'(2)]-[-2*d+2*m(3)-m(2)]=3s
                                .....
                          m'(n)-m(n)=(n-1)s.
    Находим разность m'(n)-m(n)=(n-1)s. Вычисляем s.

     3. Удалите цифру (По материалам Молдавской олимпиады).
     Пусть s=1.
     Просматривать число слева направо.  Найти первую такую циф-
ру, за которой идет строго меньшая цифра,  и эту первую  вычерк-
нуть. Если цифры идут монотонно, не убывая, вычеркнуть последнюю.
     Пусть d1 d2 ... dk - десятичная запись числа N. Пусть 1<=i<
<j<=k, Ni и Nj - результаты вычеркивания из N i-й и j-й цифр со-
ответственно. Разобьем десятичную запись чисел Ni и  Nj  на  три
отрезка -  от  1-й  до  (i-1)-й,  от  i-й до (j-1)-й и от j-й до
(k-1)-й цифр.
      1  2 ....   i-1      i    ....   j-1     j   ... k-1
  Ni d1 d2 .... d(i-1)  d(i+1)  ....    dj  d(j+1) ... dk
  Nj d1 d2 .... d(i-1)  di      .... d(j-1) d(j+1) ... dk

     Первый и третий отрезки равны (или отсутствуют),  и резуль-
тат сравнения Ni и Nj при d(i) <> d(i+1) не зависит от j.
     Если s>1, то s раз применяется приведенный выше алгоритм.
     Так как s<10, то имеет смысл хранить и анализировать только
10 текущих цифр.  При этом может удаляться цифра или в  середине
введенной строки, или в конце.
.
                             Тесты.
                            Задача 1
1)
     20
     1)3
     2)2
     3)7
     4)5
     5)11
     6)13
     7)2
     8)1
     9)8
     10)19
     11)17
     12)15
     13)11
     14)10
     15)7
     16)1
     17)2
     18)4
     19)5
     20)17
     ответ: s=1
            {2}
2)
     6
     1)2
     2)3
     3)4
     4)5
     5)1
     6)6
     ответ:s=6
           {1,2,3,4,5,6}
3)
     14
     1)6
     2)5
     3)1
     4)3
     5)4
     6)2
     7)8
     8)10
     9)7
     10)9
     11)3
     12)2
     13)1
     14)9
     ответ:s=10
           {1,2,3,4,5,6,7,8,9,10}

.

                     Задача 2

     m1        mN       N      d      j     ответ
1)   1.0       1.0      21    1.0    15      85.0
2)  30.0     210.0      10   -5.0     8    данные некорректны
3)  40.0      58.0      10   -4.0     2    данные некорректны
4)  40.0    1370.0      20   -5.0    13     460.0
5)   1.0       3.625    22    0.9375 14     100.125
6)  50.0       8.5      84    0.25   59     383.5
7)   1.0       1.0      10    0.0     3       1.0

               ТЕСТЫ К ЗАДАЧЕ N 3
     Порядок ввода: р
                    а(1) b(1)
                    a(2) b(2)
                    .........
                    a(p) b(p)
                    s
     замечание: при правильных числовых ответах помечать-
                есть ли вывод не по возрастанию номеров

1)
     2
     2 1234
     1 9
     5
     ответ: 2 3 4 8 9
2)
     4
     10000 111111111111111  (по 15 цифр)
     60000 22
     2     9
     10    00001
     3
     ответ: 1)из [150001 - 270000]
            2)270001
            3)270002

3)
     9
     50000 111111111111111  (по 15 цифр)
     50000 222222222222222
     .....................
     50000 999999999999999
     4
     ответ: 1)из [6000001 - 6750000]
            2)из [6000001 - 6750000]
            3)из [6000001 - 6750000]
            4)из [6000001 - 6750000]

4)
     2
     2 01
     1 02
     3
     ответ: 2 4 6
.
                     Второй день. Решения.
               1. Знаменитость (Теоретическая задача).
     Если мы спрашиваем человека А,  знает ли он человека B, и от-
вет - "Да", то A - не знаменитость, если же "Нет", то тогда B - не
знаменитость.  Одним вопросом мы исключаем из дальнейшего рассмот-
рения  одного человека.  Когда,  после N-1 вопроса,  остается один
единственный человек, мы должны сделать проверку, действительно ли
он он знаменитость, (то есть он не знает никого, а его знают все -
это еще (N-1) вопрос).  Необходимость  проверки  можно  обосновать
следующим примером:
     1 знает 2, 2 знает 3, 3 знает 1.

                            2. Pасписание.
     Пусть имеется оптимальное расписание,  в котором номера выполняе-
мых работ совпадают с порядковыми номерами работ. Тогда этому расписа-
нию будет соответствовать минимальное значение штрафа. Всякая переста-
новка в порядке выполнения двух или более работ уже не может  привести
к уменьшению штрафа, поэтому, переставив местами работы с номерами k и
k+1, мы получим штраф не меньше.
     Обозначим через l(i) время начала выполнения работы i.
     С учетом представления штрафа это можно записать так
 k-1                                          n
 SUM c(i)*l(i) + c(k)*l(k) + c(k+1)*l(k+1) + SUM  c(i)*l(i) <=
 i=1                                        i=k+2
       k-1                                            n
   <=  SUM c(i)*l(i) + c(k+1)*l'(k+1) + c(k)*l'(k) + SUM  c(i)*l(i).
       i=1                                          i=k+2

     Здесь l'(k+1) и l'(k) - время  начала  выполнения  соответственно
(k+1)-й и  k-й  работы после перестановки.  Заметим,  что k-я работа в
обоих расписаниях выполнятся после того, как будут выполнены предшест-
вующие k-1 работы, поэтому
  l(k)=l'(k+1), l(k+1)=l(k)+t(k), l'(k)=l'(k+1)+t(k+1)=l(k)+t(k+1).
     В результате получаем:
    с(k)l(k) + c(k+1)(l(k)+t(k)) <= c(k+1)l(k) + c(k)(l(k)+t(k+1))
                       c(k+1)t(k) <= c(k)t(k+1)
                      t(k)/c(k) <= t(k+1)/c(k+1).
     Алгоритм:
     1) Для всех работ вычислить отношение t(i)/c(i);
     2) Упорядочить работы по возрастанию этого отношения.

                          3. Прямоугольники.
     Каждый Пi можно положить либо  горизонтально,  либо  вертикально.
Будем заполнять П от нижнего левого угла.
     На каждом шаге мы
     1) будем  искать  в  уже заполненной фигуре "нишу" с минимальными
координатами левого нижнего угла;
     2) для каждого из еще не использованных Пi повторить
            брать очередной Пi и пытаться вставить в "нишу"
            если удалось, и мы не вышли за пределы П,
            то
               пометить Пi как испольнованный
               на шаг 1
              scratch:
               пометить Пi как неиспольнованный
            конец то
         конец для
         если использовали все Пi, то печать результата. Стоп.
         если не использован ни один Пi, то решения нет.
                                         иначе возврат на scratch
.
                             Тесты.
                             Задача 2

   t        c

1) 5
   1,       0
   2,       1
   3,       1
   4,       1
   5,       1

ответ  16
   2, 3, 4, 5, 1

2)4
  1,        1
  0,        5
  1,        2
  1,        3

ответ  4
  2, 4, 3, 1

3)4
  1,        1
  100,    100
  3,        6
  4,        6

ответ 825
  3, 4, 1, 2       или   3, 4, 2, 1

4)8
  999,    998
  99,      98
  98,      97
  95,      96
  94,      95
  94,      93
  2,        1
  99,       0

ответ 569193
  5, 4, 1, 2, 3, 6, 7, 8

                              Задача 3.
#     N       П         Пi      Ответ
1)    7    200,400    100,500    нет
                      200,800
                      250,350
                      350,250
                      400,400
                      201,201
                      1,1000

2)    6    10,2       1,1    нет
                      1,1
                      1,1
                      1,1
                      1,1
                      1,1

3)    4    400,300               да, П3=400,300
                      205,9
                      25,22
                      300,400
                      290,799

4)    3    500,300    200,400    нет
                      300,200
                      100,100
                                       ┌─────┬─────┐
5)    7    1200,1000  600,400    да    │     │     │
                      600,400          ├───┬─┴─┬───┤
                      600,400          │   │   │   │
                      600,400          │   │   │   │
                      400,600          └───┴───┴───┘
                      400,600
                      400,600

                                        100   500
6)    6    600,500    100,400    да    ┌─┬──────────┐ 100
                      100,500          │ ├───┬──────┤
                      200,300    400   │ │   │      │ 200
                      200,300          │ │   ├──────┤
                      200,300          ├─┴───┤      │ 200
                      100,300    100   └─────┴──────┘
                                         300   300
7)    6    400,700    600,300    нет
                      200,500
                      100,500
                      100,500
                      200,200
                      300,200
