Hướng dẫn giải

Cho dãy ~n~ chữ số và ~m~ lần bấm phím: phím 1 cộng thêm 1 (modulo 10) vào mọi chữ số, phím 2 dịch vòng sang phải một vị trí. Cần in trạng thái cuối cùng. Nhận xét then chốt: phép cộng 1 tác động lên tất cả chữ số như nhau nên nó không phụ thuộc vị trí, do đó giao hoán với phép dịch vòng.

Sub 1: Mô phỏng — ~O(n \cdot m)~, dùng khi ~n, m \le 1000~

Làm đúng theo đề: với mỗi phím, hoặc cộng 1 cho từng chữ số, hoặc dịch vòng cả xâu. Nếu chỉ nộp sub này: đúng 17/20 test (3 test lớn bị quá thời gian).

Sub 2: Đếm số lần bấm — ~O(n + m)~

Vì phép cộng và phép dịch vòng không ảnh hưởng lẫn nhau, kết quả chỉ phụ thuộc vào số phím 1 (gọi là ~c_1~) và số phím 2 (gọi là ~c_2~), không phụ thuộc thứ tự. Mỗi chữ số được cộng ~c_1 \bmod 10~ và bị dịch sang phải ~c_2 \bmod n~ vị trí (vòng tròn). Chữ số ở vị trí ~i~ (đánh số từ 0) chuyển tới vị trí ~(i + c_2) \bmod n~. Nếu chỉ nộp sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

Hàm main đọc dữ liệu; khi ~n, m \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.

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

int n, m;
string s, k;

// Sub 1: mô phỏng từng lần bấm phím — O(n*m)
void sub1() {
    for (char c : k) {
        if (c == '1') {
            for (int i = 0; i < n; i++) s[i] = (s[i] - '0' + 1) % 10 + '0';
        } else {
            rotate(s.begin(), s.end() - 1, s.end()); // dịch vòng sang phải 1 vị trí
        }
    }
    cout << s << "\n";
}

// Sub 2: phím 1 cộng cho mọi chữ số như nhau, phím 2 chỉ dịch vòng
// => chỉ cần đếm số phím 1 (cộng) và số phím 2 (dịch) — O(n+m)
void sub2() {
    int add = 0;
    long long rot = 0;
    for (char c : k) {
        if (c == '1') add++; else rot++;
    }
    add %= 10;
    rot %= n;
    string r(n, '0');
    for (int i = 0; i < n; i++)
        r[(i + rot) % n] = (s[i] - '0' + add) % 10 + '0';
    cout << r << "\n";
}

int main() {
    freopen("LOCK.INP", "r", stdin);
    freopen("LOCK.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> s >> m >> k;
    if (n <= 1000 && m <= 1000) sub1();
    else sub2();
}