放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

破解东京大学2013年招生海报谜题

前文已经说过了,201^^3是个天文数字,肯定不需要计算的。一般ACM里遇到了大数,那肯定是有周期性的,最后往往求mod解决。注意到前面的密匙“THEUNIVERSITYOFTOKYO”本身就是一个周期,于是hankcs用自己的魔方程序跑了下,发现了周期。

我们定义每次旋转魔方(比如执行T)为1步,让程序按照密匙一直旋转,发现20160步后魔方还原了,那么此20160就是周期。也就是说在20160步内肯定已经破解了此魔方,假设是在第n * 20步(20是密匙的长度)的时候破解了,那么剩下的201^^3 – n * 20 步都是耍花招骗人的。由于密匙有长度20,需要将周期除一下:20160 / 20 = 1008。

问题归结于求n,由周期性可知n = 201^^3 % 1008。

hankcs并不了解数论,但是还是搜索到一个有用的公式:

(a * b) % c = ((a % c) * (b % c)) % c

看到这里hankcs明白201^^3 % 1008仍然含有一个大数,大数怎么办?还是一板斧,找周期!hankcs编写了一段程序求解201x % 1008(x = 1 …… 1024)并从中发现了周期规律:

201
81
153
513
297
225
873
81
153
513
297
225
873

从第二个余开始都在重复着周期为6的周期串。hankcs并不了解数论,所以这里只是依据“现象”推断这就是一个周期串。如果读者朋友能够证明的话,请一定赐教。今天发现这个完全可以用数学归纳法证明……

那么问题进一步简化为201201 % 6 等于多少的问题。不过201201仍然是个大数,怎么办?仍然靠周期一板斧!继续用前面的程序求解201x % 6(x = 1 …… 1024)并从中发现了周期规律:

3
3
3
3
3
3
3
3
3
3

这下不用我说明了,201x % 6 = 3是板上钉钉的事情了。

于是201^^3 % 1008 = 第一个列表中第 (201x % 6 – 1) % 6 + 1 = 2 个数(先减一后加一是因为周期从第二个数开始),也就是153,n = 153 !没有严密的证明,浪人的剑法只要夺命就好了。

于是重复153次密匙,也就是旋转153 * 20 = 3060 步就能破解魔方,将3060代入魔方程序解出最终结果:

Cong
ratu
lati
ons!
Follow the link.
http://www.is.s.
u-tokyo.ac.jp/is
t_ueno_yuuka
Grad
Sch
of
IST

看来谜题的答案就是让我Follow the link. http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka ,于是hankcs复制此url到地址栏回车,结果看到:

破解东京大学2013年招生海报谜题2.png

这句话的意思是,已结束这个页面的公开展示。想想也不奇怪,海报是5月份贴出来的,现在都11月份了。反正我破解了这个谜题,这就是我要的结果。

昨天晚上开始熬夜到2点,上午精读课上终于解明此题的时候,hankcs简直要无视讲台上的石津先生狂笑起来。也许这个简陋的画面对hankcs来说,胜于一切红颜:

破解东京大学2013年招生海报谜题3.png

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 破解东京大学2013年招生海报谜题

评论 27

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #15

    转起来,找找其他年份的招生海报,很有意思!

    yuandj2年前 (2022-06-08)回复
  2. #14

    胜于一切红颜, 哈哈,口是心非了吧,你是没遇到红颜。

    yuandj2年前 (2022-06-08)回复
  3. #13

    很有趣味性~不错,好好膜拜下~

    DArren7年前 (2017-07-04)回复
  4. #12

    特意来膜

    陽炎零8年前 (2016-05-12)回复
  5. #11

    找到魔方的周期后就可以用快速幂了 不过博主的做法明显更体现能力

    18年前 (2016-01-26)回复
    • 我之前没想清楚。 即使用快速幂还是要找模运算的周期 只不过可以少找一个。因为是模运算,所以肯定有周期,所以博主的做法,我想应该算标准做法。

      18年前 (2016-01-26)回复
  6. #10

    图挂了

    38年前 (2015-12-01)回复
  7. #9

    佩服佩服

    董文宇11119年前 (2015-02-26)回复
  8. #8

    我对博主简直佩服得五体投地OTZ

    9年前 (2015-02-22)回复
  9. #7

    用的什么OCR工具? [馋嘴]

    我是来学习的10年前 (2014-09-28)回复
  10. #6

    可以用简单点的方法,既然只是旋转就不会改变任何一个字符,只是改变位置排列。结果肯定是有意义的英文单词的话,然后用程序跑下就好了(取出其中的可能的单词组合)。

    eSpin10年前 (2014-07-30)回复
  11. #5

    牛人

    JackieWang10年前 (2014-07-16)回复
  12. #4

    我已经说不出话了,,,,

    鸟到底hello10年前 (2014-06-23)回复
  13. #3

    关于程序方面一窍不通,但是身为一个日语学习者,我翻来翻去发现怎么所有的文都是一个作者,啦啦啦,这个网站是你一个人在运作咩?所以,上外都生活着一群怎样的人儿啊~~!! [good]

    阳夏10年前 (2014-06-16)回复
    • 因为这是我的个人博客呀,当然是我一个人在写东西啦。上外的大家嘛,都是从外表到内心都很美丽的一群人呢 [飞吻]

      hankcs10年前 (2014-06-16)回复
      • 哈哈,看样子美丽的你也是三年生呢!首先谢谢你的回复啦•﹏•每次懒得查字典预习的时候就跑过来偷笔记,阿里嘎头~以后还请多多关照!

        阳夏10年前 (2014-06-16)回复
        • 不客气,请多多关照~

          hankcs10年前 (2014-06-16)回复
  14. #2

    石津みなと??

    milkkk10年前 (2013-12-31)回复
    • はい、そうです。

      hankcs10年前 (2013-12-31)回复
      • 我也上过石津老师的课,老师人超好的!!

        这么说来hankcs是我的学姐… 学长… 咦?性别不明,反正叫前辈没错!

        milkkk10年前 (2013-12-31)回复
        • へー,幸会幸会!那么你是二年生么,详细的微博什么的私聊吧

          hankcs10年前 (2013-12-31)回复
          • 能求下你的微博吗~

            Joe7年前 (2017-08-15)
  15. #1

    皇上太牛逼

    比格迪克航空公司10年前 (2013-12-26)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》