\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.7}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

Mục lục

1. <Cài đặt>
   • Hint
   • Approach
   • Code
     
     
2. <Giải trực tiếp>
   • Hint
   • Approach
   • Code

\(\color{#300000}{\text{Hint 1 <Cài đặt>}}\)

• Nhận thấy các chữ cái kết quả xuất ra được là phân biệt và không liên quan nhau (nghĩa là mình xuất một đoạn chữ số có giá trị là một kí tự thì những kí tự còn lại không bị ảnh hưởng và luôn có cách để xuất ra)

• Nên ta sẽ thử từng xâu có độ dài 2 và 3 và xuất ra nếu được

\(\color{#c01515}{\text{Approach 1 <Cài đặt>}}\)

• Gọi \(toDec(c)\) là hàm biến kí tự \(c\) thành chữ số

• Gọi hàm \(inRange(x, l, r)\) kiểm tra xem \(x \in [l, r]\) đúng hay sai

• Ta tính \(v_2\) là giá trị của 2 kí tự xét từ vị trí \(i\) xem nó thuộc đoạn \(97..99\) thì xuất ra và di chuyển con trỏ sang 2 ô

• Ta tính \(v_3\) là giá trị của 3 kí tự xét từ vị trí \(i\) xem nó thuộc đoạn \(100..122\) thì xuất ra và di chuyển con trỏ sang 3 ô

\(\color{#009933}{\text{Code tham khảo<Accepted> }}\): Cài đặt

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(|s|)\ \color{#7f5f3f}{\text{time}}\ ||\ O(|s|)\ \color{#7f5f3f}{\text{memory}}}}\)

int toDec(char c) { return c - '0'; }
bool inRange(int x, int l, int r) { return (l <= x) && (x <= r); }
int main()
{
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); )
    {
        int v2 = toDec(s[i + 0]) * 10 + toDec(s[i + 1]) * 1;
        if (inRange(v2, 97, 99))
        {
            cout << char(v2);
            i += 2;
        }

        int v3 = toDec(s[i + 0]) * 100 + toDec(s[i + 1]) * 10 + toDec(s[i + 2]) * 1;
        if (inRange(v3, 100, 122))
        {
            cout << char(v3);
            i += 3;
        }
    }

    return 0;
}

\(\color{#300000}{\text{Hint 2 <Tối ưu không gian>::<Giải trực tiếp>}}\)

• Dù có thể không cần thiết lắm và cải thiện được nhiều nhưng có tồn tại thuật toán giải trực tiếp bài này với việc nhận từng kí tự 1

Trong \(C++\) đó là lệnh \(std::getchar\)

\(\color{#c01515}{\text{Approach 2 <Tối ưu không gian>::<Giải trực tiếp>}}\)

• Gọi \(t\) là mã ASCII của kí tự hiện tại, nếu \(t \in ['a', 'z']\) thì xuất, không thì khởi tạo nó về \(0\) để tính tiếp

Công thức \(t_{now} = 10 * t_{pre} + (c - '0')\)

• Gọi \(c\) là kí tự hiện tại \(['0'..'9']\), chuyển nó về dạng số và chèn nó về bên phải \(t\), nếu nó không phải là chữ số thì nó không thuộc xâu \(S\) nữa nên ta sẽ dừng vòng lặp

\(\color{#009933}{\text{Code tham khảo<Accepted> }}\): Giải trực tiếp

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(|s|)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

inline bool isDigit(char c)      { return '0' <= c && c <= '9'; }
inline bool isLowerLatin(char c) { return 'a' <= c && c <= 'z'; }
int main()
{
   int t = 0; // khoi tao
   while (true) {
       char c = getchar();
       if (isDigit(c) == false) break; /// neu ki tu hien tai khong thuoc xau S

       t = 10 * t + (c - '0');
       if (isLowerLatin(t)) /// kiem tra
       {
           cout << t;
           t = 0; /// khoi tao
       }
   }

   return 0;
}