Algoogle

Algorithm for Programming Contest

AOJ 2584 Broken Cipher Generator

Category: AOJ Tag: implementation

Broken Cipher Generator

問題概要


’[‘と’]’で囲まれた区間は反転.
文字の前の’-‘と’+’の文だけ文字をずらす.
‘?’は計算後辞書順最小になるように決める.
これを実装しろ

解法


反転部分は再帰する.
‘?’は最後に’A’にするのがいいのは明らか.
素直に実装すればよい

コード


(2584.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

const string f = "-.+";
string seq, ans;
int n, cur;


char genc()
{
        int pm = 0, p;
        while((p = f.find(seq[cur])) >= 0) {
                pm += p-1;
                cur++;
        }
        char c = seq[cur];
        if(c == '?') return 'A';
        return ((c-'A'+pm)%26+26)%26+'A';
}

string gens(int rev)
{
        string ret = "";
        for (++cur; cur < n; cur++) {
                char &c = seq[cur];
                if(rev and c == ']') break;
                if(c == '[') ret += gens(1);
                else ret.push_back(genc());
        }
        if(rev) reverse(begin(ret),end(ret));
        return ret;
}

string solve()
{
        n = seq.size();
        ans = "";
        cur = -1;
        return gens(0);
}

bool input()
{
        cin >> seq;
        return seq!=".";
}

int main()
{
        while(input()) cout << solve() << endl;
        return 0;
}

Comments