Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Решение задачи питон

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

В качестве собеседования Михаилу предложили очистить от мусора довольно большой двор. Для удобства представим двор как прямоугольную таблицу, состоящую из n строк и m столбцов. Строки пронумерованы сверху вниз числами от 1 до n, а столбцы — слева направо числами от 1 до m. На пересечении i-й строки и j-го столбца находится клетка с координатами (i,j).Изначально в каждой клетке двора лежит огромная куча мусора. Михаил в рамках своего собеседования произвел k
операций, каждая из которых была одного из двух типов:

Убрать весь мусор во всех клетках
(i,j), таких что i+j=s;
Убрать весь мусор во всех клетках (i,j), таких что i−j=d.
Ваша задача — определить количество клеток, в которых Михаил убрал весь мусор.
Формат входных данных
Первая строка содержит два целых числа n и m (1≤n,m≤10**9) — размеры двора. Вторая строка содержит одно целое число k(0≤k≤300000) — количество операций, совершенных Михаилом.

Каждая из следующих k строк содержит описание очередной операции, совершенной Михаилом в следующем формате:
+ s (2≤s≤n+m) — данная операция означает, что Михаил убрал весь мусор во всех клетках (i,j), таких что i+j=s;
- d(1−m≤d≤n−1)— данная операция означает, что Михаил убрал весь мусор во всех клетках (i,j), таких что i−j=d.

Формат выходных данных
Выведите одно целое число — количество клеток, в которых Михаил убрал весь мусор.

Примеры
Входные данные
4 4
4
+ 4
+ 2
- 0
- -3
Выходные данные
7
Примечания
Рассмотрим действия Михаила в примере из условия:

Михаил убирает мусор из клеток (i,j), для которых i+j=4. Это клетки с координатами (1,3), (2,2) и (3,1).
Михаил убирает мусор из клеток (i,j), для которых i+j=2. Это клетка с координатами (1,1).
Михаил убирает мусор из клеток (i,j), для которых i−j=0. Это клетки с координатами (1,1), (2,2), (3,3) и (4,4).
Михаил убирает мусор из клеток (i,j), для которых i−j=−3. Это клетка с координатами (1,4).
Таким образом, мусор был убран из клеток (1,1), (1,3), (1,4), (2,2), (3,1), (3,3) и (4,4).

Написал код на с++, но он падает по времени на 17 тесте, кто может помочь с оптимизацией, либо другим оптимальным решением на любом языке)
Голосование за лучший ответ
Юлия Скрипниченко Мастер (1950) 1 месяц назад
Для решения задачи на Python, где у вас есть операции на сетке размером \(n \times m\), следует использовать эффективный подход, так как прямое моделирование сетки может быть неосуществимо из-за её огромного размера. Вот как можно решить задачу с использованием множества для отслеживания уникальных координат, в которых мусор был убран:

### Решение

1. **Используем множества для хранения координат.** Для каждой операции, которая очищает мусор, вычисляем координаты ячеек, которые очищаются, и добавляем их в множество. Поскольку множества не допускают дубликатов, это также гарантирует, что мы не будем подсчитывать одну и ту же ячейку несколько раз.

2. **Учитываем ограничения и особенности**:
- При обработке операций вида `+ s` (где `i + j = s`), мы перебираем возможные значения `i` и `j`, которые соответствуют данной операции и не выходят за границы матрицы.
- При обработке операций вида `- d` (где `i - j = d`), аналогично перебираем возможные значения `i` и `j`.

### Реализация на Python

```python
def count_clean_cells(n, m, k, operations):
cleaned_cells = set()

for operation in operations:
if operation[0] == '+':
s = int(operation[1])
# Проходим по возможным значениям i, j
for i in range(1, min(n + 1, s)):
j = s - i
if 1 <= j <= m:
cleaned_cells.add((i, j))

elif operation[0] == '-':
d = int(operation[1])
# Проходим по возможным значениям i, j
for i in range(1, n + 1):
j = i - d
if 1 <= j <= m:
cleaned_cells.add((i, j))

return len(cleaned_cells)

# Пример использования
n, m = 4, 4
k = 4
operations = [
('+', '4'),
('+', '2'),
('-', '0'),
('-', '-3')
]

print(count_clean_cells(n, m, k, operations))
```

### Объяснение

1. **Перебор для операций `+ s`**:
- Перебираем все возможные `i` от 1 до `s-1` и вычисляем `j` как `s - i`.
- Проверяем, чтобы `j` находился в пределах от 1 до `m`, чтобы не выйти за границы столбцов.

2. **Перебор для операций `- d`**:
- Перебираем все возможные `i` от 1 до `n` и вычисляем `j` как `i - d`.
- Проверяем, чтобы `j` находился в пределах от 1 до `m`, чтобы не выйти за границы столбцов.

Этот подход использует множества для хранения уникальных очищенных ячеек и позволяет эффективно подсчитать количество уникальных ячеек, в которых был убран мусор.
Егор Шуруповертов Ученик (152) 1 месяц назад
Я думал ты про змею будешь гворить
Похожие вопросы