SPOJ.COM - Thuật toán bài ARMY - Army Strength

Đề bài:

Đợt tấn công tiếp theo của MechaGodzilla đang trên đường đến trái đất. Và một lần nữa, trái đất sẽ phải chiến đấu với MechaGodzilla. Đội quân của MechaGodzilla bao gồm nhiều quái vật nguy hiểm, ví dụ như Space Godzilla, King Gidorah, và MechaGodzilla. Để ngăn chặn chúng, và bảo vệ trái đất, Godzilla và bạn cô ấy đang chuẩn bị cho trận chiến.

Vấn đề đặt ra:

Mỗi đội quân bao gồm nhiều loại quái vật khác nhau. Mỗi quái vật có sức mạnh được biểu diễn bởi một số nguyên dương. Số càng lớn thì quái vật càng mạnh. Cuộc chiến sẽ bao gồm nhiều trận nhỏ. Mỗi trận, tất cả những con quái vật yếu nhất sẽ bị giết.

Nếu có một vài quái vật yếu nhất, nhưng chúng ở cùng một đội thì một trong số chúng sẽ bị giết ngẫu nhiên. Nếu cả 2 đội quân đều có ít nhất một con quái yếu nhất thì con quái vật ở đội của MechaGodzilla sẽ bị giết. Cuộc chiến kết thúc khi tất cả quái vật một trong hai đội quân bị giết hết. Đội quân còn lại sẽ chiến thắng.

Bạn được cho sức mạnh của tất cả các con quái vật. Hãy tìm ra đội chiến thắng.

Đầu vào

Dòng đầu tiên là số nguyên T, chỉ số lượng test case. Mỗi test case bắt đầu bằng một dòng trắng. Mỗi test case sẽ bắt đầu bằng 1 dòng gồm 2 số dương NG, NM lần lượt là số lượng quái vật của đội Godzilla và MechaGodzilla. Hai dòng tiếp theo. Dòng thứ nhất bao gồm NG số nguyên dương biểu diễn sức mạnh của các con quái vật ở đội Godzilla. Dòng thứ 2 là NM số dương biểu diễn sức mạnh của các con quái vật ở đội MechaGodzilla.

Đầu ra

Với mỗi test case, in ra kết quả của cuộc chiến.

Nếu chắc chắn rằng đội Godzilla thắng thì in ra "Godzilla".

Nếu chắc chắn rằng đội MechaGodzilla thắng thì in ra "MechaGodzilla".

Ngược lại thì in ra "uncertain".

Ví dụ

Đầu vào:

2 
1 1 
1 
1 
3 2 
1 3 2 
5 5 

Đầu ra:

Godzilla 
MechaGodzilla

Giải thích:

• Test case 1: mỗi đội có 1 con quái vật, và chúng có cùng độ mạnh. Do đó, quái vật ở đội MechaGodzilla sẽ bị giết. Vì vậy, đội Godzilla sẽ thắng.

• Test case 2: sẽ có 3 trận chiến, và trong mỗi trận quái vật của đội Godzilla sẽ chết. Cuối cùng, đội MechaGodzilla sẽ thắng.

Chú ý: với C/C++ sử dụng kiểu int và Pascal sử dụng kiểu longint là OK

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

Phân tích:

Ta sẽ sắp xếp quái vật theo chiều độ mạnh tăng dần. Tạo 2 con trỏ để duyệt đồng thời 2 dãy. Sau đó kiểm tra xem con nào có độ mạnh yếu hơn thì sẽ bị diệt.

Sau quá trình duyệt, đội nào vẫn tồn tại quái vật thì sẽ thắng.

Thực tế, theo như yêu cầu đề bài thì chắc chắn sẽ có đội thắng.

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;

int NG, NM;

void Merge(int *a, int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    int *temp = new int[right - left + 1];

    while(l <= m && r <= right)
    {
        if(a[l] < a[r]) temp[k++] = a[l++];
        else temp[k++] = a[r++];
    }

    while(l <= m) temp[k++] = a[l++];

    while(r <= right) temp[k++] = a[r++];

    for(int i = 0; i < k; i++)
        a[left + i] = temp[i];

    delete[] temp;
}

void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right)/2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, right);
        Merge(a, left, m, right);
    }
}

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

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

    int Testcase = 0;
    cin >> Testcase;

    for(int tc = 0; tc < Testcase; tc++)
    {
        cin >> NG >> NM;

        int *ng_army = new int[NG];
        for(int i = 0; i < NG; i++)
            cin >> ng_army[i];

        int *nm_army = new int[NM];
        for(int i = 0; i < NM; i++)
            cin >> nm_army[i];

        // Sắp xếp sức mạnh của quái vật theo chiều độ mạnh tăng dần
        MergeSort(ng_army, 0, NG-1);
        MergeSort(nm_army, 0, NM-1);

        // 2 con trỏ vào 2 mảng, để duyệt lần lượt các phần tử
        int ig = 0, im = 0;
        while(ig < NG && im < NM)
        {
            // nếu độ mạnh quái vật ở đội MechaGodzilla <= độ mạnh
            // quái vật ở đội Godzilla thì quái vật đội MechaGodzilla sẽ chết
            // ngược lại thì quái vật đội Godzilla sẽ chết.
            // thực tế, sẽ luôn tồn tại 1 đội thắng
            if(nm_army[im] <= ng_army[ig]) im++;
            else if(nm_army[im] > ng_army[ig]) ig++;
        }

        // Đội nào vẫn còn quái vật thì sẽ thắng
        if(ig < NG) cout << "Godzilla" << endl;
        else cout << "MechaGodzilla" << endl;

        delete[] ng_army;
        delete[] nm_army;
    }

    return 0;
}