Входные данные: стандартный ввод Выходные данные: стандартный вывод Ограничения на память: 32 MB Время на тест: 1 секунда Тесты к задаче:Скачать
Score – это игра для двух игроков. Игровое поле состоит из N точек, пронумерованных от 1 до N, часть из которых соединена стрелками. Каждая стрелка идет от одной точки к некоторой другой точке. Каждая точка принадлежит одному из двух игроков. Игрок, которому принадлежит точка, называется ее владельцем. Кроме того, каждой точке приписано некоторое положительное число. Все приписанные числа различны. Точка с номером 1 является стартовой. В начале игры каждый из игроков имеет 0 очков.
Игра состоит в следующем. Будем обозначать буквой С текущую точку, то есть точку, в которой мы находимся в начале хода. В начале игры С является точкой с номером 1 (стартовой). Ход в игре делает владелец С, при этом выполняются следующие операции:
Если значение, приписанное С, больше, чем текущее количество очков у владельца С, то значение числа, приписанного С, становится новым количеством очков для владельца С. В противном случае, число очков у владельца С остается прежним. Количество очков другого игрока в обоих случаях не меняется.
Далее владелец С выбирает по своему усмотрению одну из стрелок, выходящих из текущей точки, и точка, на которую эта стрелка указывает, становится новой текущей. Заметим, что один игрок может сделать подряд несколько ходов.
Игра заканчивается, когда после некоторого хода текущей становится стартовая точка. Победителем считается игрок, который имеет большее количество очков в конце игры.
Набор стрелок между точками всегда такой, что
из любой точки выходит по крайней мере одна стрелка;
любая точка Р достижима из стартовой точки, то есть, существует такая последовательность стрелок, по которой можно добраться от стартовой точки до Р;
гарантируется, что игру всегда можно закончить за конечное число ходов.
Напишите программу, которая играет в эту игру и выигрывает. Наборы точек и стрелок во всех играх, в которые будет предложено сыграть вашей программе для ее оценки, организованы так, что ваша программа всегда может выиграть вне зависимости от того, принадлежит ей первый ход или нет. Во время оценки вашей программы противник будет играть оптимально, то есть, при первом же неправильном ходе со стороны вашей программы она проигрывает.
ВВОД И ВЫВОД
Ваша программа читает входные данные из стандартного потока ввода и записывает выходные данные в стандартный поток вывода. Ваша программа - это Игрок 1, а противник – Игрок 2. Ваша программа начинает свою работу со считывания следующих входных данных из стандартного потока ввода.
Первая строка входных данных содержит одно целое число – количество точек N, 1≤N≤1000. Каждая из последующих 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
stdout
объяснение
4
N
0 1 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, вы должны организовать ввод и вывод следующим образом:
Если ваша программа на Pascal, вы должны организовать ввод и вывод следующим образом:
Readln(target);
Writeln(target);
ВСПОМОГАТЕЛЬНЫЕ ПРОГРАММНЫЕ СРЕДСТВА
Вам дана программа (score2 для Linux, score2.exe для Windows), которая читает описание начальных данных из файла с именем score.in и переписывает их в стандартный поток вывода в форме, в какой их должна считать ваша программа из стандартного потока ввода. После этого программа score2 играет за Игрока 2, читая ходы вашей программы из стандартного потока ввода и записывая свои ходы, сделанные случайным образом, в стандартный поток вывода. Вы можете запустить вашу программу и программу score2 в отдельных окнах и вручную организовать игру между ними.
ОЦЕНКА ПРОГРАММЫ
Если ваша программа при тестировании выигрывает, то вы получаете полный балл за тест, в противном случае - 0 баллов. При тестировании ваша программа сначала будет играть с другой программой, и на всю игру будет отводиться на 1 секунду больше времени, чем указано во временных ограничениях. Ввод и вывод программ будут записаны в некоторые файлы. Затем ваша программа запускается второй раз, при этом входные данные направляются ей из записанного при первом запуске файла. Ваша программа должна выдать те же самые выходные данные, что и при первом запуске. При втором запуске определяется реальное время работы вашей программы. дома цены автомобилей . мясное пюре . Автозапчасти оптом Шевроле