Ответ в теме: Правильные скобочные последовательности

      Комментарии к записи Ответ в теме: Правильные скобочные последовательности отключены

Главная Форумы Программирование Алгоритмы и структуры данных Правильные скобочные последовательности Ответ в теме: Правильные скобочные последовательности

#3814

Решение задачи предоставил Данил Рязанцев:

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
// 1 - (
// 0 - )
using uint = unsigned int;
bool check(uint seq, uint bit){
int num = 0; // +1 = (
// -1 = )
if(!((seq >> (bit-1)) & 1) || (seq & 1)){
return false;
}
for(int i = bit-1; i >= 0; --i){
if((seq >> i) & 1){
++num;
}
else {
--num;
}
if(num < 0){
return  false;
}
}
return num == 0;
}
std::string coder(uint seq, int bit){
std::string s;
for(int i = bit-1; i >= 0; --i){
if((seq >> i) & 1){
s += '(';
}
else {
s += ')';
}
}
return s;
}
uint decoder(const std::string& s) {
uint res = 0;
for (auto i : s) {
res  |= (i == '(');
res <<= 1;
}
return res;
}
int main() {
size_t N;
std::cin >> N;
std::vector<std::string> vec_seq;
uint begin = 0;
for(size_t i = 0; i < N; ++i){
begin <<= 2;
begin |= 2;
}
uint end = 0;
for(size_t i = 0; i < N; ++i){
end <<= 1;
end |= 1;
}
end <<= N;
do{
if(check(begin, N*2)){
vec_seq.push_back(coder(begin, N*2));
}
begin += 2;
} while(begin <= end);
std::cout << "F(" << N << "): " << std::endl;
for(const auto &i : vec_seq){
std::cout << i << std::endl;
}
std::cout << vec_seq.size() << std::endl;
return 0;
}

Комментарий:

только не знаю зачем вычислять большие значения, когда уже при 10 количество правильных перестановок равно 16796, а при 11 = 58786