In số lượng 'A' tối đa với 4 phím (A, Ctrl+A, Ctrl+C, Ctrl+V)

Cho phép dùng 4 thao tác: gõ 'A', Ctrl+A (chọn tất), Ctrl+C (sao chép), Ctrl+V (dán). Với N lần nhấn phím, tìm số lượng 'A' tối đa có thể tạo ra.

Quan sát: Với N ≤ 6, tốt nhất là chỉ gõ 'A' (kết quả = N). Với N ≥ 7, tối ưu là tìm điểm ngắt (breakpoint) để thực hiện chuỗi: Ctrl+A, Ctrl+C, rồi nhiều Ctrl+V.

Đầu vào và Đầu ra

Đầu vào: N = 7
Đầu ra: 9
(Cách làm: A, A, A, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V)

Thuật toán

1. Nếu keystrokes ≤ 6 → trả về keystrokes.
2. Mảng result[i] lưu số 'A' tối đa với i+1 phím.
3. Khởi tạo result[0..5] = 1..6.
4. Với n từ 7 đến keystrokes:
   • Thử mọi breakPoint từ n-3 xuống 1 (vị trí bắt đầu Ctrl+A).
   • curr = (n - breakPoint - 1) * result[breakPoint - 1] (số lần dán × số 'A' trước khi copy).
   • Cập nhật result[n-1] = max(result[n-1], curr).
5. Trả về result[keystrokes-1].

Ví dụ C++

#include <iostream>
using namespace std;

int keyNumbers(int keystrokes) {
    if (keystrokes <= 6) return keystrokes;
    int result[keystrokes];
    for (int n=1; n<=6; n++) result[n-1] = n;
    for (int n=7; n<=keystrokes; n++) {
        result[n-1] = 0;
        for (int breakPoint=n-3; breakPoint>=1; breakPoint--) {
            int curr = (n - breakPoint - 1) * result[breakPoint-1];
            if (curr > result[n-1]) result[n-1] = curr;
        }
    }
    return result[keystrokes-1];
}

int main() {
    int keystrokes;
    cout << "Enter Number of keystrokes: "; cin >> keystrokes;
    cout << "Maximum Number of A's with " << keystrokes << " keystrokes is: " << keyNumbers(keystrokes);
}

Kết quả

Enter Number of keystrokes: 7
Maximum Number of A's with 7 keystrokes is: 9