Tóm tắt đề bài

Kim phút của đồng hồ ban đầu ở vị trí \(a\) phút. Kim phút quay và đi qua số 12 đúng \(n\) lần, sau đó dừng lại ở vị trí số \(k\). Tính tổng số phút mà kim phút đã quay được.

Phân tích

• Các thông số cần lưu ý:
  • Một vòng đồng hồ tương ứng với 60 phút.
  • Vị trí số \(k\) trên mặt đồng hồ (từ 1 đến 12) tương ứng với phút thứ \(k \times 5\). Ví dụ: số 3 là phút thứ 15, số 6 là phút thứ 30.
  • Kim phút đi qua số 12 nghĩa là nó hoàn thành một chu kỳ và bắt đầu từ phút thứ 0.
• Ràng buộc: \(n\) có thể lên đến \(10^9\), do đó tổng số phút có thể vượt quá giới hạn của kiểu số nguyên 32-bit (\(2 \cdot 10^9\)). Chúng ta cần sử dụng kiểu số nguyên 64-bit (long long trong C++ hoặc int trong Python).

Cách làm đơn giản (Brute Force)

Ý tưởng

Mô phỏng việc kim phút quay từng phút một. Mỗi khi kim phút chuyển từ phút thứ 59 sang phút thứ 0 (vị trí số 12), ta tăng biến đếm số lần đi qua số 12. Dừng lại khi đã đi qua số 12 đủ \(n\) lần và kim phút đang ở vị trí \(k \times 5\).

Độ phức tạp

• Thời gian: \(O(n \times 60)\), với \(n = 10^9\) thì thuật toán này sẽ chạy mất khoảng \(6 \times 10^{10}\) bước, quá chậm để đạt điểm tối đa.
• Đánh giá: Phù hợp cho \(n \leq 10^5\).

Code Brute Force

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, n, k;
    cin >> a >> n >> k;
    long long total_minutes = 0;
    long long current_pos = a;
    long long pass_count = 0;
    long long target_pos = k * 5;

    while (true) {
        current_pos++;
        total_minutes++;
        if (current_pos == 60) {
            current_pos = 0;
            pass_count++;
        }
        if (pass_count == n && current_pos == target_pos) {
            break;
        }
    }
    cout << total_minutes << endl;
    return 0;
}

a = int(input())
n = int(input())
k = int(input())

total_minutes = 0
current_pos = a
pass_count = 0
target_pos = k * 5

while True:
    current_pos += 1
    total_minutes += 1
    if current_pos == 60:
        current_pos = 0
        pass_count += 1
    if pass_count == n and current_pos == target_pos:
        break

print(total_minutes)

Hướng giải quyết (Tối ưu)

Nhận xét

Chúng ta có thể chia quá trình quay của kim phút thành 3 giai đoạn:

1. Giai đoạn 1: Quay từ vị trí \(a\) ban đầu đến số 12 lần đầu tiên.
   • Số phút cần quay: \(60 - a\).
   • Sau giai đoạn này, kim phút đã đi qua số 12 được 1 lần.
2. Giai đoạn 2: Quay thêm các vòng toàn phần để đủ \(n\) lần đi qua số 12.
   • Vì đã đi qua 1 lần ở giai đoạn 1, ta cần đi qua thêm \(n - 1\) lần nữa.
   • Mỗi lần đi qua số 12 tiếp theo tương ứng với một vòng quay 60 phút.
   • Số phút cần quay: \((n - 1) \times 60\).
3. Giai đoạn 3: Từ số 12 (sau lần thứ \(n\)), quay đến vị trí số \(k\).
   • Vị trí số \(k\) tương ứng với \(k \times 5\) phút.
   • Số phút cần quay: \(k \times 5\).

Công thức tổng quát

Tổng số phút = (Phút để đến số 12 lần đầu) + (Phút cho \(n-1\) vòng quay tiếp theo) + (Phút từ số 12 đến số \(k\))

Độ phức tạp

• Thời gian: \(O(1)\) do chỉ sử dụng các phép tính toán cơ bản.
• Bộ nhớ: \(O(1)\).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Sử dụng long long để tránh tràn số vì n lên tới 10^9
    long long a, n, k;
    cin >> a >> n >> k;

    // Tính toán theo công thức đã phân tích
    // (60 - a): số phút để kim quay từ a đến số 12 lần thứ nhất
    // (n - 1) * 60: số phút để kim quay thêm n-1 vòng để đủ n lần qua số 12
    // k * 5: số phút từ số 12 quay đến vị trí số k
    long long result = (60 - a) + (n - 1) * 60 + (k * 5);

    cout << result << endl;

    return 0;
}

# Đọc dữ liệu vào
a = int(input())
n = int(input())
k = int(input())

# Python tự động xử lý số nguyên lớn nên không lo tràn số
# Áp dụng công thức:
# - Thời gian tới số 12 lần đầu: 60 - a
# - Thời gian cho n-1 vòng tiếp theo: (n - 1) * 60
# - Thời gian từ số 12 đến số k: k * 5
result = (60 - a) + (n - 1) * 60 + k * 5

print(result)