Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1816
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1816
Prague Vikings?
By Maratona de Programação 2003, IME-USP 
Brazil
Timelimit: 1
Traces of an old viking civilization has been discovered around Prague, and a big amount of printed material was found near the arqueological site. As expected, the reading of this material proved to be arduous and challenging, since this civilization used a text encoding schema to avoid its knowledge to be used by its rivals.
Recently, czech researchers announced with great excitement to the press the understanding of the encoding mechanism used by those vikings. According to the researchers, the viking alphabet was made by the letters from A to Z (including letters K, W and Y).
The encoding we accomplished in the following way. Initially, it was built a list where the letter A appear in the first position, the letter B in the second, and so on, with the letters following the same order of our alphabet. Next, the text to be encoded was swept from left to right and, for each letter l found, the number of its position on the list was printed and l was moved to the start of the list. For instance, the viking encoding for the message:
A B B B A A B B B B A C C A B B A A A B C
was given by the following integer sequence:
1 2 1 1 2 1 2 1 1 1 2 3 1 2 3 1 2 1 1 2 3
The czech researchers are asking your help to build a program that receive a sequence of integers that represents an encoded message and decode it.
Input
Your program must be prepared to work with multiple instances. Each instance have the following structure. In the first line an integer m (0 ≤ m ≤ 10000) that represents the number of integers that compose the encoded text. In the next line its given, separated by white spaces, the m integers values (each value is greater or equal to 1 and less or equal to 26). A value of m = 0 indicates the end of the instances and must not be processed.
Output
For each solved instance, you must print the identifier Instancia h where h is an integer number that sequentially increases from 1. In the next line you must output the decoded text. A blank line must be printed after each instance.
| Sample Input | Sample Output |
|
21 |
Instancia 1 ABBBAABBBBACCABBAAABC Instancia 2 VEGAN Instancia 3 XXX Instancia 4 VIDALONGAAOSSTRAIGHTEDGERS |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
int x;
int inst = 1;
string s;
string aux;
while (cin >> n)
{
if (!n) break;
s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
aux = "";
cout << "Instancia " << inst++ << '\n';
for (int i = 0; i < n ; i++)
{
cin >> x;
--x;
cout << s[x];
aux.push_back(s[x]);
s.erase(s.begin() + x);
aux += s;
s = aux;
aux = "";
}
cout << "\n\n";
s.clear();
}
}
Input
1 2 1 1 2 1 2 1 1 1 2 3 1 2 3 1 2 1 1 2 3
5
22 6 8 4 15
3
24 1 1
26
22 10 6 4 13 16 16 12 5 1 4 20 1 21 21 5 10 7 16 6 15 12 5 3 8 9
0
Output
ABBBAABBBBACCABBAAABC
Instancia 2
VEGAN
Instancia 3
XXX
Instancia 4
VIDALONGAAOSSTRAIGHTEDGERS
#2 Code Example with Python Programming
Code -
Python Programming
instancia = 1
while True:
ordem = int(input())
if ordem == 0:
break
print("Instancia %d" % instancia)
instancia += 1
resposta = []
array = [i for i in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"]
entrada = [int(i) for i in input().split()]
for i in entrada:
resposta.append(array[i - 1])
antigo = array.pop(i - 1)
array.insert(0, antigo)
print("".join(resposta))
print("")
Input
1 2 1 1 2 1 2 1 1 1 2 3 1 2 3 1 2 1 1 2 3
5
22 6 8 4 15
3
24 1 1
26
22 10 6 4 13 16 16 12 5 1 4 20 1 21 21 5 10 7 16 6 15 12 5 3 8 9
0