Description

在这个有话不直说的年代, 密码学越来越被广泛接受. 我们引用经典的 “凯撒密码”. 在英文中, 凯撒加密只对 \(26\) 个字母生效 (分大小写) 我们按照 a 到 z 来排字母. 凯撒加密的原理就是把原文的每一个字母都按顺序往后移 \(K\) 位. 这个 \(K\) 将被作为密钥. (‘a’ 往后移变成 ‘b’, ‘z’ 往后移会变成 ‘a’) , 其中 \(0 \leq K \leq 25\). 现在给出一系列用凯撒 加密的英文句子, 请你编写程序逐句翻译. 也就是说, 请你确定一个密钥, 使得解码以后的文字最符合英文的规则与规范. 数据保证存在唯一的解码方案, 使得明码是完全可以分辨的 英文句子.

Input

输入一定包括 \(10\) 行每一行都是用同一密钥加密的英文.

Output

输出 \(10\) 行, 为解密结果. 不允许格式上有任何不同.

Sample Input

Welcome to the test. This is the 1st sample test case.
Vdkbnld sn sgd sdrs. Sghr hr sgd 2mc rzlokd sdrs bzrd.
Welcome to the test. This is the 3rd sample test case.
Nvctfdv kf kyv kvjk. Kyzj zj kyv 4ky jrdgcv kvjk trjv.
Govmywo dy dro docd. Drsc sc dro 5dr ckwzvo docd mkco.
Nvctfdv kf kyv kvjk. Kyzj zj kyv 6ky jrdgcv kvjk trjv.
Jrypbzr gb gur grfg. Guvf vf gur 7gu fnzcyr grfg pnfr.
Ucjamkc rm rfc rcqr. Rfgq gq rfc 8rf qyknjc rcqr ayqc.
Ckriusk zu znk zkyz. Znoy oy znk 9zn ygsvrk zkyz igyk.
Xfmdpnf up uif uftu. Uijt jt uif mbtu tbnqmf uftu dbtf.

Sample Output

Welcome to the test. This is the 1st sample test case.
Welcome to the test. This is the 2nd sample test case.
Welcome to the test. This is the 3rd sample test case.
Welcome to the test. This is the 4th sample test case.
Welcome to the test. This is the 5th sample test case.
Welcome to the test. This is the 6th sample test case.
Welcome to the test. This is the 7th sample test case.
Welcome to the test. This is the 8th sample test case.
Welcome to the test. This is the 9th sample test case.
Welcome to the test. This is the last sample test case.

Data Range

数据将从不同的方面考察. 请尽量保证程序的准确性.

每一行长度不会太短 (不少于 \(3\) 个单词的完整句). 没有全角字符和其他语言符号, 可能包含半角空格和标点.

单个测试点不超过 5kB.

Explanation

这道题用后边想都知道是密码学......

也就是说, 考虑到英文字母中最常出现的 \(8\) 个字符是 “a, s, i, n, t, o, e, r”, 最不常出现的是 “z, x, p, b, j, k, q” (只需旁边几块钱, hzwer 说的);

然后再考虑一些特判和常见单词就可以了.

但是这毕竟是一道玄学题...... 所以如果用的词汇表略大还会搞成 WA~

然后就只能膜了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define raise_condition() while (true) printf("BREAKPOINT\n")
using namespace std;
typedef long long lli;
const int maxn = 1010;

string patr[20] = {
    "we", "you", "it", "he", "they",
    "is", "are", "was",
    "the", "a",
    "on", "in", "of", "to",
    "do", "if", "and", "but", "how",
    "all"
}; // Common vocabulary
char match1[8] = {
    'a', 's','i','n', 't','o', 'e','r'
}; // Most occured letters
char match2[4] = {
    'j', 'q', 'x', 'z'
}; // Least occured letters
int weight[26]; // Weight for indifidual characters

bool is_lower(char ch) {
    return ch >= 'a' && ch <= 'z'; }
bool is_upper(char ch) {
    return ch >= 'A' && ch <= 'Z'; }
bool is_letter(char ch) {
    return is_lower(ch) || is_upper(ch); }

string right_shift(string str, int distance = 1)
{
    string ans = "";
    for (unsigned int i = 0; i < str.length(); i++) {
        if (str[i] >= 'a' && str[i] <= 'z')
            ans += (str[i] - 'a' + distance + 26) % 26 + 'a';
        else
            ans += str[i];
    }
    return ans;
}

int eval_weight(string str, int type[])
{
    // Now we have a string with only lower-case letters
    int length = str.length();
    for (int i = 0; i < 100; i++)
        str += " ";
    int sum = 0;
    // Letter judifications and special letters
    for (int i = 0; i < length; i++)
        if (is_lower(str[i])) {
            sum += weight[str[i] - 'a'];
            if (str[i] == 'i' && type[i] == 1)
                sum += 5;
        }
    // Checking vocabularies
    for (int i = 0; i < length; i++) {
        if (i <= 0 || type[i - 1] == 2) {
            for (int k = 0; k < 20; k++) {
                string nstr = patr[k];
                int nlen = nstr.length();
                // Incompatible length
                if (i + nlen >= length)
                    continue;
                // Not a whole word
                if (type[i + nlen] != 2)
                    continue;
                // Finding match
                bool found = true;
                for (int j = 0; j < nlen; j++)
                    if (str[i + j] != nstr[j]) {
                        found = false;
                        break;
                    }
                // Failure in finding
                if (!found)
                    continue;
                // One correct string matches
                sum += 4;
                break;
            }
        }
    }
    // Returning.
    return sum;
}

int T;
int type[maxn];

int main(int argc, char** argv)
{
    // Initializing weight
    memset(weight, 0, sizeof(weight));
    for (int i = 0; i < 8; i++)
        weight[match1[i] - 'a'] += 1;
    for (int i = 0; i < 4; i++)
        weight[match2[i] - 'a'] -= 2;
    // Reading data
    T = 10;
    for (int idx = 1; idx <= T; idx++) {
        // Clearing and reading
        memset(type, 0, sizeof(type));
        string str[26];
        getline(cin, str[0]);
        int length = str[0].length();
        // Retrieving type data
        for (int i = 0; i < length; i++) {
            if (is_upper(str[0][i])) {
                type[i] = 1;
                str[0][i] += 'a' - 'A';
            } else if (is_lower(str[0][i])) {
                type[i] = 0;
            } else if (str[0][i] == '\'') {
                type[i] = -1;
            } else {
                type[i] = 2;
            }
        }
        // Shifting characters
        for (int i = 1; i < 26; i++)
            str[i] = right_shift(str[0], i);
        // Evaluation
        int maxx = 0,
            res = 0;
        for (int i = 0; i < 26; i++) {
            int tres = eval_weight(str[i], type);
            if (tres >= maxx) {
                maxx = tres;
                res = i;
            }
        }
        // Output string;
        for (int i = 0; i < length; i++)
            if (type[i] == 1)
                str[res][i] += 'A' - 'a';
        for (unsigned int i = 0; i < str[res].length(); i++)
            printf("%c", str[res][i]);
        printf("\n");
    }
    return 0;
}