Каранаев Линар Минтимерович Стерлибашево 2017 содержание глава реферативное изложение

Ваша программа читает входные данные из стандартного ввода и пишет их в стандартный вывод. Ваша программа – Игрок 1, а программа жюри – Игрок 2. Когдаваша программа начинает работать, она должна считать следующую информацию из стандартного ввода.

Первая строка содержит одно целое число: количество позиций N. 1

Следующая строка содержит N целых чисел – владельцев позиций. Если позиция i принадлежит игроку 1 (то есть вам), то i-e число равно 1, иначе – 2.

Следующая строка содержитМцелых чисел – цены позиций. Если i-e целое число есть, то цена позиции i равнаj. Все эти величины j удовлетворяют свойствам: 1≤j≤N и все ценыj различны.

Игра начинается с положения фишки в позиции 1. Ваша программа должна играть, как описано ниже, и закончить игру, когда фишка вернется в позицию 1.

• 
  Если сейчас очередь хода вашей программы, то она должна написать номер следующей позиции Р, 1≤Р≤Мвстандартный вывод.
  
• 
  Если сейчас очередь хода вашего противника, то ваша программа должна прочитать номер следующей позиции Р,1≤Р≤N из стандартного ввода.
  

Позиции, помещенные в круглые скобки, принадлежат игроку l,a позиции в квадратных скобках принадлежат игроку 2. Каждая позиция имеетсобственную цену,записанную внутри скобок, и номер позиции рядом. Игра,которую предстоит сыграть, представлена далее.

По завершению игры игрок 1 имеет счет 3, игрок 2 имеет счет 2. Игрок 1 побеждает.

В нижеследующем примере target – это целая переменная для позиции.

Вам дается программа (score2 для Linux, score2.exe для Windows). Эта программа читает описание игры из файла score.in в вышеописанном формате. Программа пишет эту информацию в стандартный вывод в том же формате. Этот вывод может быть использован для ввода в вашу программу в тестовых целях. После этого программа играет со случайной стратегией, читая ходы вашей программы из стандартного ввода и записывая собственные ходы в стандартный вывод.

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

Тело главной программы выглядит следующим образом:

begin

Calculate; {Подготовка к работе}

cv:=l; {Текущая вершина}

While true do

begin

ifv[cv]=l {Еслиходмой}

Next(cv); {Выбратьход}

writeln(cv); {Передать его жюри}

end

readln(cv); {Ввести ход от соперника}

if cv=1 then exit; {Если вернулись в вершину 1 - конец}

end;

Главная программа очевидна и хорошо самодокументирована. Осталось разобрать содержание вызываемых из главной программы процедур InputData, Calculateи Next(cv). НачнемсInputData.

procedure InputData;

begin

for i:=l to N do

for j:=l to N do read (a[i , j]);

for i:=l to N do read(v[i]);

for i:=l to N do read(c[i]);

end;

• 
  N – количество позиций;
  
• 
  А– граф игры (a[i,j] = 1, если есть дуга из вершины i в вершинуj);
  
• 
  V – владельцы позиций v[i] = 1 или = 2;
  
• 
  С – цены позиций, от 1 до N, все различны.
  

procedure Calculate:

var

i : byte:

for i:=l to N do Sorted[c[i]]:=i;

for i:=l to N do

for j:=l to N do Free[i, j]:=true;

end;

Строка условия задачи «1≤j≤N и все ценыj различны» дает нам замечательнопростой способ отсортировать вершины (позиции) по возрастанию цен:

То есть в массиве Sorted на позиции k мы храним номер позиции (вершины), ценакоторой равна k. Кроме того, мы подготавливаем к последующим расчетам массив пометок использованных дуг графа: Free[i,j] =True, если дуга из i ъ] еще неиспользовалась.

И, наконец, процедура Next(cv) по текущей вершине cv вычисляет следующую вершину cv (в случае хода первого игрока):

Procedure Next(var cv:integer);

begin

for i:=N downto 1 do

begin

cv:=Sorted[i];

exit;

end;

if (a[cv.Sorted[i]]=l)and(v[Sorted[i]]=2)and Free[cv,Sorted[i]] then

begin

Free[cv.Sorted[i]]:=False;

exit;

end;

Если из текущей вершины нет дуги в нашу вершину, то затем перебираем дугив принадлежащие сопернику вершины в порядке возрастания цены с тем, чтобыхудшую взять первой.[2: 314-318]