Матч 346, Охота за бриллиантами (DiamondHunt)

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

Имеется строка, содержащая символы ‘<’ и ‘>’. Каждая подстрока вида “<>”является бриллиантом. Когда в строке обнаруживается бриллиант, то последовательность “<>”удаляется из нее. Продолжаем процесс обнаружения и удаления бриллианта из строки до тех пор, пока это можно сделать. В задаче требуется подсчитать количество найденных таким образом бриллиантов.

Класс: DiamondHunt

Метод: int countDiamonds(string mine)

Ограничения: mine содержит от 1 до 50 символов ‘<’ и ‘>’.

Вход. Строка mine, состоящая из символов ‘<’ и ‘>’.

Выход. Количество бриллиантов, найденных в строке mine указанным способом.

Пример входа

mine

"><<><>>><"

">>>><<"

"<<<<<<<<<>>>>>>>>>"

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

3

0

9

РЕШЕНИЕ

обработка строк

Для решения задачи можно промоделировать процесс поиска и удаления бриллиантов при помощи строковых функций. Но поступим иначе. В переменной depth будем подсчитывать количество открывающихся скобок ‘<’. Если встречается закрывающаяся скобка ‘>’ и значение переменной depth на текущий момент больше нуля, то символ ‘>’ обязательно образует бриллиант в какой-нибудь момент времени. В этом случае количество найденных бриллиантов увеличим на 1, а значение depth уменьшим на 1.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

class DiamondHunt

{

public:

int countDiamonds(string mine)

{

int res, i, depth;

for(depth = res = i = 0; i < mine.size(); i++)

{

if (mine[i] == '<') depth++;

else if (depth > 0) depth--, res++;

}

return res;

}

};