Задача на реализацию

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

Формат входных данных
В первой строке записано натуральное число n (n <= 1000). Вторая и третья строки содержат соответственно время подготовки (в часах) и количество баллов набранных на экзамене i-м студентом (1<=i<=n). Все числа положительные целые. В первой строке числа не превышают 10, во второй строке - не превышают 100.

Выполните следующие задания
1. Создайте DataFrame из входных данных
2. Обучите модель LinearRegression
3. Предскажите оценку для студента, который готовился 5.5 часов
4. Во второй строке выведите через пробел два числа: коэффиценты k и b линии регрессии
6. В третьей строке выведите время подготовки, необходимое для получения чтобы получить 75 баллов 

Все числа необходимо вывести с точностью до одного знака после запятой

Словом называется последовательность символов ограниченная слева и справа пробелом или началом(концом) строки. Найдите все слова, начинающиеся на английскую букву p (без учета регистра).

Формат входных данных
Строка, состоящая из букв английского алфавита. Длина строки не более 1000 символов.

Формат выходных данных
Выведите все найденные слова в одной строке, разделяя их одним пробелом. Порядо слов должен быть таким же как в исходной строке.

Родители Андрея решили поклеить на одну из стен в его комнате новые обои. Высота стены n сантиметров, а ширина m сантиметров. К сожалению, обои, выбранные родителями, Андрею не понравились, и он решил их чем-нибудь закрыть. Так как он участвовал в большом количестве олимпиад, у него накопилось много дипломов. Все дипломы у Андрея одинаковые это прямоугольники высотой a сантиметров и шириной b сантиметров. Помогите Андрею узнать, сколько квадратных сантиметров обоев он сможет завесить дипломами, если не будет их разрезать и переворачивать. Все дипломы должны целиком размещаться внутри стены и не накладываться друг на друга.
Формат входных данных
В первой строке входных данных находится целое число n (1 n ≤ 2 ·10⁹) высота стены.
Во второй строке находится целое число m (1 ≤ m ≤ 2 · 10⁹) ширина стены.
В третьей строке находится целое число a (1 ≤ a ≤ 2 ·10⁹) высота диплома.
В четвёртой строке находится целое число b (1 ≤ b ≤ 2 · 10⁹) ширина диплома.
Формат выходных данных
Выведите одно целое число площадь части стены, которая будет закрыта дипломами, если их не поворачивать, не обрезать и не накладывать друг на друга.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в С и С++, тип long в Java и С#).

Замечание
В примере из условия можно разместить 6 дипломов, суммарная площадь которых равна 12 квадратным сантиметрам. Большее число дипломов разместить нельзя, они будут вылезать за границы стены.

 

Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.

Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор.

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

Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена.

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

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

re.finditer(pattern, string) - находит все совпадения, возвращает итератор.

• Возвращает: итератор объектов Match
• Использование: for match in re.finditer(r'\d+', text):

match.groups(default=None) - возвращает все захваченные группы в виде кортежа

Особенности:

• Возвращает ВСЕ группы из шаблона

• Группы нумеруются с 1 (group(1), group(2))

• Если группа не найдена, возвращает default (по умолчанию None)

match.group(0) - найденная строка

---

Найти все теги товаров и вывести их вместе с названиями товаров.

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

Товар: iPhone_14
Теги: Premium, New
Полное совпадение: Name: iPhone_14, Price: 999.99$, Category: Electronics, Tags: [Premium, New]

Извлечь номера заказов и общие суммы. Вывести в виде списка кортежей. 

Например, 
('1001', '2049.97')
...

Дубликаты - одинаковые строки в данных, которые могут исказить анализ.

Основные методы

df.duplicated() - находит дубликаты (возвращает True/False)
df.drop_duplicates() - удаляет дубликаты
df.nunique() - количество уникальных значений

Параметры drop_duplicates()

subset - столбцы для проверки дубликатов
keep - какую копию оставить ('first', 'last', False)
ignore_index -  пересоздает аккуратный последовательный индекс (0, 1, 2, 3, 4...).

Пример

df_clean = df.drop_duplicates()  # Удалить полные дубликаты
df_partial = df.drop_duplicates(subset=['name'])  # По имени
df_last = df.drop_duplicates(keep='last')  # Оставить последний

---

Задание

1) Посчитайте количество полных дубликатов в прикрепленном датасете (программа должна вывести целое число)
2) Удалите все полные дубликаты и выведите размер получившегося датасета.

Обработка пропусков

df.dropna() - удаляет строки с пропусками
df.fillna(value, inplace=True) - заполняет пропуски значением value
df.fillna(df.mean(), inplace=True) - заполняет средним значением

Параметр inplace:
inplace=False (по умолчанию) - создает копию с изменениями
inplace=True- изменяет исходный DataFrame напрямую

Метод fillna() с словарем позволяет заполнить пропуски в разных столбцах различными значениями за одну операцию. Синтаксис:

df.fillna({'column1': value1, 'column2': value2, ...})

Пример
 

df = ...
# Заполнение разными значениями
fill_dict = {
    'age': df['age'].mean(),      # Средним значением
    'salary': df['salary'].median(), # Медианой
    'city': 'Unknown'             # Константой
}

df_filled = df.fillna(fill_dict)
print(df_filled)

 

---

Задание

Проанализируйте датасет супергероев, считав его из прикрепленного файла
Напишите программу, который ищет и обрабатывает пропуски. 

1. Заполните пропуски в power и intelligence средними значениями
2. Заполните пропуски в costume_cost медианным значением 
3. Заполните пропуски в first_appearance значением 1950 
4. Для текстовых полей (name, alias, universe) заполните пропуски строкой Unknown

Выведите обработанный датасет на экран, используя print(df)

Пропущенные значения (NaN, None, NULL) - одна из главных проблем при анализе данных.

Поиск пропусков

df.isnull() - находит пропуски
df.isnull().sum() - считает пропуски по столбцам

 

---

Задание

Проанализируйте датасет супергероев, считав его из прикрепленного файла
Напишите программу, который ищет пропуски. Выведите

1. В первой строке - количество пропусков в каждом столбце (семь целых чисел через пробел)
2. Во второй строке - процент пропущенных значений (отбросив дробную часть) для каждого столбца  (семь целых чисел через пробел)

Числа должны быть в порядке перечисления столбцов в датасете.

Пример вывода (пример дан для понимания формата вывода):
1 2 3 2 1 1 4
10 20 30 20 10 10 40

⏰ Починка машины времени:
[██████████████░░░░░░] 71% - Модуль 5 из 7 восстановлен
✅ Генератор порталов: КАЛИБРУЕТСЯ
⚡ Энергия растет!

---

Каждый маячок имеет координату относительно 2025 года:

• Отрицательное число = маячок в прошлом (например, -50 означает 1975 год)
• Положительное число = маячок в будущем (например, +30 означает 2055 год)
• Ноль = сигнал остановки сканирования

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

Что должна делать программа:

1. Считывать координаты маячков (числа), пока не получит сигнал стоп (число ноль)
2. Подсчитать:
   • Сколько маячков в прошлом (отрицательные координаты)
   • Сколько маячков в будущем (положительные координаты)
   • Самый древний маячок (наименьшая координата)
3. Вывести отчет о сканировании (смотри пример)

 

💡 Подсказка:

- Текущий год = 2025 (точка отсчета)
- Если координата = -20, это 2025 - 20 = 2005 год
- Если координата = +15, это 2025 + 15 = 2040 год
- Чем меньше число, тем дальше в прошлое!

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

Для упрощения первой своей конструкции Оля приняла решение рассматривать задачу в виде плоскости таким образом, что лазер будет всегда находиться в начале координат, его направление будет иметь угол кратный 45-ти градусам, а система коробов, от которых он будет отражаться, всегда будет перпендикулярна взгляду (перпендикулярна плоскости OXY). Но также стоит учесть, что короба, от которых будет отражаться свет, имеют как свойства отражения света, так и преломления, притом со всех четырёх сторон. Стоит также пренебречь в ходе расчётов тем, что луч лазера может отражаться в обратном направлении, таким образом не теряя интенсивности, а при прохождении через начало координат считаем, что он не прерывается, а летит дальше).

Результатом успеха Оля считает тот случай, когда лазер в следствие отражений попал в результирующую точку, которую Оля заранее знает, но так как лазер имеет батарейку, которая быстро садится, она просит Вас помочь ей заранее определить, будет ли успешным её текущая конструкция.
Для удобства расчётов Оля гарантирует, что точка пересечения луча со сторонами металлических коробов будет всегда целым числом, а стороны короба будут параллельным осям OY и OX.
Входные данные
В первой строке подаются два числа:

•  направление лазера, находящегося в начале координат, в виде угла наклона кратного 45 градусам (угол считается против часовой стрелке) (положительное направление оси OX равно 0 градусов, а положительное направление оси OY равно 90 градусам) (угол от 0 до 315 градусов);
•  интенсивность света лазера в нановаттах (целое число от 100 до 5000).
• На второй строке подаётся число N (1 <= N <= 20) – количество металлических коробов (параллелепипедов), которые Оля хочет установить. Далее на N строках подаются через пробел параметры каждого короба:
•  координаты левого верхнего угла, координаты правого нижнего угла короба (целые числа в диапазоне [-100;100]);
•  процент поглощения света (вещественное число в диапазоне [0; 100]).

На последней строке входных данных подаются координаты результирующей точки (целые числа в диапазоне [-100;100])

Выходные данные
Вывести в ответе в случае успеха конструкции интенсивность (только целую часть), с которой луч лазера попадёт в результирующую точку.
Если конструкция не успешна (лазер поглотился более чем на 90% от начальной интенсивности), то вывести координаты первого короба на пути лазерного луча, при отражении от которого интенсивность стала меньше 10% от начального) с указанием полученной интенсивности (только целую часть) (вывод через пробел – координаты левого верхнего угла, правого нижнего, (в том порядке, в котором короб был введена в программу), затем полученная интенсивность).
Гарантируется, что лазер не может улететь в бесконечность, то есть результатом может быть либо поглощение луча, либо попадание в результирующую точку.

Компания “РудниК” хочет построить автономный рудодобывающий городок и ей необходимо рассчитать хватит ли её новому городу припасов на автономное существование в течении 100 месяцев. Для автономного существования городу необходимы: токарные изделия, электронные платы, бетон и еда. Изначально в городке находится по 30 единиц каждого ресурса. Каждые 10 месяцев в городок приходит по X единиц каждого ресурса. То есть при наступлении 10-го, 20-го, 30-го месяца и так далее. Чтобы автономно существовать без построек город потребляет по Y единицы каждого ресурса за месяц. Потребление ресурса происходит после поступления ресурсов с заводов и других источников. Если в какой-то месяц один из ресурсов кончится (станет равным 0 или меньше 0), то город закроют, а жителей вывезут. Рудодобывающий город начинает свой отсчёт с дня №1. Администрация города может строить здания, чтобы производить ресурсы самостоятельно:

• - завод по переработке отходов. Стоимость 8 токарных изделий, 3 электронные платы, 10 бетона. Время строительства 5 месяцев. Каждые 2 месяца завод будет выдавать 5 бетона и 2 токарных изделия. Потребляет 3 токарных изделия каждые 5 месяцев. ID завода - 1.
• - теплица. Стоимость 8 бетона и 5 токарных изделий. Время строительства 5 месяцев. Каждые 5 месяцев теплица будет приносить 7 еды. Потребляет 2 бетона каждые 10 месяцев. ID завода - 2.
• - завод по производству электроники. Стоимость 6 электронных плат, 10 токарных изделий, 10 бетона. Время строительства 10 месяцев. Каждые 10 месяцев будет выдавать по 6 электронных плат. Потребляет 2 токарных изделия каждые 18 месяцев. ID завода - 3.
• - завод по производству бетона. Стоимость 4 электронные платы, 8 токарных изделий, 8 бетона. Время строительства 8 месяцев. Каждые 8 месяцев будет выдавать по 8 бетона. Потребляет 1 токарное изделие и 1 электронную плату каждые 12 месяцев. ID завода - 4.

Завод начинает приносить доход или начинает вести отсчёт до выдачи новых ресурсов на следующий месяц после завершения его постройки или прошлой выдачи ресурсов. Если завод приносит ресурсы на n-ый месяц, на следующий n+1 месяц начинается отсчёт прихода ресурсов в новом цикле. Представим, что теплица начнёт строительство в 5-ый месяц, значит её строительство завершится на 9-ый месяц, производить ресурсы она будет с 10-го месяца, а первый “урожай” будет собран на 14-ый месяц. Администрация города может построить несколько заводов, если у неё хватает на это ресурсов. Можно начать строительство завода только, если на момент начала строительства все ресурсы есть в наличии. Месяц начала строительства завода полностью учитывается во времени его строительства. Только разные заводы/строения могут строится одновременно. Эффекты от нескольких заводов складываются.

Формат входных данных
На вход программа получает 2 числа 0<=X<=40, 1<=Y<=40, количество ресурсов, которые колония получается и тратит соответственно. И двумерный массив (каждый элемент на новой строке), размером 4 на 5, указывающий в какой месяц должно начаться строительство того или иного здания. Где по вертикали - ID строения/завода, а по горизонтали номер планируемой к строительству постройки. Каждую постройку могут построить максимально 5 раз. Если в столбце строения указано число 0, значит завод/строение не строится.

Формат выходных данных
На выходе программа должна выдать количество месяцев, которые город смог самостоятельно себя обеспечивать, если он просуществовал 100 месяцев, значит город признан успешным. На следующих строках вывести остаток ресурсов на момент завершения расчётов, не важно успешных или неуспешных. Числа могут принимать отрицательные значения.
Строка 1: Кол-во прожитых месяцев; 2: Токарных изделий; 3: Электронных плат; 4:Бетона; 5:Еды.

Иван Фёдорович сыщик с очень большим стажем. Однажды в городе произошла серия больших ограблений. На местах ограбления не было обнаружено ни улик, ни зацепок. Однажды грабителей практически застали врасплох, но они смогли скрыться. На месте преступления Иван Фёдорович заметил, что грабители обронили папку с листком и набором картонных карточек, с вырезанными окошками на этих картах. Придя в офис и рассмотрев улики подробнее, было замечено, что на листке напечатана прямоугольная матрица, состоящая из цифр, а карточки все были размером с матрицу, притом отверстия, вырезанные в карточках, отображали какие-то случайные цифры из матрицы.
Иван Фёдорович вспомнил, что когда-то сталкивался с подобной схемой обозначения мест ограбления, что карточки помогали определить координаты следующего места ограбления. Потому Иван Фёдорович решил выписать координаты всех мест преступлений в виде долготы и широты, а далее найти карточки, которые соответствуют координатам следующих мест преступлений.
Помогите ему быстрее найти преступников, определив координаты следующих мест преступлений.
Координаты преступления собираются при помощи карточки следующим образом:

• на матрицу накладывается карточка;
• далее двигаясь по каждой строке по порядку слева-направо, выписываются цифры, которые попали в прорези;
• цифр всегда 18, притом координаты всегда состоят из 8цифр (две целой части, шесть вещественной), значит два символа игнорируются и обозначают точку в вещественном числе в соответствующем порядке.

Пример матрицы и карточки (где белые участки – это вырезы (отверстия)).

Таким образом начинаем выписывать цифры по строкам слева-направо: 554755831378617673. Знаем, что цифр обозначающих координату 8, а две лишние – обозначающие запятые, получим координаты 55.755831 37.617673.
Также на каждой карточке Иван Фёдорович заметил на углу пометку, которая, как позднее он понял, определяет, как должна быть развёрнута карточка, так как метка должна при наложении всегда находиться в левом верхнем углу при взгляде на неё:

• 1 – метка в левом верхнем углу карточки;
• 2 – метка в правом верхнем углу карточки;
• 3 – метка в правом нижнем углу карточки;
• 4 – метка в левом нижнем углу карточки.

Входные данные
на первой строке подаётся целое число K (2 <= K <= 100) – количество преступлений, которые совершили грабители;
далее на K строках подаются координаты предыдущих мест преступлений в виде вещественных чисел с точкой, разделённых пробелом (например, 55.755831 37.617673)
на следующей строке подаются размеры матрицы и карточек в виде целых чисел N, M (5 <= N,M <= 1000), где N – количество строк матрицы, а M – количество столбцов;
далее на N строках подаются по M цифр матрицы;
после подаётся на новой строке целое число – количество карточек L (K < L <= 100); 
далее подаётся на одной строке L цифр от 1 до 4 через пробел, которые отображаются метки карточка в соответствии с порядком их появления;
затем L раз по N строк и M цифр подаются карточки по порядку их появления, которые содержат либо цифру 1 – обозначающую наличие прорези на ней, либо 0 – если прорези в этом месте на карточке нет.
Выходные данные
выведите все координаты будущих мест преступлений (каждую с новой строки), отсортировав их по возрастанию (если две координаты одинаковые по первой координате, то сортировать по возрастанию по второй), координаты одного места выводить через пробел.
Примечание:
·при выводе дробной части координат выводить всегда 6 знаков, если знаков меньше, то дополнять их незначащими нулями;
·если матрица прямоугольная, то гарантируется, что при совмещении метки на карточке с левым верхним углом матрицы, карточка совпадёт с размером матрицы;
·данные на карточках нельзя отзеркаливать (переворачиватькарточки не в плоскости OXY);
·гарантируется, что если даны метки на карточках, то при повороте карточка совпадёт с размером матрицы, не будет такого, что карточка будет иного размера, чем матрица.

Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Формат ввода
На вход программе в первой строке подаётся натуральное число N. Далее идет N строк, каждая из которых содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
   0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
   1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
   2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
   3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Формат вывода
T строк: первая строка - состояние точки K в первую мс, вторая строка - состояние точки K во вторую мс, и так далее до T мс.

Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

В сказочном мире Геомаба живут необычные существа в виде прямоугольников. Все они разного размера, но передвигаются все они одинаково –перекатыванием сбоку на бок. В очередной из дней жители Геомаба решиливыбрать себе мэра, так как дороги в их мире очень опасные – в них очень многоям и в них легко застрять, так как жители-прямоугольники могут передвигатьсятолько по плоским дорогам.
Мэр решил незамедлительно собрать группу добровольцев и направить их по дорогам Геомаба, но дорог так много, что Мэр понял, что отправлять добровольцев, а потом вытаскивать их из ям – дело трудозатратное, потому он обратился к Вам за помощью – написать алгоритм, который по размеру прямоугольника покажет все ямы, которые необходимо залатать, чтобы житель-прямоугольник смог спокойно передвигаться по дороге, а город потратил минимально ресурсов (заделал как можно меньше ям).
Прямоугольник считается застрявшим, если он не смог беспрепятственно перекатиться через яму (его угол попал в яму (не включая начало и конец ямы)).
Если прямоугольник попал не углом в яму, а попал точно стороной на границы ямы, то он не считается застрявшим.

Формат входных данных
На вход на первой строке подаётся число X (1 <= X <= 100000) – длина дороги в метрах.
На второй строке подаются числа W, H (1 <= W,H <= 100) – высота и ширина жителя-прямоугольника в метрах соответственно.
На третьей строке подаётся число N (1 <= N <= 1000) – количество ям на дороге.
Далее на N-строках подаются координаты начала ямы (в метрах от начала дороги) и её ширина в виде целых положительных чисел от 1 до X. Координаты ям могут подаваться в любом порядке. Но все ямы не пересекаются и не накладываются.
Формат выходных данных
Выведите на первой строке количество ям, которые необходимо заделать, чтобы житель-прямоугольник, для которого производится расчёт, смог добраться до конца дороги.
Далее выведите координаты всех ям отсортированные в порядке появления от начала дороги до конца, КАЖДУЮ С НОВОЙ СТРОКИ.

Примечание
Житель-прямоугольник перед стартом дороги находится так, что три его вершины находятся за пределом начала дороги, а одна вершина, являющаяся самой правой, стоит на позиции 0. Первоначальное положение жителя-прямоугольника может быть любым, нужно выбрать оптимальное, чтобы залатать как можно меньше ям.
Если решений несколько, выведите то, в котором сумма координат ям для залатывания наименьшая.

В данном случае житель может стоять основанием перед началом дороги на стороне 2 (положение №1) или 3 (положение №2).
Если он стоит на основании длиной 2, то он попадёт только в яму под номером 14.
Если он стоит на основании длиной 3, то он попадёт в ямы 10 и 14.
Городу выгоднее заделать только одну яму, под номером 14.

Положение №1.


Положение №2.

 

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

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

В данном случае заданы две квадратные матрицы размер 3*3. Их поставили вплотную друг к другу, соприкасается только одна строка по одинаковым числам (строка 2).

Потому данная строка полностью удаляется в двух матрицах, потому получаем.

Далее каждая матрица вращается по часовой стрелке на 90 градусов.


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

Формат входных данных
На первой строке подаётся целое число N – размер квадратных матриц (1 <= N <= 1000).
Далее на N строках подаётся по N целых чисел в диапазоне от -1000 до 1000 – левая матрица.
Далее на N строках подаётся по N целых чисел в диапазоне от -1000 до 1000 – правая матрица.
Формат выходных данных
Вывести на одной строке через пробел сумму чисел оставшихся ячеек левой матрицы и правой матрицы, соответственно.



 

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из координат клетки и цвета. Если \(S_{i,j} = ((i', j'), c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же перемещается в клетку \((i', j')\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на минимальное требуемое число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

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

1. <<fill \(i\) \(j\) with \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

   • очередное перемещение привело робота в клетку, которую он уже красил в процессе выполнения текущей команды;

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<at-least \(x\) \(c\)>> — выставить ограничение на минимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле меньше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<no-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<move \(i\) \(j\) to \(i'\) \(j'\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \(((i', j'), c)\), где \((i', j')\) — клетка, в которую надо переместиться, а \(c\) — цвет, в который затем надо ее покрасить.

6. <<no-move \(i\) \(j\)>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = ((1, 2), \mathtt{red})\), \(S_{1,2} = ((2, 2), \mathtt{blue})\), \(S_{2,2} = ((2, 1), \mathtt{green})\) и \(S_{2,1} = ((1, 1), \mathtt{red})\), то при поступлении команды <<fill \(1\) \(1\) with blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Цвета задаются строками <<red>> (красный), <<green>> (зеленый), <<blue>> (синий) и <<white>> (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд. Для обозначения красного, зеленого или синего цвета используйте первую букву его английской записи (‘r’, ‘g’ или ‘b’); для обозначения белого цвета используйте символ ‘.’.

В первом примере из условия

1. Команда <<fill 1 1 with red>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = ((2, 1), \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = ((3, 1), \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<fill 2 1 with green>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \(((2, 2), \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<at-least 3 white>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   r.
   g.
   r.

4. Затем <<fill 2 2 with R>> должен покрасить \((2, 2)\) в красный (ограничение на число белых уже снято), но это бы привело к получению квадрата с цветами r.gr, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<fill 2 2 with B>> выполняется. После чего, в соответствии с \(S_{2,2} = ((1, 2), \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   rg
   gb
   r.

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из направления (вправо, вверх, влево, вниз) и цвета. Если \(S_{i,j} = (d, c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же смещается на одну клетку в направлении \(d\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на максимальное разрешенное число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

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

1. <<color \(i\) \(j\) \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

   • очередное перемещение привело робота в клетку, которую он уже красил в процессе выполнения текущей команды;

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<limit \(c\) \(x\)>> — выставить ограничение на максимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле уже больше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<block \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<settings \(i\) \(j\) \(d\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \((d, c)\), где \(d\) — направление перемещения, а \(c\) — цвет, в который затем будет раскрашена клетка, в которую робот переместится.

6. <<settings \(i\) \(j\) none>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = (\rightarrow, \mathtt{red})\), \(S_{1,2} = (\downarrow, \mathtt{blue})\), \(S_{2,2} = (\leftarrow, \mathtt{green})\) и \(S_{2,1} = (\uparrow, \mathtt{red})\), то при поступлении команды <<color \(1\) \(1\) blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Направления задаются строками <<right>> (вправо), <<up>> (вверх), <<left>> (влево), <<down>> (вниз). Цвета задаются заглавными буквами ‘R’ (красный), ‘G’ (зеленый), ‘B’ (синий) и ‘W’ (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд.

В первом примере из условия

1. Команда <<color 1 1 R>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = (\downarrow, \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = (\downarrow, \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<color 2 1 G>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \((\rightarrow, \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<limit B 0>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   RW
   GW
   RW

4. Затем <<color 2 2 R>> должен покрасить \((2, 2)\) в красный, но это бы привело к получению квадрата с цветами RWGR, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<color 2 2 B>> отрабатывает корректно, так как до этого было разрешено иметь на поле не больше \(1\) синей клетки. После чего, в соответствии с \(S_{2,2} = (\uparrow, \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   RG
   GB
   RW