SPOJ.COM - Thuật toán bài ABSYS - Anti-Blot System

Posted on September 25th, 2016

Đề bài:

Tám là một học sinh lớp 2 rất thông minh, chăm chỉ và giỏi về lập trình. Gần đây, bạn ấy quyết định chuyển đổi toàn bộ nội dung ở vở ghi chép thành một phiên bản "điện tử". Tuy nhiên, Tám phát hiện ra rằng vở toán của bạn ấy bị dính đầy các vết mực.

Do đó, Tám đã scan lại toàn bộ nội dung và chuyển tới một thiết bị - cái mà bạn ấy đã lập trình ra nó từ khi mới biết chữ (quả là một thiên tài !!!). Thiết bị này thay thế tất cả vết mực thành dòng chữ "machula".

Vấn đề đặt ra ở đây là:

Bạn được đưa cho vở viết của Tám, được xử lý bởi thiết bị trên. Chúng bao gồm những bài toán đơn giản, được sử dụng để thực hành phép tính cộng với những số nguyên dương. Nhiệm vụ của bạn là phục hồi lại những vùng bị dính mực.

Đầu vào

Dòng đầu tiên là số tự nhiên T, xác định số lượng test case. Mỗi test case được bắt đầu bằng một dòng trống. Mỗi test case chỉ bao gồm 1 dòng, biểu diễn biểu thức dạng "number + number = number", trong đó, number là số nguyên dương. Một phần của biểu thức được thay thế bởi dòng chữ "machula". Dòng chữ này luôn luôn bao phủ một chuỗi các số không có dấu cách, thậm chí là bao phủ toàn bộ số. Giả sử mỗi biểu thức chỉ có một cách duy nhất để hoàn thành.

Đầu ra

Mỗi test case, đầu ra bao gồm 1 dòng dạng "number + number = number". Trong đó, tất cả các số đã được phục hồi.

Ví dụ

Đầu vào:

3 
23 + 47 = machula 
3247 + 5machula2 = 3749 
machula13 + 75425 = 77038 

Đầu ra:

23 + 47 = 70 
3247 + 502 = 3749 
1613 + 75425 = 77038 

Chú ý: với C++/C/Java sử dụng int, Pascal sử dụng longint là OK!

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/ABSYS/

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 = 1000;
 
bool IsDigit(char ch)
{
    if((ch >= '0' && ch <= '9')) return true;
    return false;
}
 
/*
* Trả về độ dài xâu nếu chúng chứa toàn chữ số từ 0 đến 9
* Nếu trong xâu có tồn tại kí tự không phải là số thì trả về -1
*/
int GetLength(char* arr)
{
    int length = 0;
    for(int i = 0; i < MAX; i++)
    {
        if(arr[i] == '') break;
        else if(IsDigit(arr[i])) length++;
        else 
        {
            length = -1;
            break;
        }
    }
    return length;
}
 
/*
* Chuyển đổi xâu chứa toàn chữ số thành số nguyên kiểu int
* Nếu xâu đầu vào không hợp lệ, tức chứa kí tự không phải số
* thì trả về số -1
* ngược lại thì trả về giá trị của số tương ứng
*/
int ConvertArrayToInt(char* str)
{
    int length = GetLength(str);
    if(length < 0) return -1;
 
    int r = 0;
    for(int i = 0; i < length; i++)
        r = r * 10 + str[i] - '0';
 
    return r;
}
 
int main()
{
    ios::sync_with_stdio(false);
    
    // comment dòng này khi submit
    freopen("input.txt","r",stdin);
 
    int T = 0;
    cin >> T;
    
    // tạo ra mảng 5 phần tử để lưu 5 thành phần trong biểu thức
    int a[5];
 
    for(int tc = 0; tc < T; tc++)
    {
        for(int i = 0; i < 5; i++)
        {
            char str[MAX];
            cin >> str;
 
            a[i] = ConvertArrayToInt(str);
        }
 
        // Thực tế ta chỉ cần quan tâm đến phần tử a[0], a[2], a[4]
        // vì chúng là số
        int n1 = a[0];
        int n2 = a[2];
        int n3 = a[4];
 
        // Vì mỗi biểu thức chỉ có một cách duy nhất để hoàn thành,
        // nên chỉ có khả năng
        // là 1 trong 3 vị trí bị dính mực
        if(n1 < 0) a[0] = a[4] - a[2];
        else if (n2 < 0) a[2] = a[4] - a[0];
        else a[4] = a[0] + a[2];
 
        cout << a[0] << " + " << a[2] << " = " << a[4] << endl;
    }
    
    return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!