Постановка задачи
Кодер кодирует первые16строчных букв английского языка, используя 4 бита каждая. Первый бит (слева) кода равен 0, если буква находится среди первых 8 букв, иначе он равен 1, что означает, что она находится среди последних 8 букв. Второй бит кода равен 0, если буква находится среди первых 4 букв из тех 8 букв, которые были найдены на предыдущем шаге, иначе это 1, что означает, что она находится среди последних 4 букв из этих 8 букв. Точно так же третий и четвертый биты обозначают половину, в которой находится буква.
Например, буква j будет закодирована как:
- Среди (a,b,c,d,e,f,g,h || i,j,k,l,m,n,o,p) j появляется во второй половине. Таким образом, первый бит его кодировки равен 1.
- Теперь среди (i,j,k,l || m,n,o,p) j появляется в первой половине. Таким образом, второй бит его кодировки равен 0.
- Теперь среди (i,j || k,l) j появляется в первой половине. Таким образом, третий бит его кодировки равен 0.
- Теперь среди (i || j) j появляется во второй половине. Таким образом, четвертый и последний бит его кодировки равен 1.
Итак, кодировка j — 1001,
Дана двоично закодированная строка S длиной не более 105, декодируйте строку. То есть первые 4 бита — это кодировка первой буквы секретного сообщения, следующие 4 бита кодируют вторую букву и так далее. Гарантируется, что длина строки кратна 4.
Вход:
- Первая строка входных данных содержит целое число T, обозначающее количество тестовых случаев.
- Первая строка каждого теста содержит целое число N — длину закодированной строки.
- Вторая строка каждого теста содержит закодированную строку S.
Вывод:
Для каждого тестового примера выведите декодированную строку в отдельной строке.
Ограничения
- 1≤T≤10
- 4≤N≤105
- Длина закодированной строки кратна 4.
- 0≤Si≤1
Подзадачи
- 100баллов : исходные ограничения.
Пример ввода:
3
4
0000
8
00001111
4
1001Пример вывода:
a
ap
jОбъяснение:
- Пример1:
Первый бит равен 0, поэтому буква лежит среди первых 8 букв, то есть среди a,b,c,d,e,f,g,h. Второй бит равен 0, поэтому он лежит среди первых четырех из них, т. е. среди a, b, c, d.
Третий бит равен 0, поэтому он снова лежит в первой половине, т. е. это либо a, либо b. Наконец, четвертый бит также равен 0, поэтому мы знаем, что это буква a.
- Пример2:
Каждые четыре бита соответствуют символу. Как и в примере 1, 0000 эквивалентно aa. Точно так же 1111 эквивалентно p. Итак, декодированная строка — это ap.
- Пример3:
Первый бит равен 1, поэтому буква лежит среди последних 8 букв, т.е. среди i,j,k,l,m,n,o,p. Второй бит равен 0, поэтому он лежит среди первых четырех из них, то есть среди i,j,k,l.
Третий бит равен 0, поэтому он снова лежит в первой половине, т. е. это либо i, либо j. Наконец, четвертый бит равен 1, поэтому мы знаем, что это буква j.
Код (решение)
Код реализован на Java.
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
while(n--!=0){
int size=Integer.parseInt(br.readLine());
String str=br.readLine();
String s="";
String ans="";
for(int i=0;i<size;i=i+4){
if((i+4)==size)
s=str.substring(i);
else
s=str.substring(i,i+4);
int start=0;
int mid=0;
String arr="abcdefghijklmnop";
int end=arr.length();
String a="";
for(int j=0;j<s.length();j++){
if(s.charAt(j)=='0'){
mid=(start+end)/2;
a=arr.substring(start,mid);
end=mid;
}
else{
mid=(start+end)/2;
if(end==16)
a=arr.substring(mid);
else
a=arr.substring(mid,end);
start=mid;
}
}
ans=ans+a;
}
System.out.println(ans);
}
}
}
Надеюсь, вам понравилась статья. Пожалуйста, поставьте 50 аплодисментов этой статье и подписывайтесь на меня, чтобы не пропустить новые блоги, связанные с программированием.
Ссылки
