Bài toán mật mã Ninja

Bài toán

Những Ninja thực hiện trao đổi thông tin với nhau theo cách riêng của họ. Trước khi trao đổi thông tin, họ sẽ dùng những mật mã để xác nhận đảm bảo người đối diện là Ninja cùng phe phái. Những mật mã này sẽ được tạo mới từng ngày bởi Shinobi – một Ninja đam mêm số học.
Shinobi tạo ra mật mã bằng cách lấy tích 3 chữ số của cùng của số NT (N, T tương ứng là ngày, tháng tạo mật mã).
Ví dụ: Hôm nay là ngày 19/3, 19^3 = 6859 và tích 3 chữ số cuối cùng là 360. Vậy mật mã ngày 19/3 Shinobi tạo ra là: 360.
Bạn hãy cho biết vào ngày N tháng T, thì mật mã Shinobi tạo ra là bao nhiêu?
Dữ liệu: Vào từ tệp NJCODE.INP gồm
một dòng duy nhất ghi số nguyên dương N và T (N ≤ 31, T ≤ 12).
Kết quả: Ghi ra tệp NJCODE.OUT mật mã Shinobi tạo ra trong ngày N tháng T.

Cài đặt bài toán với Python

Để giải bài toán này, chúng ta cần thực hiện các bước sau:

  1. Đọc dữ liệu từ tệp NJCODE.INP, lấy ra hai giá trị nguyên dương N và T.

  2. Tính giá trị của N^3.

  3. Lấy tích 3 chữ số cuối cùng của N^3.

  4. Ghi kết quả ra tệp NJCODE.OUT.

Dưới đây là đoạn code Python thực hiện các bước trên:

# Đọc dữ liệu từ tệp NJCODE.INP
with open('NJCODE.INP', 'r') as f:
    n, t = map(int, f.readline().split())

# Tính giá trị của N^3
n_cube = n**3

# Lấy tích 3 chữ số cuối cùng của N^3
code = (n_cube // 100) % 1000

# Ghi kết quả ra tệp NJCODE.OUT
with open('NJCODE.OUT', 'w') as f:
    f.write(str(code))

Chú ý rằng, khi lấy tích 3 chữ số cuối cùng của N^3, ta sử dụng phép chia nguyên để loại bỏ các chữ số ở đầu. Sau đó, ta sử dụng phép chia lấy dư cho 1000 để lấy ra 3 chữ số cuối cùng.

Ví dụ: Nếu trong tệp NJCODE.INP có nội dung là “19 3”, thì sau khi thực thi đoạn code trên, kết quả sẽ được ghi ra tệp NJCODE.OUT là “360”.

Cài đặt bài toán với C++

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    freopen("NJCODE.INP", "r", stdin);
    freopen("NJCODE.OUT", "w", stdout);

    int n, t;
    cin >> n >> t;

    // Tính giá trị của N^3
    int n_cube = n * n * n;

    // Lấy tích 3 chữ số cuối cùng của N^3
    int code = (n_cube / 100) % 1000;

    cout << code;

    return 0;
}

Đánh giá độ phức tạp

Để đánh giá độ phức tạp của thuật toán trên, ta xét từng bước một:

  1. Đọc dữ liệu từ tệp: Thao tác này có độ phức tạp O(1), vì chỉ cần đọc vào hai số nguyên.

  2. Tính giá trị của N^3: Thao tác này có độ phức tạp O(1), vì chỉ cần tính lũy thừa bậc ba của N.

  3. Lấy tích 3 chữ số cuối cùng của N^3: Thao tác này có độ phức tạp O(1), vì chỉ cần thực hiện một số phép chia và lấy dư.

  4. Ghi kết quả ra tệp: Thao tác này có độ phức tạp O(1), vì chỉ cần ghi ra một số nguyên.

Vì mỗi bước đều có độ phức tạp O(1), nên tổng độ phức tạp của thuật toán là O(1).

Vì vậy, ta có thể kết luận rằng độ phức tạp của thuật toán trên là O(1), tức là thuật toán có độ phức tạp cố định và không phụ thuộc vào kích thước đầu vào.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *