Problem - B - Codeforces
codeforces.com
뒤에서부터
- 제목
Decode String
- 조건
time limit per test : 1 second
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
Polycarp has a string s consisting of lowercase Latin letters.
He encodes it using the following algorithm.
He goes through the letters of the string s from left to right and for each letter Polycarp considers its number in the alphabet:
if the letter number is single-digit number (less than 10), then just writes it out;
if the letter number is a two-digit number (greater than or equal to 10), then it writes it out and adds the number 0 after.
For example, if the string s is code, then Polycarp will encode this string as follows:
'c' — is the 3-rd letter of the alphabet. Consequently, Polycarp adds 3 to the code (the code becomes equal to 3);
'o' — is the 15-th letter of the alphabet. Consequently, Polycarp adds 15 to the code and also 0 (the code becomes 3150);
'd' — is the 4-th letter of the alphabet. Consequently, Polycarp adds 4 to the code (the code becomes 31504);
'e' — is the 5-th letter of the alphabet. Therefore, Polycarp adds 5 to the code (the code becomes 315045).
Thus, code of string code is 315045.
You are given a string t resulting from encoding the string s. Your task is to decode it (get the original string s by t).
- 입력
The first line of the input contains an integer q (1≤q≤10^4) — the number of test cases in the input.
The descriptions of the test cases follow.
The first line of description of each test case contains one integer n (1≤n≤50) — the length of the given code.
The second line of the description of each test case contains a string t of length n — the given code. It is guaranteed that there exists such a string of lowercase Latin letters, as a result of encoding which the string t is obtained.
- 출력
For each test case output the required string s — the string that gives string t as the result of encoding. It is guaranteed that such a string always exists. It can be shown that such a string is always unique.
예제 입력1 | 예제 출력1 |
9 6 315045 4 1100 7 1213121 6 120120 18 315045615018035190 7 1111110 7 1111100 5 11111 4 2606 |
code aj abacaba ll codeforces aaaak aaaaj aaaaa zf |
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main() {
fastio;
int tc, sz;
string str, tmp;
cin >> tc;
while(tc--){
cin >> sz >> str;
stack<char> st;
for(int n = sz - 1 ; n >= 0 ; n--){
if(str[n] == '0'){
tmp = str.substr(n - 2, 2);
st.push(stoi(tmp) + 'a' - 1);
n -= 2;
}
else{
st.push(str[n] - '0' + 'a' - 1);
}
}
while(!st.empty()){
cout << st.top();
st.pop();
}
cout << endl;
}
return 0;
}