Olymp8
.pdfПример
Входные данные
Первая строка входного файла содержит два натуральных числа: W – ширина доски, H – высота доски (1≤W,H≤75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ «X» (заглавная английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами –
X1, Y1, X2, Y2, причём 1≤X1,X2≤W, 1≤Y1,Y2≤H. Здесь (X1,
Y1) и (X2, Y2) – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Выходные данные
Для каждого запроса необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует
Мат-мех 2015 |
31 |
Трёхмерные ладьи
Игра в трехмерные шахматы ведется на кубическом поле N×N×N. Трехмерная ладья может ходить на любое число клеток по прямой в любом из шести направлений (в любую сторону в каждом из трех направлений).
На таком поле расставлены K ладей. Напишите программу, которая определит, бьют они все поле или нет.
Входные данные
В первой строке входного файла записано натуральное число N (1≤N≤1000), задающее размеры игрового куба, и количество ладей K (0≤K≤106). Далее записано K троек чисел, задающих координаты ладей (координата по каждому измерению — натуральное число от 1 до N).
Выходные данные
Выведите в выходной файл слово YES, если эти ладьи бьют весь куб, и слово NO в противном случае. В случае NO выведите во второй строке координаты какой-нибудь клетки, которая не бьется ни одной из ладей.
Мат-мех 2015 |
32 |
Литература
«Московские олимпиады по информатике 2002-2009» Е.В. Андреевой, В.М.Гуровица, В.А.Матюхина, Москва, 2009
Мат-мех 2015 |
33 |