Задача [B'-B] 6: Работа дворником C++, Python, Java, Go, Rust, Pascal.
К черту это спортивное программирование! Пойду работать дворником!
Михаил
Однажды, после неудачно написанного контеста на 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
≤
300
000
) — количество операций, совершенных Михаилом.
Каждая из следующих
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
киньте кто нибудь пж С3 и С6
Ку, какие ещё задачи решил из b'-b и b-a', может помогу чем-то
#include <iostream>
#include <unordered_set>
#include <conio.h>
#include <windows.h>
#include <cmath>
#include <set>
using namespace std;
bool IsSizeConditionCompleted(int n, int m)
{
return (1 <= n && m <= pow(10, 9));
}
bool IsConditionOperationsCompleted(int k)
{
return (k >= 0 && k <= 300000);
}
struct cell
{
int i;
int j;
bool operator<(const cell& other) const {
return tie(i, j) < tie(other.i, other.j);
}
};
// Функция для вывода содержимого списка
void printCells(const set<cell>& cells) {
for (const auto& c : cells) {
cout << "cell(" << c.i << "," << c.j << ")" << endl;
}
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
set<cell> cleared_cells;
cout << "Дана матрица, которая апроксимирует размер двора: " << endl;
int n = -1, m = -1, k = -1;
while (IsSizeConditionCompleted(n, m) != true && IsConditionOperationsCompleted(k) != true)
{
cout << 'n' << " - это количество строк матрицы" << endl;
cin >> n;
cout << 'm' << " - это количество столбцов матрицы" << endl;
cin >> m;
cout << 'k' << " - это количество операций, которые произвёл работник" << endl;
cin >> k;
}
unordered_set<int> s_diagonals, d_diagonals;
for (int i = 0; i < k; ++i) {
char type;
int value;
cin >> type >> value;
if (type == '+') {
s_diagonals.insert(value);
}
else {
d_diagonals.insert(value);
}
}
// Рассчитываем клетки для +s
for (int s : s_diagonals) {
int min_i = max(1, s - m);
int max_i = min(n, s - 1);
if (min_i <= max_i) {
for (int i = min_i; i <= max_i; ++i) {
int j = s - i;
if (j >= 1 && j <= m) {
cleared_cells.insert({ i, j });
}
}
}
}
// Рассчитываем клетки для -d
for (int d : d_diagonals) {
int min_i = max(1, 1 + d);
int max_i = min(n, m + d);
if (min_i <= max_i) {
for (int i = min_i; i <= max_i; ++i) {
int j = i - d;
if (j >= 1 && j <= m) {
cleared_cells.insert({ i, j });
}
}
}
}
cout << "Очищенные клетки:" << endl;
printCells(cleared_cells);
cout << "Ответ: " << cleared_cells.size();
return 0;
}
Скинь пж bb1 и bb4, я тебе заплачу