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

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

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

Москва

Продолжение. Cм. № 37, 40

Игра Score

 

Score — это игра для двух игроков. Игровое поле состоит из N точек, пронумерованных от 1 до N, часть из которых соединена стрелками.
Каждая стрелка идет от одной точки к некоторой другой точке. Каждая точка принадлежит одному из двух игроков.
Игрок, которому принадлежит точка, называется ее владельцем. Кроме того, каждой точке приписано некоторое положительное число.
Все приписанные числа различны.
Точка с номером 1 является стартовой.
В начале игры каждый из игроков имеет 0 очков.
Игра состоит в следующем. Будем обозначать буквой С текущую точку, то есть точку, в которой мы находимся в начале хода. В начале игры С является точкой с номером 1 (стартовой). Ход в игре делает владелец С, при этом выполняются следующие операции:
1. Если значение, приписанное С, больше, чем текущее количество очков у владельца С, то значение числа, приписанного С, становится новым количеством очков для владельца С. В противном случае число очков у владельца С остается прежним. Количество очков другого игрока в обоих случаях не меняется.
2. Далее владелец С выбирает по своему усмотрению одну из стрелок, выходящих из текущей точки, и точка, на которую эта стрелка указывает, становится новой текущей. Заметим, что один игрок может сделать подряд несколько ходов.
Игра заканчивается, когда после некоторого хода текущей становится стартовая точка. Победителем считается игрок, который имеет большее количество очков в конце игры. Набор стрелок между точками всегда такой, что из любой точки выходит по крайней мере одна стрелка;
· любая точка Р достижима из стартовой точки, то есть существует такая последовательность стрелок, по которой можно добраться от стартовой точки до Р;
· гарантируется, что игру всегда можно закончить за конечное число ходов.

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

Ввод и вывод

Ваша программа читает входные данные из стандартного потока ввода и записывает выходные данные в стандартный поток вывода. Ваша программа — это Игрок 1, а противник — Игрок 2. Ваша программа начинает свою работу со считывания следующих входных данных из стандартного потока ввода.

Первая строка входных данных содержит одно целое число — количество точек N, 1N1000. Каждая из последующих N строк содержит по N целых чисел (нулей или единиц), описывающих стрелки. Если на игровом поле существует стрелка, направленная от точки i к точке j, то j-е число в i-й строке (из этих N строк) равно 1, в противном случае — 0.

Следующая строка содержит N целых чисел, обозначающих владельцев каждой из N точек. Если точкой i владеет Игрок 1, то i -е число — единица, а если Игрок 2 — то двойка.

Следующая строка содержит N целых чисел, обозначающих значения, приписанные точкам. Если i-е число в этой строке равно j, то i-й точке приписано число j .

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

· если ход делает ваша программа (она является владельцем текущей точки), то она должна вывести в стандартный поток вывода номер точки, в которую следует перейти по выбранной вашей программой стрелке;

· если же ход делает ваш противник, то ваша программа должна считать из стандартного потока ввода номер точки, в которую следует перейти по стрелке, выбранной противником;

· когда текущей станет снова точка с номером 1, программа должна заканчивать свою работу.

Рассмотрим следующий пример для игрового поля, показанного на рис. 1. Точки, изображенные в виде окружностей, принадлежат Игроку 1, а в виде квадратов — Игроку 2. Значения, приписанные точкам, помещены внутрь окружностей или квадратов. Номера точек расположены вне геометрических фигур. Следующие входные и выходные данные описывают игру, сыгранную для изображенного на рис. 1 игрового поля.

STDIN

SDDOUT

Объяснение

4 N
1 0 0 0 Информация о стрелках, выходящих из точки 1
0 0 1 1 Информация о стрелках, выходящих из точки  2
0 0 0 1 Информация о стрелках, выходящих из точки 3
1 0 0 0 Информация о стрелках, выходящих из точки 4
1 1 2 2 Владельцы точек
1 3 4 2 Числа, приписанные точкам
2 Ход Игрока 1
4 Ход Игрока 1
1

Игрок 2 ходит в начальную точку — игра заканчивается.

В результате данной игры Игрок 1 набирает 3 очка, а Игрок 2 — 2 очка. Игрок 1 выиграл.

Указания по написанию программы

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

cin>>target;
cout<<target<<endl<<flush;

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

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

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

readln(target);
writeln(target);

Вспомогательные программные средства

Вам дана программа (SCORE2.EXE), которая читает описание начальных данных из файла с именем SCORE.IN и переписывает их в стандартный поток вывода в форме, в какой их должна считать ваша программа из стандартного потока ввода. После этого программа SCORE2 играет за Игрока 2, читая ходы вашей программы из стандартногопотока ввода и записывая свои ходы, сделанные случайным образом, в стандартный поток вывода. Вы можете запустить вашу программу и программу SCORE2 в отдельных окнах и вручную организовать игру между ними.

Оценка программы

Если ваша программа при тестировании выигрывает, то вы получаете полный балл за тест, в противном случае —0 баллов. При тестировании ваша программа сначала будет играть с другой программой, и на всю игру будет отводиться на 1 секунду больше времени, чем указано во временнЫх ограничениях. Ввод и вывод программ будут записаны в некоторые файлы. Затем ваша программа запускается второй раз, при этом входные данные направляются ей из записанного при первом запуске файла. Ваша программа должна выдать те же самые выходные данные, что и при первом запуске . При втором запуске определяется реальное время работы вашей программы.

Решение

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

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

Приведем процедуру, реализующую этот алгоритм, в результате обращения к которой в массиве play_strategy для каждой точки будем иметь значение наилучшего из нее хода владельца данной точки. Предварительно массивы player1_max и player2_max заполнены так: если владельцем i-й вершины является Игрок 1, то player1_max[i] равно значению этой вершины, а player2_max[i] равно 0, в противном случае — наоборот.

const max = 1000;
type ar = array[1..max] of integer;
var
  owner_of_pos, value_of_pos,
  player1_max, player2_max,
  play_strategy, dfs_numb : ar;
  adj_matr : array[1..max, 1..max] of byte;
  numb_of_pos, dfs_cnt : integer;

procedure search(position : integer);
   var player1_wins, player2_wins : ar;
   i, j, max_score, op_min_score : integer;
   begin
     dfs_numb[position] := dfs_cnt;
     inc(dfs_cnt);
     for i := 1 to numb_of_pos do
       player1_wins[i] := -1;
       player2_wins := player1_wins;
        for i := 1 to numb_of_pos do
          begin {собственно поиск в глубину}
            if (adj_matr[position, i] <> 0) and (position <> i) then
              if dfs_numb[i] = -1 then
            begin
               search(i);
            if player1_max[i] > player2_max[i] then
              player1_wins[i] := player1_max[i]
             else player2_wins[i] := player2_max[i]
          end
     end;
     j := -1; max_score := -1; op_min_score := -1;
     {определяем наилучший ход}
   if owner_of_pos[position] = 1 then
     begin
      for i := 1 to numb_of_pos do
        if player1_wins[i] > max_score then
        begin
          max_score := player1_wins[i]; j := i
         end;
         if j <> -1 then {игрок 1 может выиграть}
    begin
       play_strategy[position] := j;
           player1_max[position] := max_score;
           player2_max[position] := player2_max[j];
         if value_of_pos[position] > max_score then
           player1_max[position] := value_of_pos[position]
          end
         else {Гарантии выигрыша Игрока 1 нет}
      begin
         for i := 1 to numb_of_pos do
             if (player2_wins[i] > -1) and ((op_min_score = -1) or
            (op_min_score > player2_wins[i])) then
         begin
            op_min_score := player2_wins[i]; j := i
         end;
         play_strategy[position] := j;
        player1_max[position] := player1_max[j];
        player2_max[position] := op_min_score;
          if value_of_pos[position] > player1_max[position] then
           player1_max[position] := value_of_pos[position]
          end
        end
        else {Владелец текущей позиции - Игрок 2}
        begin
              for i := 1 to numb_of_pos do
                  if player2_wins[i] > max_score then
                begin
                    max_score := player2_wins[i]; j := i
                end;
                if j <> -1 then {Игрок 2 может выиграть}
                begin
                  play_strategy[position] := j;
                  player2_max[position] := max_score;
                  player1_max[position] := player1_max[j];
                 if value_of_pos[position] > max_score then
                 player2_max[position] := value_of_pos[position]
                end
                else {гарантии выигрыша Игрока 2 нет}
                  begin
                  for i := 1 to numb_of_pos do
                  if (player1_wins[i] > -1)and((op_min_score = -1) or
                       (op_min_score > player1_wins[i])) then
                  begin
                          op_min_score := player1_wins[i]; j := i
                   end;
                  play_strategy[position] := j;
                  player2_max[position] := player2_max[j];
                  player1_max[position] := op_min_score;
                   if value_of_pos[position] > player2_max[position] then
                   player2_max[position] := value_of_pos[position]
          end
     end
 end;

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