Giải thuật vui - Cặp ngoặc kép

Discussion in 'C & C++' started by Mickey, Dec 5, 2017.

  1. Mickey

    Mickey Hacking For Hacker Staff Member

    Lâu lâu mình sang này hóng thấy Topic lập trinh bên này không sôi nổi lắm nhỉ :05.18-flustered: Thui có một đề toán khá hay leach từ spoj.com Cho anh em làm cho đỡ quên kiến thức :hypnotysed:
    Cho một dãy ký tự độ dài N chỉ gồm các ký tự mở ngoặc '(' và đóng ngoặc ')'.Ta nói hai vị trí (i,j) là một cặp ngoặc kép nếu như:
    1. 1≤i<j<n
    2. Ký tự thứ i và i+1 là dấu mở ngoặc '('
    3. Ký tự thứ j và j+1 là dấu đóng ngoặc ')'
    Hãy đếm xem có bao nhiêu cặp ngoặc kép xuất hiện trong xâu ký tự đã cho
    Input: Một dòng duy nhất chứa xâu ký tự độ dài N (1≤N≤50000)
    Output: Một số nguyên duy nhất là số lượng cặp ngoặc kép tìm được
    Example:
    Input: )((()())())
    Output: 4
    Ngôn ngữ cho phép: C/C++/Pas
    Cố gắng code bài tối ưu về thời gian xử lí và kích thước
     

Share This Page