一道纠结&&有趣的水题

分类：杂七杂八 | 标签： ACM,密码 | 浏览次数：362

话说下面要写的已经是很久远的事情了，但我一想起比赛那天把它A掉就有点兴奋。 所以……

这是HUST(华中科大)4月5号Monthly的G题：

Uiwurerirexb jeqvad

Time Limit: 1 Sec Memory Limit: 128 MB
Submissions: 499 Solved: 209

Description

Fmur lan oxbrvu mzx, E abpxcay Jvmffabza qdxwfaou eb vmjsad.xdz, eb nvejv rvada mda ombc jdcqrxzdmqvc qdxwfaou. Moxbz rvaua qdxwfaou rvada mda ombc iuebz uiwurerirexb jeqvad oarvxy. Rx sbxn oxda mwxir er, E nabr rx Neseqayem:

Eb jdcqrxzdmqvc, m uiwurerirexb jeqvad eu m oarvxy xl abjdcqrexb wc nvejv iberu xl qfmebrakr mda daqfmjay nerv jeqvadrakr mjjxdyebz rx m dazifmd ucurao; rva “iberu” omc wa uebzfa farradu (rva oxur jxooxb), qmedu xl farradu, rdeqfaru xl farradu, oekridau xl rva mwxta, mby ux lxdrv. Rva dajaetad yajeqvadu rva rakr wc qadlxdoebz mb ebtadua uiwurerirexb.

Uiwurerirexb jeqvadu jmb wa jxoqmday nerv rdmbuqxuerexb jeqvadu. Eb m rdmbuqxuerexb jeqvad, rva iberu xl rva qfmebrakr mda damddmbzay eb m yelladabr mby iuimffc giera jxoqfak xdyad, wir rva iberu rvaouaftau mda falr ibjvmbzay. Wc jxbrdmur, eb m uiwurerirexb jeqvad, rva iberu xl rva qfmebrakr mda darmebay eb rva umoa uagiabja eb rva jeqvadrakr, wir rva iberu rvaouaftau mda mfraday.

Rvada mda m biowad xl yelladabr rcqau xl uiwurerirexb jeqvad. El rva jeqvad xqadmrau xb uebzfa farradu, er eu radoay m ueoqfa uiwurerirexb jeqvad; m jeqvad rvmr xqadmrau xb fmdzad zdxiqu xl farradu eu radoay qxfczdmqvej. M oxbxmfqvmwarej jeqvad iuau lekay uiwurerirexb xtad rva abreda oauumza, nvadamu m qxfcmfqvmwarej jeqvad iuau m biowad xl uiwurerirexbu mr yelladabr reoau eb rva oauumza, nvada m iber ldxo rva qfmebrakr eu omqqay rx xba xl uatadmf qxuuewefereau eb rva Jeqvadrakr mby teja-tadum.

Rveu reoa E zeta cxi uijv m qdxwfao, eb nvejv Yaujdeqrexb, Ebqir, Xirqir, Umoqfa Ebqir mda mff jeqvadrakr, nvadamu Umoqfa Xirqir eu iuebz qfmebrakr. Xl jxidua, rveu qdxwfao eu iuebz ueoqfa uiwurerirexb jeqvad mby oxbxmfqvmwarej jeqvad.

Rx uxfta oxbxmfqvmwarej jeqvad allejeabrfc, cxi jmb dalad rx vrrq://nnn.uajdarjxyawdamsad.jxo/UJWUxftd.heq

Input

Rva ebqir jxbrmebu oifreqfa jmuau. Amjv jmua vmu xbfc xba feba – jeqvadrakr nerv bx oxda rvmb 100 jvmdmjradu.
Eb amjv jeqvadrakr, rvada mda xbfc fxnad farradu mby uqmjau.

Output

Lxd amjv jmua, xirqir xba feba – rva qfmebrakr jxddauqxbyebz rx rva ebqir. Daoaowad rvmr famta uqmjau mfxba.

Sample Input

g g g

Sample Output

q q q

HINT

Source

Hust Monthly 10.04.05/Isun

一看到这题，我就傻了：毋庸置疑这绝对不是英文，也很可能不是地球上的任何一种语言文字。 所以开始就以为是Chrome浏览器的bug，所以连刷了几遍，还是一样。 最后还把Chrome重启了一遍，显然还是一样。

既然全篇都是英文字母，所以极有可能是经过了加密的英文题面。 又因为不可能搞很高级的加密方法，所以：果断猜测这个加密不过是在26个字母中建立的一个映射。 但这个映射是怎么弄的？

其实最容易发现的一个突破口是Description的结尾处，明眼人都知道这是一个URL。所以前面部分肯定对应着http://www。这样就知道了：密文中的v对应着原文的(下用”->”代替)h，r->t，q->p，n->w。再根据

四个字母已经破解出来了，接下来有点迷茫了，直接从头看Description是肯定一点办法都没有的，因为根本不知道这个题目是讲什么的。 于是我们只能根据现有的四个现成的密钥下手。

我果断看到Input，为什么先看它？很简单，因为acm的Input有些话都是一种程式了。”ebqir”根据q->p,r->t，所以这个单词就是”input”，进而又得出几个密钥：e->i,b>-n,i->u。 Rva，因为得出了Rv->Th，所以，显然它就是”The”了，这样又得出了a->e。 jmuau和Amjv很好弄，a->e,v->h和jmuau的构造再结合Amjv一起验证得出两个就是”cases”和”Each”，得出j->c,m->a,u->s。而后的oxda rvmb是一组，考虑到后面紧跟着100，所以这里应该是数据规模的限定。的确，就是”more than”，因为a->e,r->t,v->h等等，得出o->m,x->o,d->r。继而根据前面得出的，jvmdmjradu就是characters。这半句话的意思就是“不超过100个字符”，合情合理。

Eb amjv=In each，jeqvadrakr暂时猜不出。 之后的farradu已经很明显：只有f不知道了，所以这个单词是letters，又得出f->l。跳过mby，uqmjau已经得出来是spaces了。明显spaces和letters是并列关系，所以mby=and，由此又得出y->d。O(∩_∩)O哈哈~

再看Output，跳过Lxd，amjv jmua是each case了，而且Lxd=?or，所以Lxd=For。l->f。xirqir=output(这个可以证明前面推理的正确性……)  jxddauqxbyebz=correspondin? ，只有可能是corresponding了，这也跟前面的xba feba(=one line)联系起来。 所以：z->g。Daoaowad=Remem?er，显然是Remember，w->b。 Daoaowad rvmr famta uqmjau mfxba.=Remember that leave spaces alone. 太像英文了，内牛满面……

让我们回顾一下前面得出的密钥：

已经完成了19/26。 我们完全可以用所得的密钥把整个题面大概翻译一下。就用以下的代码翻译：

#include<cstdio>
char code[30]={"en ril  uc fawm pt  shbodg"};
int main()
{
    char c;
    while (scanf("%c",&c)>0)
    {

        if (c>='a' && c<='z') putchar(code[c-'a']);
        else if (c>='A' && c<='Z') putchar(code[c-'A']+'A'-'a');
        else putchar(c);
	}
}

Description翻译出来大概是这样的：

Last few months ago, I en o ed Challenge problems in hac er.org, in which there are man  cr ptograph  problems. Among these problems there are man  using substitution cipher method. To  now more about it, I went to Wi ipedia:

In cr ptograph , a substitution cipher is a method of encr ption b  which units of plainte t are replaced with cipherte t according to a regular s stem; the “units” ma  be single letters (the most common), pairs of letters, triplets of letters, mi tures of the abo e, and so forth. The recei er deciphers the te t b  performing an in erse substitution.

Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, the units of the plainte t are rearranged in a different and usuall   uite comple  order, but the units themsel es are left unchanged. B  contrast, in a substitution cipher, the units of the plainte t are retained in the same se uence in the cipherte t, but the units themsel es are altered.

There are a number of different t pes of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed pol graphic. A monoalphabetic cipher uses fi ed substitution o er the entire message, whereas a pol alphabetic cipher uses a number of substitutions at different times in the message, where a unit from the plainte t is mapped to one of se eral possibilities in the Cipherte t and  ice- ersa.

This time I gi e  ou such a problem, in which Description, Input, Output, Sample Input are all cipherte t, whereas Sample Output is using plainte t. Of course, this problem is using simple substitution cipher and monoalphabetic cipher.

To sol e monoalphabetic cipher efficientl ,  ou can refer to http://www.secretcodebrea er.com/SCBSol r. ip

这样，基本上可以断定这段话是一个好奇并且对密码充满兴趣的人的故事。根据最后一段To sol?e，可以断定是”去解决”，即To solve，又得出新的密钥t->v，后面的efficientl?显然就是efficiently，于是c->y。 所以第一段开头的话是I enjoyed Challenge problem… 所以p->j。 第一段的最后一句话又很显然是I went to Wikipedia(维基百科)，所以s->k。

文中多次出现te t结构，结合题意、上下文，肯定是text，所以k->x。  如此这般，我们已经解决了24个字母了。 剩下的两个貌似不好确定了……

原来NC的我忽略了一个明摆着的事实——Sample Input&Output。 g->q！  如此这般，只剩h了，h->z。 Bingooooooo!!!

接下来就没难度了，修改上面的代码就可以了。

#include<cstdio>
char code[30]={"enyrilqzucxfawmjptkvshbodg"};
int main()
{
    char c;
    while (scanf("%c",&c)>0)
    {

        if (c>='a' && c<='z') putchar(code[c-'a']);
        else putchar(c);
	}
}

PS1.这题做之前的确有蛮想死，不过边做，得到的越多，就越兴奋。 到最后全部解出来，爽得要死~

PS2.这是一道跟算法没有任何联系的题，考的是你的耐磨度、经验和英语能力。

PS3.不懂编程没关系，撇开代码看就是了。

PS4.这不算结题报告吧，我还没到写结题报告的程度。 纯粹写着玩玩，哈哈~

PS5.有兴趣的可以把题目再完整的翻译一次，确实比较无语。