Вы - -й посетитель этой странички 

Решение задач XIII международной олимпиады

Е.В. Андреева

Москва

Продолжение. Начало см. в № 37/2001

Игра ioiwari

· Если в руке игрока более одной бусинки, тогда если текущая лунка уже содержит 5 бусинок, то игрок вынимает из нее одну бусинку и перемещает в свой банк; если же в текущей лунке менее пяти бусинок, тоигрок помещает в нее одну бусинку из своей руки.

· Если же в руке игрока ровно одна бусинка, тогда если текущая лунка содержит от одной до четырех бусинок, то все бусинки из этой лунки и единственная бусинка из руки игрока помещаются в его банк; впротивном случае (то есть текущая лунка содержит 0 или 5 бусинок), бусинка из руки игрока перемещается в банк противника.

Ваша программа читает входные данные из стандартного потока ввода и пишет выходные данные в стандартный поток вывода. Ваша программа играет за первого игрока, а противник — за второго. В начале работы ваша программа должна считать строку из 7 целых чисел p 1 , …, p 7 : начальное количество бусинок в лунках с номерами 1, …, 7 соответственно ( лунки пронумерованы от 1 до 7 по часовой стрелке).

Вам дана программа ( IOIWARI2. EXE ), которая для одной конкретной начальной ситуации играет за второго игрока оптимальным образом. В первую строку стандартного потока вывода эта программа выводит данные,описывающие начальное распределение бусинок по лункам, которое должна считать ваша программа в начале своей работы:

    4 3 2 4 2 3 2

В приведенных ниже примерах переменная mymoveсодержит ваш ход, а переменная last — ход противника. Если программа на C++ использует iostreams, вы должны организовать ввод и вывод следующим образом:

cin>>last;

Если программа на Cи или C++ использует scanf и printf, вы должны организовать ввод и вывод следующим образом:

printf("%d\n",mymove); fflush (stdout);scanf ("%d", &last);

Если ваша программа на Паскале, вы должны организовать ввод и вывод следующим образом:

Writeln(mymove);Readln(last);

П р и м е р

Ниже приведено корректное описание 6 ходов и содержимое лунок и банков игроков после каждого хода.

Баллы

Здесь Move ( B, i ) обозначает состояние доски, которое получится в результате выбора для начала хода ячейки  i, а D ( B , i ) — разницу между количеством бусинок, помещенных в банк первого и второго игрока соответственно в результате такого хода, максимум и минимум определяются для всех возможных значений i. Очевидно, что выигрышная стратегия для первого игрока в игре, начинающейся в состоянии доски B, существует, если Diff ( 1, B ) > 0.

Рекурсивная формула для Diff, приведенная выше,  конечно же, решает задачу: первый игрок всегда должен ходить с той лунки i , на которой достигается значение максимума в этой формуле. Однако очевидно, что этот алгоритм эффективно реализовать затруднительно, так как при рекурсивной же его реализации неоднократно будут перевычисляться значения функции для одних и тех же состояний игры и в большинстве случаев его выполнение занимает неоправданно много времени.

Сделать данный алгоритм эффективным можно, если запоминать уже вычисленные значения Diff ( w, B ). Для этого каждому состоянию игрового поля нужно присвоить свой порядковый номер. Так как в ходе любой игрыв каждой лунке будет находиться не более 5 бусинок, следовательно, каждое состояние доски может быть обозначено семизначным числом в шестеричной системе счисления. Максимальным среди таких чисел является 5555555 ₆ = 279935 ₁₀ , а для хранения полученной информации о каждом состоянии доски требуется 3 байта, следовательно, для запоминания информации обо всех возможных ситуациях потребуется 3 • 279935 = 839805 то есть менее одного мегабайта памяти. Так как все возможные состояния игры известны заранее, значения для данной таблицы можно было сосчитать заранее и включить их в текст программы. В этом случае хранить можно только номер лунки. Временная сложность алгоритма пропорциональна числу ребер в графе. В самом худшем случае это число не превышает 7 • 279935.

Twofive

Секретные сообщения между Санта-Клаусом и его маленькими помощниками обычно кодируются так называемым 25-языком. В этом языке используется 25-алфавит, который совпадает с латинским алфавитом с одним исключением — в нем отсутствует буква Z ' , то есть 25-алфавит содержит 25 латинских букв от        ' A ' до ' Y ' в том же порядке, что и латинский алфавит. Каждое слово в 25-языке состоит ровно из 25 различных букв. Слово записывается в таблице размера 5 x 5, строказа строкой. Например, слово

будет записано так:

Правильным словом 25-языка считается слово, буквы которого в каждой строке и каждом столбце расположены по возрастанию их номера в алфавите. Поэтому слово ADJPTBEKQUCGLRVFINSWHMOXY
является правильным словом, а слово
ADJPTBEGQUCKLRVFINSWHMOXY
— нет (возрастающий порядок нарушается во втором и третьем столбцах).

Лексикон Санта-Клауса состоит из всех правильных слов 25-языка. Слова расположены в возрастающем лексикографическом порядке и пронумерованы, начиная с единицы. Например, в лексиконе Санта-Клауса слово ABCDEFGHIJKLMNOPQRSTUVWXY имеет номер 1, а слово ABCDEFGHIJKLMNOPQRSUTVWXY имеет номер 2. Во втором слове, по сравнению с первым, буквы ' U '   и ' Т ' поменялись местами. К сожалению, лексикон Санта-Клауса огромен. Напишите программу, которая определяет порядковый номер по заданному слову из лексикона Санта-Клауса, а по заданному порядковому номеру определяет соответствующее слово. В лексиконе Санта-Клауса не больше 2 ³¹ слов.

Ввод

Входной файл имеет имя  TWOFIVE. IN  и состоит издвух строк. Первая строка содержит один из символов  ' W   '  или ' N   '. Если первая строка содержит ' W  ' , тогда вторая строка содержит правильное слово 25-языка, тоесть строку из 25 символов. Если первая строка содержит ' N ', то вторая строка содержит  порядковый номер существующего слова 25-языка.

TWOFIVE.IN                  TWOFIVE.OUT

W                                    2

ABCDEFGHIJKLMNOPQRSUTVWXY

N                              ABCDEFGHIJKLMNOPQRSUTVWXY

Решение

Задача решается методом динамического программирования. Решение основано на функции calcstate, которая для любого набора уже правильно размещенных на определенных местах букв подсчитывает количество возможных размещений оставшихся букв. Она сначала пытается разместить первую по алфавиту из оставшихся букв во все допустимые места ( очевидно, чтопомещать букву следует только в такие места матрицы, выше и левее которых не остается свободных клеток ), рекурсивно вызывает себя же для каждой из таких конфигураций и суммирует получаемые при этом значения. Промежуточные результаты при этом сохраняются в массиве snum, размер которого равен 6 ⁵ , и соответствует количеству возможных конфигураций частичного заполнения матрицы буквами ( в каждой из пяти строкможет стоять от нуля до пяти букв, что и определяет нетолько размер, но и номер каждой из конфигураций ), и, следовательно,  дважды не пересчитываются, что и обеспечивает скорость работы программы.

С помощью такой функции требуемую задачу решить несложно. Пусть, например, мы должны вычислить номер слова. Сначала пропустим и зафиксируем те буквы слова, которые не нарушают в своем следовании ( построчно сверху вниз, а в каждой строке — слева направо ) алфавитного порядка. На место же, в котором порядок нарушается, сначала поставим первую по алфавиту букву из оставшихся и подсчитаем количество возможных продолжений для такого размещения, затем — следующую по алфавиту букву, добавляя результат к уже имеющемуся числу, и т.д., пока не дойдем до буквы, которая стоит на этом месте на самом деле. Затем ищется следующее нарушение порядка в буквах.

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

const states = 6 * 6 * 6 * 6 * 6;
var reclev : longint;
  snum : array[0..states - 1] of longint;
  state : array[0..5] of longint;
  known, kncol : array[1..25] of longint;
  st : string[30];
  mode : char;
  a: longint;
function calcstate : longint;
  var i,a,b,c : longint;
   begin
     inc(reclev); a := 0;
     for i := 1 to 5 do a := a * 6 + state[i];
      if snum[a] < 0 then
        begin
          b := 0; c := known[reclev];
          if c < 0 then
            begin
            for i := 1 to 5 do
              if state[i - 1] > state[i] then
              begin
                inc(state[i]); inc(b,calcstate);
               dec(state[i])
              end
             end
         else
             if (state[c - 1] > state[c]) and
             (state[c] + 1 = kncol[reclev]) then
              begin
                 inc(state[c]); inc(b,calcstate);
                 dec(state[c])
               end;
               snum[a] := b
         end;
         calcstate := snum[a]; dec(reclev)
      end;

Продолжение следует