Решение задачи "Баян" с Codeforces

С пояснением   Просмотров: 26


Баян — это строка (да, в реальном мире баяны — это музыкальные инструменты, но давайте на время забудем об этом), являющаяся конкатенацией следующих символов: открывающей квадратной скобки (ASCII код этого символа — 091), двоеточия (ASCII код — 058), нескольких (возможно, ни одного) символов вертикальной черты (ASCII код — 124), еще одного двоеточия и закрывающей квадратной скобки (ASCII код — 093). Длина баяна — это количество символов в нем.

Например, [::], [:||:] и [:|||:] — баяны длины 4, 6 и 7, соответственно. (:|:), {:||:}, [:], ]:||:[ баянами не являются.

Вам дана строка s. Вы хотите превратить ее в баян удалением нескольких (возможно, ни одного) символов из нее. Обратите внимание, что вставлять новые символы или менять порядок существующих нельзя. Можно ли превратить s в баян такими операциями, и если да, то какая может быть максимальная длина получившегося баяна?

Код

#include <bits/stdc++.h>

using namespace std;

void rem(string &s, const string &c) {
	auto pos = s.find(c);
	if (pos == string::npos) {
		cout << -1 << endl;
		exit(0);
	}
	s.erase(0, pos + 1);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> s;
	
	rem(s, "[");
	rem(s, ":");
	reverse(s.begin(), s.end());
	rem(s, "]");
	rem(s, ":");
	
	cout << count(s.begin(), s.end(), '|') + 4 << endl;
	
	return 0;
}

         

Администратор Photo Автор: Администратор


Никаких случаев. Никаких специальных идей. Просто жадность.

Решение состоит из шести шагов:

Удалим префикс строки до позиции самого левого символа '['. Если такого символа нет, то выведем -1;
Удалим префикс строки до позиции самого левого символа ':'. Если такого символа нет, то выведем -1;
Перевернем строку;
Удалим префикс строки до позиции самого левого символа ']'. Если такого символа нет, то выведем -1;
Удалим префикс строки до позиции самого левого символа ':'. Если такого символа нет, то выведем -1;
Выведем количество символов '|' в оставшейся строке плюс четыре.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться