Một máy Turing một băng nhận aⁿbⁿ bằng cách lặp: mỗi vòng gạch chữ a ngoài cùng trái và chữ b ngoài cùng phải, phải quét qua toàn bộ vùng dữ liệu. Vì có n vòng, mỗi vòng tốn O(n) bước nên tổng cộng là bậc hai O(n²) — minh hoạ định lý rằng nhận aⁿbⁿ trên máy một băng cần Θ(n²) bước.
Với cài đặt gạch-cặp chuẩn, số bước chính xác là T(n) = 2n² + 3n + 2, trong đó n là số chữ a (bằng số chữ b).
Cho n, hãy in T(n).
Ví dụ: n = 2 → T(2) = 2·4 + 3·2 + 2 = 16.
Một số nguyên n (số chữ a, bằng số chữ b).
0 ≤ n ≤ 100000.
Số nguyên T(n) = 2n² + 3n + 2.
Ví dụ:
Đầu vào:
2
Đầu ra:
16
Giải thích:
Đang tải editor...