Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Магический квадрат подрядка N#49391

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

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100). В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы

✓ 1✗ 411 200средняяВойти и решать

Параллельное программирование#44715

Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает.
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.

Входные данные

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 10⁶). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 10³). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ {N, E, S, W} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом.
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.

Выходные данные

Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".

Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".

Примеры

№	Входные данные	Выходные данные
1	8 5 4 4 4 S 6 2 W 6 3 N 6 4 S	13

Двумерные массивы

✓ 6✗ 1201 200средняяВойти и решать

Гипер-минимум#38471

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), где 1 ≤ i_k ≤ N − M + 1, i_k ≤ j_k ≤ i_k + M − 1, а M - заданное число.

Входные данные
В первой строке входного файла задаются N и M (1 ≤ M ≤ N). Остальные строки файла содержат элементы массива X. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению 10⁹. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Выходные данные
Выведите искомый массив Y в том же формате, в котором был дан массив X.

Примеры

№	Входные данные	Выходные данные
1	1 1 1	1
2	3 2 3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1	-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5

Двумерные массивы

✓ 1✗ 21 200средняяВойти и решать

Луч света в темном царстве#38360

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

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

Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры

№	Входные данные	Выходные данные
1	3 5 X.... ..... .....	XXXXX XXXXX XXXXX
2	3 3 ... ..X ...	/X\ X.X \X/

Двумерные массивы Задачи на моделирование

✓ 3✗ 01 200средняяВойти и решать

Building a Ski Course#27301

Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:

RSRSSS

Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).

Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.

ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.

Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.

INPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа M и N.

* Строки 2..M+1: M строк ровно по N символов (каждый R или S),

описывающих желаемое финальное состояние поля.

OUTPUT FORMAT:

* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.

Ввод	Вывод
3 6 RSRSSS RSRSSS RSRSSS	3

OUTPUT DETAILS:

ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец, S в колонках 4-6.

Двумерные массивы Конструктив

✓ 0✗ 41 200средняяВойти и решать

Modern Art #3#27225

Недавно вошла в моду корова-художница Picowso.

Picowso рисует особым образом. Она начинает на чистом холсте N×N, представленной матрицей N×N нолей, где ноль означает пустую ячейку холста. Затем она рисует до 9 прямоугольников на холсте, каждый одним из 9 цветов (последовательно пронумерованных 1…9). Например, она может начать рисовать прямоугольник цветом 2, получая такое промежуточное состояние холста:

2220

0000

Затем она может нарисовать прямоугольник цветом 7:

2220

2777

0000

Затем она может нарисовать прямоугольник цветом 3:

2230

2737

2777

0000

Каждый прямоугольник имеет стороны, параллельные сторонам холста и самый большой прямоугольник может быть размером с весь холст, а самый маленький размером в одну ячейку. Каждый цвет из 1…9 используется ровно один раз, хотя впоследствии любой цвет может полностью покрыть некоторые из ранних цветов.

По заданному конечному положению холста вычислите сколько из ещё видимых цветов могли быть первым нарисованным цветом.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер холста (1≤N≤10). Следующие N строк описывают финальную картинку холста, каждая содержит по N чисел в интервале 0…9. Гарантируется, что такой ввод был получен рисованием как описано выше с использованием различных цветов.

ФОРМАТ ВЫВОДА:

Выведите количество цветов, которые могли быть использованы первым, из всех цветов, которые видны на финальном рисунке.

Ввод	Вывод
4 2230 2737 2777 0000	1

Двумерные массивы Конструктив

✓ 4✗ 181 200средняяВойти и решать

Крепкий дом#27001

Джон Доу хочет построить крепкое здание, чтобы никто и никогда не нашел его. У него есть кирпичи 1х2, 1х3 и "уголки", то есть квадратики 2х2, у которых отсутствует одна клетка. Для уточнения смотрите на рисунки.

Стеной назовем клеточный прямоугольник, который заполняют кирпичи. Кирпичи должны ложиться по линиям сетки, их можно как угодно поворачивать. Кирпичи не могут накладываться друг на друга и на каждой клетке должен лежать кирпич.

Джон считает стену крепкой, если нельзя провести такую прямую, что по обе стороны от нее есть кирпичи и она не пересекает ни одного кирпича. Касание кирпичей не считается пересечением. Вам требуется спроектировать крепкую стену, величиной NхM. Можно поворачивать кирпичи на углы, кратные 90 градусам.

Формат входных данных

Вводятся числа N и M (1 <=N, M <= 100) высота и ширина требуемой стены.

Формат выходных данных

Выведите N строк, содержащих по M символов от «A» до «Z», описывающие стену. Каждый кирпич должен описываться одинаковыми символами (кирпичи, имеющие общую сторону должны описываться различными символами). Не должно существовать прямой, по обе стороны которой были бы кирпичи и она не пересекала бы ни один из кирпичей. Если стену с заданными ограничениями построить невозможно, выведите «impossible».

Частичные решения, работающие при N, M <=6 получат не менее 40 баллов.

Двумерные массивы

✓ 0✗ 11 300средняяВойти и решать

Крестики-нолики#21821

Пете и Васе стало очень скучно на уроке биологии, и они решили поиграть в любимую всеми школьниками игру в крестики-нолики до пяти в ряд на бесконечном поле.

Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй — ноликами. В свой ход игрок

выбирает свободную клетку поля и ставит туда свой символ. Если после хода очередного игрока на поле есть пять его символов подряд по вертикали, горизонтали или диагонали, то сделавший такой ход игрок объявляется победителем и игра заканчивается.

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

за один ход. Петя называет ход оптимальным, если для этого хода выполнено одно из двух:

• этот ход приводит к немедленной победе Пети;

• не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети

будет следующий ход, который приведет к его немедленной победе.

Помогите Пете найти количество оптимальных ходов.

Формат входных данных

В первой входного файла находятся два натуральных числа n, m (1 ≤ n,m ≤ 200) — размеры прямоугольника, содержащего все уже поставленные на поле крестики и нолики.

Следующие n строк содержат по m символов, каждый из которых равен одному из следующих:

«.» (точка), «X» (заглавная латинская буква «икс») или «0» (ноль). При этом «.» обозначает пустую клетку, «X» обозначает крестик, а «0» обозначает нолик. Гарантируется, что на поле находится

равное число крестиков и ноликов, и ни один игрок еще не одержал победу.

Формат выходных данных

Выведите одно число — количество оптимальных ходов Пети.

Примеры

№	Входные данные	Выходные данные
1	5 3 ... 000 XXX ... ...	2
2	4 4 ..0. .XX0 .0X. ....	0
3	5 6 ...... .XXX.. .0000. ..X... ......	0

Двумерные массивы Задача на реализацию Простые игры

✓ 1✗ 21 300средняяВойти и решать