Tóm tắt đề bài

Các số tự nhiên được phân vào 3 hàng A, B, C theo quy luật như ví dụ:

• A: \(1, 6, 7, 12, 13, 18, \dots\)
• B: \(2, 5, 8, 11, 14, 17, 20, \dots\)
• C: \(3, 4, 9, 10, 15, 16, 21, \dots\)

Nhập \(N\), hãy xác định \(N\) thuộc hàng nào (in ra A, B hoặc C).

Phân tích

Quan sát các dãy theo modulo \(6\):

• Hàng A: \(1, 6, 7, 12, 13, 18, 19, \dots\)
  • Lấy \(\bmod 6\): \(1, 0, 1, 0, 1, 0, 1, \dots\)
  • Vậy A ứng với \(N \bmod 6 \in \{0,1\}\).
• Hàng B: \(2, 5, 8, 11, 14, 17, 20, \dots\)
  • Lấy \(\bmod 6\): \(2, 5, 2, 5, 2, 5, 2, \dots\)
  • Vậy B ứng với \(N \bmod 6 \in \{2,5\}\).
• Hàng C: \(3, 4, 9, 10, 15, 16, 21, \dots\)
  • Lấy \(\bmod 6\): \(3, 4, 3, 4, 3, 4, 3, \dots\)
  • Vậy C ứng với \(N \bmod 6 \in \{3,4\}\).

Lý do xuất hiện chu kỳ \(6\): khi liệt kê số tự nhiên, mẫu phân bố vào 3 hàng lặp lại sau mỗi 6 số.

Vì \(N \le 10^{10}\), cách làm theo mô phỏng là không thể; nhưng dùng phép chia dư là \(O(1)\).

Hướng giải quyết

Nhận xét

Chỉ cần tính \(r = N \bmod 6\), rồi ánh xạ:

• Nếu \(r = 0\) hoặc \(r = 1\) ⇒ in A
• Nếu \(r = 2\) hoặc \(r = 5\) ⇒ in B
• Nếu \(r = 3\) hoặc \(r = 4\) ⇒ in C

Thuật toán

1. Đọc số \(N\).
2. Tính \(r = N \bmod 6\).
3. Kiểm tra theo 3 nhóm giá trị của \(r\) và in ra hàng tương ứng.

Độ phức tạp

• Thời gian: \(O(1)\)
• Bộ nhớ: \(O(1)\)

Code tham khảo

n = int(input())

if n % 6 == 1 or n % 6 == 0:
    print('A')
if n % 6 == 2 or n % 6 == 5:
    print('B')
if n % 6 == 3 or n % 6 == 4:
    print('C')