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

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

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

#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