Bảng mã Ascii (HSG '18)

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong bảng mã ASCII, \(26\) kí tự chữ cái thường từ ‘a’ đến ‘z’ được mã hóa tương ứng bằng các số tự nhiên từ \(97\) đến \(122\).

Cho một xâu kí tự \(S\) chỉ chứa toàn các kí tự chữ cái thường. Gọi \(P\) là xâu mã hóa tương ứng của xâu \(S\) bằng cách mã hóa từng ký tự trong \(S\) (theo bảng mã ASCII) và viết liên tiếp nhau. Ví dụ: \(S\) = ‘ab’ thì \(P\) = ‘9798’.

Hãy viết chương trình nhập vào từ bàn phím một xâu đã mã hóa \(P\) và in ra màn hình xâu kí tự \(S\).

Input

  • Một xâu đã mã hóa \(P\).

Output

  • In ra màn hình xâu ký tự \(S\).

Constraints

  • \(1 \leq P.size() \leq 255\)

Example

Test 2

Input 
979899
Output 
abc

Test 3

Input 
1009711097110103
Output 
danang

Bình luận


  • 0
    thanhyl7a20    3:34 p.m. 12 Tháng 10, 2021

    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

    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∈[l,r] đúng hay sai

    Ta tính v2 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 v3 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 ô

    Code tham khảo<Accepted> : Cài đặt
    Complexity : O(|s|) time || O(|s|) memory
    Copy
    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;

    }
    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
    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∈[′a′,′z′] thì xuất, không thì khởi tạo nó về 0 để tính tiếp
    Công thức tnow=10∗tpre+(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
    Code tham khảo<Accepted> : Giải trực tiếp
    Complexity : O(|s|) time || O(1) memory
    Copy
    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;
    }


    • 0
      thanhkhoa123    10:40 a.m. 8 Tháng 7, 2022

      HÌNH NHƯ CODE MẪU SAI :)))


      • 0
        lagiahuy    1:19 p.m. 14 Tháng 10, 2021 ← đã chỉnh sửa

        (đã thu hồi)

        4 bình luận nữa