Hiểu bài toán

Mô tả bài toán về một người con gái đeo bộ vòng tay 7 chiếc. Ban đầu cô đeo tất cả 7 chiếc ở tay trái. Cứ sau mỗi ngày, cô chuyển một vòng từ tay này sang tay kia. Sau 7 ngày (một tuần), cô sẽ quay lại tay ban đầu (tay trái) để tiếp tục chuyển vòng. Yêu cầu: Cho số ngày n (1 ≤ n ≤ 100), hãy tính số vòng còn lại trên tay trái và tay phải tại ngày thứ n.

Các cách tiếp cận

Cách Mô phỏng dựa trên chu kỳ (Cycle Analysis)

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

int main() {
    int n;
    cin >> n;

    // Chu kỳ lặp lại sau 14 ngày (7 ngày chuyển từ trái sang phải, 7 ngày chuyển từ phải sang trái)
    int k = n % 14;
    int left, right;

    if (k == 0) {
        // Sau 14, 28, ... ngày, về lại trạng thái ban đầu (trống tay phải)
        left = 7;
        right = 0;
    } else if (k <= 7) {
        // Nằm trong 7 ngày đầu tiên (chuyển từ trái sang phải)
        left = 7 - k;
        right = k;
    } else {
        // Nằm trong 7 ngày sau (chuyển từ phải sang trái)
        // k nằm trong khoảng 8 đến 13
        left = k - 7;
        right = 14 - k;
    }

    cout << left << " " << right;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này nhận thấy rằng hành động chuyển vòng lặp lại theo chu kỳ 14 ngày.

• 7 ngày đầu: Chuyển 1 vòng từ Trái sang Phải mỗi ngày. Sau k ngày (0<k<=7): Trái có <code>7-k, Phải có k.
• 7 ngày tiếp (ngày 8 đến 14): Chuyển 1 vòng từ Phải sang Trái mỗi ngày.
• Công thức chung:
  • r = n % 14.
  • Nếu r == 0: Trạng thái ban đầu (7, 0).
  • Nếu r <= 7: Trái = 7 - r, Phải = r.
  • Nếu r > 7: Trái = r - 7, Phải = 14 - r. Cách này xử lý O(1) và rất hiệu quả.

Cách Mô phỏng trực tiếp (Simulation)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int left = 7;
    int right = 0;
    int day = 1;

    int direction = 1; // 1: Chuyển từ Trái sang Phải, -1: Chuyển từ Phải sang Trái

    while (day <= n) {
        if (direction == 1) {
            left--;
            right++;
            if (left == 0) direction = -1;
        } else {
            left++;
            right--;
            if (right == 0) direction = 1;
        }
        day++;
    }

    cout << left << " " << right;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách cài đặt đúng nhất theo mô tả 'tháo chiếc vòng ở tay này đeo qua tay khác và sẽ di chuyển ngược lại nếu như hết 01 tuần'.

• Ban đầu có 7 vòng ở Trái.
• Dùng biến direction để xác định hướng chuyển.
• Khi một tay hết vòng (0), hướng chuyển sẽ đảo ngược.
• Lặp lại n lần.
• Với n nhỏ (≤ 100), cách này chạy rất nhanh và dễ hiểu.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chu kỳ lặp lại sau 14 ngày.
• Trạng thái của các tay phụ thuộc hoàn vào số ngày đã trôi qua tính từ trạng thái ban đầu.
• Có thể giải nhanh bằng công thức toán học thay vì chạy mô phỏng.

Lỗi thường gặp

• Quên xử lý trường hợp khi n chia hết cho 14 (dư 0), cần gán về trạng thái ban đầu (7, 0).
• Nhầm lẫn giữa việc chuyển vòng khi đã sang chu kỳ thứ 2 (tay phải chuyển về tay trái).