SPOJ.COM - Thuật toán bài ANARC09A - Seinfeld

Đề bài:

Mình đã viết những câu chuyện được nhiều năm rồi, một vài trong số đó thì khá là ngớ ngẩn, chỉ là biến những vấn đề đơn giản trở nên phức tạp, và những vấn đề phức tạp trở nên đơn giản. Nhưng, điều đó không dành cho vấn đề sau.

Bạn được đưa cho một chuỗi kí tự, không có dấu cách và được tạo bởi toàn những dấu ngoặc đóng và mở. Nhiệm vụ của bạn là tìm ra số bước tối thiểu để làm cho chuỗi kí tự này trở nên hợp lệ. Sự hợp lệ được định nghĩa như sau:

1. Chuỗi kí tự rỗng được gọi là hợp lệ

2. Nếu S hợp lệ thì, {S} cũng hợp lệ

3. Nếu S, T hợp lệ, thì kết hợp lại là ST cũng hợp lệ.

Tất cả những chuỗi sau là hợp lệ: {}, {}{} và {{}{}}. Nhưng những cái sau đây thì không hợp lệ: }{, {{}{, và {}{

Một bước được định nghĩa là một lần thay thế dấu mở ngoặc thành đóng ngoặc hoặc ngược lại.

Đầu vào

Gồm 1 hay nhiều test case. Mỗi test case được miêu tả trên 1 dòng. Dòng này không chứa dấu cách và chỉ chứa dấu mở ngoặc và đóng ngoặc. Có tối đa 2000 kí tự và tất cả đều có độ dài chẵn. Dòng cuối cùng của đầu vào được tạo bởi 1 hay nhiều dấu '-'.

Đầu ra

Mỗi test case, in ra theo mẫu:

k. N

Trong đó, k là số thứ tự test case (bắt đầu từ 1), và N là số bước tối thiểu để chuyển chuỗi đã cho thành chuỗi hợp lệ.

Ví dụ

Đầu vào:

}{ 
{}{}{} 
{{{} 
---

Đầu ra:

1. 2 
2. 0 
3. 1 

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/ANARC09A/

Phân tích

Ở đây ta sẽ sử dụng stack để loại bỏ những cặp hợp lệ. Bằng cách là lần lượt cho từng kí tự vào stack, nếu kí tự ở đỉnh stack là { mà kí tự cho thêm vào là } thì khi đó ta sẽ cho kí tự ở đỉnh stack ra ngoài. Vì chúng là cặp hợp lệ.

Sau đó, ta sẽ xử lí đối với những kí tự còn lại trong stack để tính ra số bước cần thiết.

Ở đây, mình không dùng thư viện có sẵn. Mình sử dụng mảng cùng với một biến để lưu độ dài mảng. Và sẽ thao tác với nó giống như stack.

Ví dụ: int stack[MAX], leng = 0;

• Muốn push 1 phần tử x vào stack, mình sẽ xử lí như sau: stack[leng] = x; leng++;

• Muốn pop phần tử ở stack ra thì mình sẽ xử lí như sau: leng--;

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

const int MAX = 2005;

char str[MAX], stack[MAX];
int  stack_leng, Answer;

int GetLength(char *str)
{
    int length = 0;
    while(str[length] != '') length++;
    return length;
}

int main()
{
    ios::sync_with_stdio(false);

    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    int tc = 0;
    int length;

    while(true)
    {
        cin >> str;
        if(str[0] == '-') break;

        tc++;
        stack_leng = 0;
        length       = GetLength(str);
        Answer     = 0;

        // cho kí tự đầu tiên vào stack
        stack[stack_leng++] = str[0];

        for(int i = 1; i < length; i++)
        {
            // Nếu đỉnh stack là '{' và kí tự tiếp theo cho vào là '}'
            // thì bỏ cả hai ra khỏi stack vì cặp này đã hợp lệ
            // Các trường hợp khác thì sẽ cho tiếp vào stack
            if(stack[stack_leng-1] == '{' && str[i] == '}') stack_leng--;
            else stack[stack_leng++] = str[i];
        }

        //
        if(stack_leng == 0)
            Answer = 0;
        else if(stack[0] == '{')
            // thì bắt buộc stack phải có dạng: {{{{,
            // vì nếu có dấu } thì ta đã bỏ cặp đó ra khỏi stack rồi
            Answer = stack_leng / 2;
        else // stack[0] = '}'
        {
            // duyệt từ đầu của stack
            int start = 0;

            while(true)
            {
                if (start >= stack_leng) break;

                if(stack[start] == '}' && stack[start + 1] == '}')
                {
                    Answer ++;
                    start  +=2;
                }
                else if (stack[start] == '}' && stack[start + 1] == '{')
                {
                    Answer += 2;
                    start  += 2;
                }
                else if (stack[start] == '{')
                // thì chắc chắn các kí tự phía sau phải là {
                {
                    Answer += (stack_leng - start)/2;
                    break;
                }
            }
        }

        cout << tc << ". " << Answer << endl;
    }

    return 0;
}