9-11 класс
Задача 1. «СовятникХагварца»(20б).
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT. TXT
Ограничение по времени тестирования: 1 секунды на один тест.
В совятнике школы Хогварц для почтовых сов сделали полочки для сидения. Будем обозначать занятое совой место 1, а свободное 0. Таким образомсовятник задается квадратной таблицей А[1:N,1:N], элементы которой равны 0 или 1, причем пусть всегда А[i, i]=0 для любого i (на этих полочках установлены светильники).
Необходимо найти, если они есть, такие строку i0 и столбец j0, чтобы в столбце j0 были все 0, а в строке i0 - все 1 (кроме элемента A[i0,i0], равного 0).
Формат входных данных:
В первой строке входного файла записано целое число: N – размерсовятника. В следующих N строках записаны через пробел по N чисел 0 или 1. (0<N<=5000)
Формат выходных данных:
В выходной файл вывести через пробел найденные i0 и j0 или –1, если таких строки и столбца нет.
Пример:
INPUT. TXT | OUTPUT. TXT |
4 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 | -1 |
Задача 2. «Гуляющий кубик»(20б).
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT. TXT
Ограничение по времени тестирования: 2 секунды на один тест.
Гарри Поттеру на день рождения подарили волшебный кубик. Кубик находится на некоторой клетке обычной шахматной доски размером 8×8. Кубик полностью закрывает собой ровно одну клетку доски, т. е. размер ребра кубика равен размеру стороны клетки доски. На каждой стороне кубика записано какое-то целое число N (0 ≤ N ≤ 1000). На разных сторонах кубика могут быть различные числа.
Из начальной клетки кубик с помощью заклинания перемещается по доске путем его поворота через соответствующее ребро на соседнюю клетку. Каждому возможному пути перемещения кубика из начальной клетки в конечную можно поставить в соответствие сумму чисел, побывавших на его нижней грани, при этом каждое число добавляется столько раз, сколько оно появлялось на нижней грани кубика. Числа, соответствующие начальному и конечному положению кубика, также суммируются. Путь кубика считается оптимальным, если при достижении конечной клетки названная сумма оказывается минимальной.
Требуется написать программу, определяющую путь между двумя заданными клетками, которому будет соответствовать минимальная сумма чисел, побывавших на нижней грани кубика. Начальная и конечная клетки различны.
Формат входных данных:
Во входном файле INPUT. TXT в первой строке через пробел записаны координаты начальной и конечной клеток в следующем формате: первый символ – буква от ‘a’ до ‘h’ включительно, определяющая номер столбца на шахматной доске, второй – цифра от 1 до 8 включительно, определяющая номер строки.
Во второй строке файла находятся 6 чисел, которые записаны на гранях кубика спереди, сзади, сверху, справа, снизу и слева соответственно. Числа в строке разделены пробелами.
Формат выходных данных:
Выходной файл OUTPUT. TXT состоит из двух строк. В первой строке записана минимальная сумма чисел пути. Во второй строке выведен сам оптимальный путь перемещения кубика или один из возможных путей, если их несколько. Путь представляет собой последовательность координат клеток на шахматной доске, отображающих процесс перемещения кубика. Он начинается в начальной клетке и заканчивается в конечной. Все координаты клеток должны быть представлены в том же формате, что и во входном файле и разделены пробелами.
Пример файлов входных и выходных данных:
INPUT. TXT | OUTPUT. TXT |
е2 e3 0 8 1 2 1 1 | 5 e2 d2 d1 e1 e2 e3 |
Задача 3. «Шоу»(20б).
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT. TXT
Ограничение по времени тестирования: 5 секунд на один тест.
В процессе разработки сценария для ежегодного праздника в школе Хогварц главный режиссер задумал небольшое шоу с перестроением его участников в различное число колонн ровно N способами. Для достижения наибольшего эффекта нужно было, чтобы при любом перестроении количество людей в каждой колонне было одинаковым. Чтобы решить эту задачу режиссеру необходимо знать, какое минимальное число участников M ему для этого понадобится. Например, для случая N=3 потребуется пригласить всего четыре человека, которые могут выстроиться в 1, 2 и 4 колонны. Если же для некоторых N потребуется более 109 человек, то режиссер должен отказаться от задуманной идеи, так как необходимое число участников собрать невозможно.
Требуется написать программу, которая решает поставленную перед режиссером задачу, т. е. для заданного количества способов построения N определяет минимальное количество участников шоу.
Формат входных данных:
Входной файл INPUT. TXT содержит одно натуральное число N (N£1000), определяющее количество необходимых режиссеру способов построения участников.
Формат выходных данных:
Выходной файл OUTPUT. TXT должен содержать число M, равное минимальному количеству участников, необходимых режиссеру для осуществления N способов построения в процессе шоу. Если найденное число M превосходит 109, то выходной файл должен содержать только число 0.
Пример файлов входных и выходных данных:
INPUT. TXT | OUTPUT. TXT |
5 | 16 |
6 | 12 |
24 | 360 |
Задача 4. «Конверты для Прорицательницы»(20б).
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT. TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Как Вы, должно быть, помните, после победы Нео над агентом Джоном Смитом и заключения мира с Империей Машин, наступил новый день. Прорицательница сообщила Нео, что теперь «все будет хорошо» и можно спокойно уйти на покой. Но, чтобы не быть признанной устаревшей и ненужной программой, Прорицательница задумала заняться гаданиями. Свои предсказания она написала на открытках и теперь собирается разложить их по конвертам.
В распоряжении Прорицательницы имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров Открытки нельзя складывать, сгибать и т. п., но можно помещать в конверт под углом. Например, открытка с размерами сторон 5×1 помещается в конверты с размерами 5×1, 6×3, 4.3×4.3, но не входит в конверты с размерами 4×1, 10×0.5, 4.2×4.2.
Требуется написать программу, определяющую, можно ли разложить все открытки по конвертам, чтобы в каждом конверте было по одной открытке.
Формат входных данных:
В первой строке входного файла INPUT. TXT записано целое число N – количество открыток и конвертов (1<=N<=20).
В следующих Nстроках указаны размеры открыток, по одной открытке на строку. Это пары положительных чисел, записанных через запятую, не превосходящих 105.
Далее следуют N строк с размерами конвертов. Размеры конвертов указаны в том же формате, что и открыток: в каждой строке через пробел по два положительных числа, меньше либо равных 105.
Формат выходных данных:
В выходной файл OUTPUT. TXT необходимо вывести слово «ДА», если предсказательница сумеет разложить все открытки по конвертам, или слово «НЕТ» в противном случае.
Пример файлов входных и выходных данных:
INPUT. TXT | OUTPUT. TXT |
2 1 5 8 2 3 10 4.3 4.5 | ДА |
2 1 7 8 2 3 10 4.3 4.5 | НЕТ |
Задача 5. "Укладка плиток"(20б).
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT. TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Мэр города Энска принял решение вымостить главную городскую площадь разноцветными плитками. В распоряжении строителей имеются наборы из разноцветных прямоугольных плиток размером 1´2 кв. метр. Дизайнеры разделили городскую площадь на прямоугольные площадки длиной nметров и шириной mметров (n, m – четные числа) и приняли решение укладывать площадки таким образом, чтобы выполнялись следующие условия:
1) все плитки площадки разных цветов;
2) ни одна плитка площадки не соприкасается полностью с какой-либо плиткой соседней площадки.
Так как количество цветов плиток ограничено, то все площадки выкладываются плитками одинаковых наборов цветов.
Строители должны вымостить плитками очередную прямоугольную площадку размером m×n. Если плитку представить в виде прямоугольника размером 1×2, на каждой половинке которой указан код ее цвета, то расположение плиток на площадке можно изобразить, как показано на рисунке 1 (n=2, m=4). На рисунке 2 изображен один из вариантов расклада плиток на новой площадке, которую строители могут вымостить с учетом сделанных ограничений.
Требуется написать программу, которая по расположению плиток в исходной площадке определяет их возможное расположение в очередной площадке, которую необходимо вымостить строителям.
Формат входных данных:
Входной файл INPUT. TXT содержит следующую последовательность строк. В первой строке записаны через пробел два целых числа n и m, определяющие размеры площадки (n, m – четные числа, не превосходящие 100). Далее следуют n строк, в каждой из которых содержится по m чисел, указывающих расположение плиток в исходной площадке. При этом каждая плитка представляется двумя одинаковыми числами, расположенными в клетках площадки, покрытых данной плиткой. Все плитки пронумерованы натуральными числами от 1 до их общего количества. Числа в каждой строке файла разделены пробелами.
Формат выходных данных:
Выходной файл OUTPUT. TXT должен содержать одно число – «–1», если решение не существует. В противном случае, он должен содержать n строк, в каждой из которых должно находиться по m чисел, указывающих в вышеуказанном формате расположение плиток в площадке, которую строителям необходимо вымостить. Числа в каждой строке файла должны быть разделены пробелами.
Если существует несколько решений задачи, то вывести одно из решений.
Пример файлов входных и выходных данных:
INPUT. TXT | OUTPUT. TXT |
2 4 1 1 2 2 3 3 4 4 | 2 1 1 4 2 3 3 4 |
Основные порталы (построено редакторами)