На планеті Бітакуляндії є щорічне престижне змагання, яке проводить Міс М, — міжнародний командний чемпіонат.
У цьому змаганні беруть участь жителі з усіх країн Бітакуляндії. На чемпіонаті також треба розв'язувати задачки з дуже цікавою легендою, як ця, але в командах. Найкращим командам за підсумками чемпіонату видаються призи.
Міс М нарешті прийшли довгоочікувані подарунки для чемпіонату, які треба відправити переможцям. Вона зрозуміла, що подарунків багато. І якщо з чашками та пакетиками все зрозуміло, то з футболками виникла проблема. Кожна команда має трьох учасників, і кожен з них замовив футболку одного з n кольорів та одного з m розмірів. Але Міс М не впевнена, що всі побажання переможців будуть виконані...
Тому Міс M розробила алгоритм, згідно з яким буде збирати подарунки для учасників.
Якщо футболка потрібного розміру та кольору ще залишилась, то вона її бере.
У протилежному випадку — шукає футболку того ж розміру, але іншого кольору. Якщо таких кілька, то колір з мінімальним номером.
Інакше шукаємо серед футболок наступного більшого розміру, але з пріоритетом кольору, який було вказано учасником на початку. Якщо немає футболки з пріоритетним кольором, але є кілька інших, то вибираємо футболку з мінімальним номером.
Інакше повторюємо процес попереднього пункту серед футболок наступного більшого розміру. Так повторюємо доти, доки такі розміри є.
Якщо ніяка футболка з тих, що залишилися, не підійшла, то футболку, яку вказав учасник, записують як відсутню.
Міс М вирішила, що треба відправити назад на склад футболки, які виявилися зайвими, та замовити ще ті футболки, які вона записала як відсутні, щоб задовольнити всіх переможців чемпіонату. Щоб не розкладати всі футболки власноруч, Міс M просить вас написати програму, яка:
Виводить, які саме футболки виявилися зайвими, у форматі таблиці розміром n×m, де l
ij
— кількість футболок i-го кольору та j-го розміру, які залишилися після того, як вона роздала всім учасникам футболки.
Виводить, які футболки треба замовити у форматі таблиці розміром n×m, де n
ij
— кількість футболок i-го кольору та j-го розміру, які попросили учасники, але організатори не змогли дати будь-які футболки.
Вхідні дані
Перший рядок містить два цілі числа n та m (1≤n≤100,1≤m≤6) — кількість різних кольорів та розмірів футболок відповідно.
Другий рядок містить m елементів — розміри футболок, які доставили Міс М. Розміри бувають — XS, S, M, L, XL, 2XL. Гарантується, що розміри даються в порядку зростання розмірів.
Кожен з наступних n рядків містить по m цілих чисел t
i1
,t
i2
,…,t
im
(0≤t
ij
≤5⋅10
3
) — кількість футболок i-го кольору та j-го розміру.
Наступний рядок містить одне ціле число k (1≤k≤10
5
) — кількість переможців.
Кожний з наступних k рядків містять по цілому числу c
i
(1≤c
i
≤n) та символу s
i
— колір та розмір кожної футболки відповідно. Гарантується, що s
i
— один з m розмірів, який був заданий.
Обробляти запити переможців треба саме в такому порядку, як зазначено.
Вихідні дані
У кожному з наступних з n рядків виведіть по m цілих чисел l
i1
,l
i2
,…,l
im
— кількість футболок i-го кольору та j-го розміру, які залишилися.
У кожному з наступних з n рядків виведіть по m цілих чисел n
i1
,n
i2
,…,n
im
— кількість футболок i-го кольору та j-го розміру, які потрібно докупити.
Приклади
Input
2 3
S M XL
1 3 0
3 0 3
9
1 S
2 XL
1 M
2 XL
1 M
2 M
1 M
2 S
1 XL
Answer
0 0 0
2 0 0
0 0 1
0 0 0
Ответы
Ответ:
Объяснение:
#include <iostream>
#include <vector>
#include <algorithm>
struct TShirt {
char size;
int count;
};
struct WinnerRequest {
int color;
char size;
};
int main() {
int n, m;
std::cin >> n >> m;
std::vector<char> sizes(m);
for (int i = 0; i < m; ++i) {
std::cin >> sizes[i];
}
std::vector<std::vector<int>> inventory(n, std::vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cin >> inventory[i][j];
}
}
int k;
std::cin >> k;
std::vector<WinnerRequest> requests(k);
for (int i = 0; i < k; ++i) {
std::cin >> requests[i].color >> requests[i].size;
}
std::vector<std::vector<int>> remainingInventory = inventory;
// Process each winner request
for (const auto& request : requests) {
int color = request.color - 1;
char size = request.size;
if (remainingInventory[color][size - 'A'] > 0) {
// Take the requested size and color if available
remainingInventory[color][size - 'A']--;
} else {
// Find a different color with the same size or larger size
char selectedSize = size;
int selectedColor = color;
while (selectedSize <= sizes.back() && remainingInventory[selectedColor][selectedSize - 'A'] == 0) {
if (selectedColor == n - 1) {
selectedColor = color;
selectedSize++;
} else {
selectedColor++;
}
}
if (selectedSize <= sizes.back()) {
remainingInventory[selectedColor][selectedSize - 'A']--;
}
}
}
// Output remaining inventory
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cout << remainingInventory[i][j] << " ";
}
std::cout << "\n";
}
// Output the required additional inventory
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cout << inventory[i][j] - remainingInventory[i][j] << " ";
}
std::cout << "\n";
}
return 0;
}