Матч 299, Проекции (Projections)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Имеется двумерная таблица, каждая ячейка которой или пустая, или занятая. Строки front и right характеризуют фронтальную и боковую проекцию: i - ый элемент front содержит ‘x’, если в i - ой колонке имеется хотя бы одна занятая ячейка, и символ ‘.’, если вся i - ая колонка пустая. Аналогично i - ый элемент right содержит ‘x’, если в i - ой строке имеется хотя бы одна занятая ячейка, и символ ‘.’, если вся i - ая строка пустая. По двум строкам front и right необходимо определить минимально и максимально возможное количество занятых ячеек в таблице.

Класс: Projections

Метод: vector<int> count(string front, string right)

Ограничения: массивы front и right содержат от 1 до 50 элементов, каждый элемент массивов содержат ‘x’ или ‘.’.

Вход. Два строковых массива front и right, содержащие символы ‘x’ и ‘.’.

Выход. Массив целых чисел, содержащий два числа: минимально и максимально возможное количество занятых ячеек в таблице.

Пример входа

front	right
“x”	“x”
“x.”	“.x”
“xxxx”	“x..x”
“x...xx..x.xxx..x.xx.”	".xx..xxx.xx."

Пример выхода

{1, 1}

{1, 1}

{4, 8}

{10, 70}

РЕШЕНИЕ

математика

Вычислим количество символов ‘x’ в массивах front и right и занесем его в переменные xf и xr. Минимально возможное количество занятых ячеек равно max(xf, xr), максимально возможное равно xf * xr.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

class Projections

{

public:

vector<int> count(string front, string right)

{

vector<int> res(2);

int xf = std::count(front.begin(),front.end(),'x');

int xr = std::count(right.begin(),right.end(),'x');

res[0] = max(xf,xr); res[1] = xf*xr;

return res;

}

};