今天的最后一篇日志了，仍然是翻译的cut-the-knot。发完我就睡觉去了。

    这里已经有五种证明根号2是无理数的方法了。现在我们算是介绍第六种方法了。
    一个有限小数的平方绝对不可能变成整数，因为小数部分不可能消失。观察有限小数的小数部分最后一个数字你会发现结论是显然的，平方后它总会产生新的“最后一位”。
    下面证明，(n/m)^2不可能等于2。n/m不可能是整数，于是把它写成小数形式，而有限小数的平方不可能是整数。如果n/m不是有限小数的话，可以把它转换成另外的进制使得n/m是有限小数，因而上面的结论仍然成立。一个进制下的无限小数可能是另一个进制下的有限小数。比如，把分数n/m转化为m进制，得到的小数肯定是有限小数。

    在每一代的繁殖中，单个的阿米巴原虫有3/4的概率分裂成两个，有1/4的概率死亡（而不产生下一代）。初始时只有一个阿米巴原虫，求阿米巴原虫会无限繁殖下去的概率。
    答案在下面。









































    解答：令p为单个阿米巴原虫分裂的概率（题目中等于3/4），令P为我们要求的概率（无限繁殖的概率）。
    初始时的那个阿米巴原虫有p的概率分裂为两个，至少有一个可以无限生存下去的概率为1-(1-P)^2。那么，我们得到式子：
      P = p*( 1 - (1-P)^2 )

    化简后得到：
      p*P^2 + (1 - 2p)P = 0

    或者写成：
      P * ( pP + ( 1-2p ) ) = 0

    由于P≠0，因此pP+(1-2p) = 0，即P = (2p-1)/p

    可以看到，如果一个阿米巴原虫分裂的概率没超过1/2，那么它不可能永远生存下去无限生存下去的概率为0。在我们的题目中，p=3/4，因此阿米巴原虫无限繁殖的概率为2/3。

    最近cut-the-knot上的一些新东西比较有意思。今天下午没事干，我翻译一些我觉得好玩的和大家分享。
    上图显示了用直线将一个四分之一圆分为面积相等的两份的三种方法。这三条线段中，哪一个最长，哪一个最短？
    答案在下面。

    第一种方案的线段长度等于圆的半径；
    第二种方案的线段长度显然大于半径，因为红色线段和半径长度相等，但它还不足以平分扇形面积。
    第三种方案的线段长度显然小于半径。

因此，线段长度为②>①>③。

    今天回学校，有人说我智商降低了。我仔细想了一下，这段时间的数理思考确实少了些；但也不能说我完全废了，我还出了一次模拟赛的题呢。摆脱应试教育的思维模式后，不知道我的智商是上升了还是下降了。我开始在想如何检测我的思维是否还和原来一样敏捷。
    刚才看到OIBH上又在讨论数理逻辑，然后网上找到了这几道逻辑题来想。实践证明，我的思维能力仍然还不错。我把这些题目写在下面大家可以试一下。
    这是一类问题，这类问题的命题中包含有条件判断的形式。

Following are several problem from the island of knights and knaves where knights always tell truth whereas knaves always lie.

   1. A makes the following statement: "If I am a knight then so is B." What are A and B?
   2. Someone asks A, "Are you a knight?" He replies, "If I am a knight then I'll eat my hat". Must he eat his hat?
   3. A says, "If I am a knight then 2+2=4." Is A a knave or a knight?
   4. A says, "If B is a knight then I am a knave." What are A and B?

    人有十个手指，用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了，手指头就不够用了。当然，有人会想到还有脚趾头。搬弄脚趾头是不现实的，数手指头只需要站着比划一下就可以了，数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记，比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”，它相当于十个指头。这样，我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈，你的MM数只有两根木棒加4个手指头，于是我的MM比你的多。久而久之，人们就只接受0到9这十个数字了，再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢？那我们现在很可能正在使用八进制，数学发展起来后我们最终只接受八个数字，而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号，这里为了便于叙述，我们仍然使用阿拉伯数字的0到7来表示。于是，人类数数的方式将变为：0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,...。这里，数字8被记作10，数字64则用100代替。在这个数学世界里，6+5=13，因为6+1得到的数已经是一位数中最大的了，再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指，12进制将成为更难想像的事。在12进制中，人类会把10和11直接想成是一个“数字”。研究的进位制大于10时，大于9的数字我们习惯上用大写字母ABC来表示。这样，自然数序列里将多出两个符号A和B来，数数的方式变为...,8,9,A,B,10,11,12,...。

    我们自然会想，人类生活中究竟有没有其它的进位制呢？当然有。比如，时间和角度就是60进位制，60秒=1分。还有更怪的，计算机的储存容量单位是1024进制的，1MB=1024KB。当然，这也是有原因的。我们在研究几何时常常需要用到1/2，1/3，1/4或者1/6，我们希望这些分数在角度进制下恰好都是整数以便于运算。于是，角度的进位制就变成了60。为什么时间也是60进位制呢？因为时间和角度密切相关，你看看你的手表就知道了（别告诉我你的手表是数字型的）。为什么钟和手表又要用圆形表盘的方式来表示时间呢？其实人自古以来计算时间都是用的圆形盘面，因为地球绕太阳旋转和地球的自转使得时间具有了周期性。
    计算机使用二进制，因为计算机元件只有两种状态（开和关，或者说通电和断点），因此计算机只认0和1两个数字。1024是2的幂，又比较接近1000符合人的习惯，因此把1024当成了计算机容量的进位制。

    前段时间有人在OIBH上问，为什么纸币的面值都是1*10^n、2*10^n、5*10^n呢。有人回答说这样的货币系统可以使得某种贪心方法正确。确实有这个结论，这样的货币系统使得解决“凑钱和找零时最少使用多少张纸币”这一问题的贪心算法（不断拿最大面额的纸币）是正确。但用这一点来解释我们的问题显然是可笑的，人们首先考虑的并不是如何方便地使用最少纸币，而是如何方便地得到总面额。一个只有1元纸币和7元纸币的货币系统同样满足贪心性质，但显然傻子才会设计出这种别扭的货币系统来。因此，我的回答是“纸币的面值取10的约数，这样的话凑钱和找零最方便”。但是，有人会问，要是我们使用的进位制不是10怎么办？换句话说，如果我们使用的是23进位制，除1和本身外没有其它约数的话，又该怎样设置货币系统呢。答案非常出人意料，如果我们使用的是23进位制的话，我们很可能根本发展不出数学这门学科来。10=1+2+3+4，是前四个正整数的和；10又是2和5的积；这样的进位制非常适合数学的发展。同样地，6=1+2+3，6=2*3，因此可能正在使用六进制的昆虫们很容易发展出数学来（六足动物的数学非常强，不是有人发现了蜜蜂蜂巢的六边形样式设计是最科学的么）。大家看过《计算机中的上帝》(Calculating God)吗？那里面构造了这样一种生物：他有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体，除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的困难。而事实上，这种生物恰好又没有发展数学的必要性。他就好像人类一样，对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说，如果你眼前有3个，或者5个东西，你不需要数，看一眼就知道有多少个；但当你眼前出现的物体数目达到7个或者8个时，你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来，数目超过46后就统称为“很多”了。直接感知数目达到50甚至60多的生物个体就扮演着该种族中的僧侣角色。46这个数字对于种族的生存已经完全足够了，他们在组建部落时总会保证部落的个体数不超过这个数字。因此，这种生物不需要数数的能力，他们也就无须发展数学了。他们不知道30加30等于多少，从某种意义上说他们甚至不知道一加一等于几，因为他们头脑中根本没有数字这个概念。作为一种补偿，他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论，因为他们的思维不受演绎逻辑的束缚。

    下文将介绍两套进制转换的方法，然后介绍这两套方法在小数转换上的应用。更多的进位制相关应用你可以在文后的习题部分中体会到。

    在讲进位制时，大多数教材会教大家二进制和十进制如何互换。今天我就偏不这样讲，我要和那些教材讲得一样了我还不如不写今天这些东西。二进制虽然常用，但比较特殊，很可能会了二进制但仍然不会其它进制；我们今天当一回蜜蜂，看看六进制和十进制怎么互相转换。学会这个后，任意进制间的转换你就应该都会了。
    说起进位制时往往要回到最根本的一些计数方法上。这篇日志是我第237篇日志。数字“237”表示两个百，加上三个十，加上七个单位一。我们把它们分别叫百位、十位和个位，同一个数字在不同数位上表示的实际数量不同。用一个式子表示上面的意思就是，237=2*100+3*10+7。这就是进位制的实际意义。
    现在，假如我是一只勤劳的蜜蜂。我写237篇日志是肯定不可能的了，因为我的数学世界里根本没有7这个数字。那就说我写了235篇日志吧。结合前面所说的东西，“十位”上的数表示有多少个6，“百位”上的数表示有多少个36（后面提到的十位、百位打引号表明这不是十进制中的“十”和“百”）。于是，六进制下的235就应该等于2*6^2+3*6+5。这个算式你用什么进制算出答案就相当于把六进制中的235转换为了什么进制。不过你要把这个式子当成别的进制算是不大可能的，算之前你估计得重新背一遍乘法口诀表（注意我为什么不说是“九九”乘法口诀表）。这就是我们为什么一般只研究十进制与其它进制互换的原因。我们用熟悉的十进制进行计算，得出2*6^2+3*6+5=72+18+5=95。这是按定义进行进制转换的方法。六进制的235等于十进制的95，我们记作(235)6=(95)10。那个6和10是下标，应该像H2O的2一样小小地写在下面。我就懒得排版了，反正转贴个几次就成Plain Text了。
    下面的任务是，考虑怎么把(95)10变回(235)6。使用六进制计算13*10+5可以得到235（十位上的9相当于六进制中的13），但我们说过六进制计算很麻烦。下面我们给出一种把十进制转换为六进制的方法，仔细思考你会发现这种方法显然是正确的。我们把所有6的幂从小到大写出来：1,6,36,216,...。216远远超过95了，因此95的六进制不可能是四位数。95里面有两个36，因此在最高位上写个“2”。去掉两个36，95里只剩23。23里有三个6，数字3将填写在第二位上，去掉这三个6最后所剩的5留给最末位。换句话说，我们不断寻找最大的x使得6^x不超过当前数，当前数减去6^x并在右起第x+1位上加一。这事实上是前面六进制转十进制的逆过程。
    上面的进制互换方法是一套方法，这是我们所介绍的第一套方法。这套方法的特点是正确性很显然，但是计算比较复杂，又费马达又费电。我们需要一个计算更方便的进制转换方法。下面介绍的就是进制转换的第二套方案。

    再一次回到一个很基础的问题：在十进制中，为什么乘以10相当于在数的末尾加一个0？我们同样会联想到位运算：为什么二进制左移一位（末尾加一个0）相当于乘以2？事实上，这个结论普遍存在于所有进位制中：k进制数的末尾加个0，相当于该数乘以k。证明方法非常简单，乘以一个k就相当于进位制展开式的每个指数都加一，也就相当于所有数字左移一位。六进制235=2*6^2+3*6+5，乘以6的话式子将变为2*6^3+3*6^2+5*6，也即2350。利用这个性质，六进制235可以很快转为十进制：235相当于2后面添0，加上3，再添一个0，再加上5，写为算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展开来，得到的式子和前面的那种计算方法(2*6^2+3*6+5)一模一样，但这里的计算方式更简便一些。如果写成程序，六进制字符串t转为十进制数a只需要一句话就可以完成：
for i:=1 to length(t) do a:=a*6+ord(t[i])-48;
    使用这种方法将十进制变回六进制是一个彻头彻尾的逆向操作：当前数不断除以6并把余数作为新的最高位。比如，95除以6等于15余5，余数5就是个位，15除以6的余数3作为“十位”，最终的商2是“百位”。这叫做短除法，是最常见的方法，网上随处可见。

    下面说一下进位制中的小数。前面的东西如果理解了，小数进制的转换将顺理成章地进行下去。六进制中的0.1相当于十进制的1/6，因为六进制中的0.1、0.2、0.3、0.4、0.5五个数把区间0到1均分为了6分。同样地，(0.05)6=(5/36)10。你会发现，一个“十分位”代表1/6，一个“百分位”代表1/6^2，之前的很多结论仍然成立。六进制小数12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3)，通过负指数把进制转换的整数部分和小数部分联系在了一起。(12.345)6转为十进制后居然变成了无限小数，其实这并不奇怪，这只是一个约数的问题：同样是三分之一，在我的六进制下正好分干净(0.2)，但在你十进制下就总也分不完，总要剩一点留给下一位(0.333333...)。这里有一些小数进制转换的实例。可以看到，一个进制下的有限小数很可能是另一个进制下的无限循环小数。另一个有趣的例子在这里。
    既然前面所说的第一套方法中六进制转十进制对于小数仍然成立，那么第一套方法的十进制转六进制也可以直接在小数上使用。如果你嫌无限小数很别扭，用分数进行操作是一种不错的选择。具体操作方法和前文叙述一模一样。针对纯小数的进制转换，我们把前文的描述换种方法再说一遍：不断寻找最小的正整数x使得1/6^x不超过当前数，当前数减去1/6^x并在小数点后第x位上加一。我就不再举例子了，下面主要讨论第二套方法在小数上的应用。
    我们曾说过，在k进制末尾加0相当于该数乘以k。可惜这对小数没有用，小数后你加它八百个“0”这个数仍然不变。其实，“末尾加0”只是这种性质反映在整数上的一种现象而已，我们还需要看到更本质的东西（还记得高二哲学么）。考虑到小数的乘k和除k，不难想到这种性质的实质是小数点的移动，整数的末尾加0其实是小数点向右移动一位的结果。显然小数也有类似的结论：将k进制小数的小数点左移一位，相当于该数除以k。比如，十进制中3.14除以10就变成了0.314。结论的证明和原来完全相同：除以k后展开式中的指数全部减一，相当于所有数右移一位。有了这个结论，我们的方法就出来了。来看六进制12.345如何转换为十进制。由于这种方法对整数和小数的处理方法有一些不同，转进制时我们通常对整数部分和小数部分分别进行操作。先把12转成十进制的8，然后单独考虑小数部分。0.345可以看作是数字“5”的小数点左移，加上4后小数点再次左移，再加上3并最后一次左移小数点；写成算式即((5/6+4)/6+3)/6。展开这个式子，实质与前面的方法仍然一样。小数部分十进制转六进制依然是彻头彻尾的逆向操作：当前数不断乘以6并取出整数部分写下来。
    这里有一个实例供大家参考，这个例子中的进制转换保证不涉及无限循环小数。1/4在十进制和六进制下的表示肯定都是有限小数，因为4的唯一一个因子2同样也是10和6的因子。先看0.25怎么变成六进制：0.25*6=1.5，取出1，留下0.5；0.5*6=3，没有小数部分了，因此(0.25)10就等于(0.13)6。现在我再把它变回去：(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。这不是彻头彻尾的逆操作吗？

    每年NOIp前总有人问负进位制。事实上，如果你搞清了上面的问题，负进位制将非常好理解。负进位制有一个非常奇特的功能：它可以表示出负数但不需要用负号。一个负进制数可能是负数，也可能是正数。比如，负六进制下的12等于十进制下的-4，而负六进制下的123等于1*(-6)^2+2*(-6)^1+3，即十进制下的27。是正是负取决于位数的奇偶：若该数有偶数位，则该数为负数；若有奇数位，则该数为正数。原因很简单，小数点每右移一位，相当于这个数乘以-6；从一位数开始，乘奇数次后该数的位数变成偶数且值为负，乘偶数次该数仍有奇数位且值仍为正。由于末尾添0的性质（小数点移位的性质）仍然成立，负六进制与十进制的转换依然是上面的方法：(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十进制转负六进制？还是那句话：彻头彻尾的逆操作。找到最小的非负整数x使得当前数减x能被6整除，这个x将作为新的最高位写到结果中，然后当前数减去x再除以-6。在这里我不说“余数”这个词，因为当除数为负数时对余数的定义很模糊。不再举例子了，例子都举烦了，自己把(123)-6=...=(27)10那一行倒过去看就是例子了。
    当然，还有更神奇的：-1+i进制可以表示出复数来，因为-1+i的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样，我也就不多说了。

    进位制的问题结束了。我们这里是以六进制为例进行的说明，但是不要忘记，最有趣的仍然是二进制。与二进制有关的趣味问题遍地都是。举个例子，你可以在这里的第三题看到一个二进制的经典应用。


文章最后还是那三句话：
Matrix67原创
转贴请注明出处
请大家帮忙校对

这次的错别字可能很多，因为我不是用的紫光，而是用的fcitx，没办法使用原来的词库了。
讲解也可能有漏洞，很多东西是我突然想到，即兴写下的。大家帮忙纠错啊！


附一：四道进位制练习题及其简略解答
    下面这些题目是在我公布的那个课件里的，是我收集的一些很不错的具有代表性的题目，讲课时已经用过多次了。

1. 证明：Σ(n=1 to ∞)6^( (2-3n-n^2)/2 )是无理数。
  解答：用六进制表示此数，该数显然为无理数。

2. 在哪一种进制中，35与58互质？
  解答：由于出现了数字8，因此进位制至少为9。事实上，35和58在任何不小于9的进位制下都互质，因为辗转相减不会出现“不够减”的情况，任何进制下最终都得1。

3. 证明：没有一种进制使三位数aaa恰等于a^3。
  解答：设此数为k进制，则ak^2+ak+a=a^3。此方程无整数解。

4. 在哪一种进制中，792可以被297整除？
  解答：这道题目非常有趣。在任何一种进制下，200的四倍都已经超过792，300的两倍都还不足792。那么，792只可能是297的三倍。设进位制为k，问题转化为解方程7k^2+9k+2=3*(2k^2+9k+7)。



附二：进位制笑话不完全收集:)

1. What would the value of 190 in hexadecimal BE?

2. If only DEAD people understand hexadecimal, how many people understand hexadecimal?

3. There are only 10 types of people in the world — those who understand binary, and those who don't.

4. There are only 10 types of people in the world — those who understand trinary, those who don't, and those who mistake it for binary.

5. Why do mathematicians think Halloween and Christmas are the same? Because 31 Oct = 25 Dec.

之所以没公布标程，是因为个人觉得标程写得比较丑。
既然有人需要就发布一下吧，标程丑总比没有标程好。

Problem 1
program whyleast;

procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====}
var
   n,i:integer;
   ans:longint=1;
begin
  assign(input,'whyleast.in');
  reset(input);
  assign(output,'whyleast.out');
  rewrite(output);
  
  readln(n);
  for i:=1 to n do ans:=ans*3;
  writeln(ans-1);
  solve(n,1,3);
  
  close(input);
  close(output);
end.



Problem 2
program height;

const
   OutputString:array[boolean]of string=('YES','NO');

type
   rec1=record
          h,p:longint;
        end;

   pointer=^rec2;
   rec2=record
          x,y:longint;
          dir:boolean;
          next:pointer;
        end;
var
   orderHeight : array[1..100000]of longint;
   SortHeight  : array[1..100000]of rec1;
   Deg,DegHash : array[0..100000]of longint;
   EdgeHash    : array[1..100000]of pointer;
   n,m,DegCount:longint;

procedure SwapRec(var t1,t2:rec1);
var
   t3:rec1;
begin
   t3:=t1;
   t1:=t2;
   t2:=t3;
end;

procedure SwapInt(var t1,t2:longint);
var
   t3:longint;
begin
   t3:=t1;
   t1:=t2;
   t2:=t3;
end;

function InsertEdgeHash(x,y:longint):integer;
var
   newp:pointer;
begin
   new(newp);
   newp^.x:=x;
   newp^.y:=y;

   if orderHeight[x] > orderHeight[y] then
      newp^.dir:=( 1.25*OrderHeight[y] <= orderHeight[x] )
   else newp^.dir:=( 1.25*OrderHeight[x] > orderHeight[y] );
   newp^.dir:=not newp^.dir;

   newp^.next:=EdgeHash[x];
   EdgeHash[x]:=newp;
   exit( ord( newp^.dir ) );
end;

function FindEdgeHash(x,y:longint):integer;
         { -1: Not Found;  0: x-->y  1: x<--y
            x Always Smaller than y }
var
   now:pointer;
begin
   now:=EdgeHash[x];
   while now<>nil do
   begin
      if now^.y=y then
      begin
         now^.dir:=not now^.dir;
         exit( ord( now^.dir ) );
      end;
      now:=now^.next;
   end;
   exit(-1);
end;

procedure UpdateDeg(t,c:longint);
begin
   if deg[t]<>c then
   begin
     dec(DegHash[Deg[t]]);
     if DegHash[Deg[t]]=0 then dec(DegCount);
     inc(DegHash[c]);
     if DegHash[c]=1 then inc(DegCount);
     Deg[t]:=c;
   end;
end;

procedure ReadHeight;
var
   i:longint;
begin
   readln(n,m);
   for i:=1 to n do
   begin
      readln(OrderHeight[i]);
      SortHeight[i].h:=OrderHeight[i];
      SortHeight[i].p:=i;
   end;
end;

procedure Sort(l,r:longint);
var
   i,j,mid:longint;
begin
   i:=l;
   j:=r;
   mid:=SortHeight[(i+j)div 2].h;
   repeat
      while SortHeight[i].h<mid do inc(i);
      while SortHeight[j].h>mid do dec(j);
      if i<=j then
      begin
         SwapRec(SortHeight[i],SortHeight[j]);
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then Sort(l,j);
   if i<r then Sort(i,r);
end;

procedure Init;
var
   low:longint=1;
   high:longint=1;
   i:longint;
begin
   DegHash[0]:=n;
   DegCount:=1;
   for i:=1 to n do
   begin
      while SortHeight[low].h*1.25 < SortHeight[i].h do inc(low);
      while ( high<n ) and ( SortHeight[i].h*1.25 >= SortHeight[high+1].h ) do inc(high);
      UpdateDeg( SortHeight[i].p, high+low-i );
   end;
end;

procedure Solve;
var
   i,x,y:longint;
   dir:integer;
   newp:pointer;
begin
   for i:=1 to m do
   begin
      readln(x,y);
      if x>y then SwapInt(x,y);
      dir:=FindEdgeHash(x,y);
      if dir=-1 then dir:=InsertEdgeHash(x,y);
      if dir=0 then SwapInt(x,y);
      UpdateDeg(x,Deg[x]+1);
      UpdateDeg(y,Deg[y]-1);
      writeln( OutputString[DegCount=n] );
   end;
end;

{====main====}
begin
   assign(input,'height.in');
   reset(input);
   assign(output,'height.out');
   rewrite(output);

   ReadHeight;
   Sort(1,n);
   Init;
   Solve;

   close(input);
   close(output);
end.




Problem 3
program wolf;

type
   rec=record
          left,right:integer;
       end;

const
   infinite=maxlongint div 3-100000;
   //Make sure no overflows occur

var
   k,n,m  : integer;
   map    : array[1..1000,1..1000]of longint;
   dist   : array[1..1000]of longint;
   hash   : array[1..1000]of boolean;
   father : array[1..1000]of longint;

   tree : array[1..1000]of rec;
   attk : array[1..1000]of longint;
   cost : array[1..1000]of integer;
   minf : array[1..1000,0..100]of longint;

procedure readp;
var
   i,x,y,d:longint;
begin
   readln(k,n,m);
   for i:=2 to n do
      readln(attk[i],cost[i]);
   for i:=1 to m do
   begin
      readln(x,y,d);
      map[x,y]:=d;
      map[y,x]:=d;
   end;
end;

procedure init;
var
   i,j:longint;
begin
   for i:=2 to n do dist[i]:=infinite;
   for i:=2 to n do hash[i]:=false;
   dist[1]:=0;
   hash[1]:=true;

   for i:=1 to n do
   for j:=1 to n do
      if map[i,j]=0 then map[i,j]:=infinite;

   for i:=1 to n do
   for j:=1 to k do
      minf[i,j]:=-infinite;
end;

procedure sssp;
var
   i,j:longint;
   min:longint=0;
   minj:longint=1;
begin
   for i:=1 to n-1 do
   begin
      for j:=1 to n do if not hash[j] then
      begin
         if ( min+map[minj,j] = dist[j] ) and ( father[j] > minj ) then
           father[j]:=minj
         else if min+map[minj,j] < dist[j] then
         begin
           dist[j]:=min + map[minj,j];
           father[j]:=minj;
         end;
      end;

      min:=infinite;
      for j:=1 to n do if not hash[j] and (dist[j]<min) then
      begin
         minj:=j;
         min:=dist[j];
      end;

      tree[ minj ].right:=tree[ father[minj] ].left;
      tree[ father[minj] ].left:=minj;
      hash[ minj ]:=true;
   end;
end;

function solve(x,y:longint):longint;  //(node,cost)

   procedure update(var t1:longint;t2:longint);
   begin
      if t1<t2 then t1:=t2;
   end;

var
   ans:longint=-infinite;
   i,t:longint;
begin
   if minf[x,y]<>-infinite then exit(minf[x,y]);
   if y>=cost[x] then ans:=attk[x];

   if tree[x].left>0 then update(ans,solve(tree[x].left,y)+attk[x]);
  
   if tree[x].right>0 then
   begin
      update(ans,solve(tree[x].right,y));
      if y-cost[x]>0 then
         update(ans,solve(tree[x].right,y-cost[x])+attk[x]);
   end;
  
   if (tree[x].left>0) and (tree[x].right>0) then
      for i:=1 to y-1 do
         update(ans,solve(tree[x].left,i)+solve(tree[x].right,y-i)+attk[x]);

   minf[x,y]:=ans;
   exit(minf[x,y]);
end;

procedure writep;
var
   ans:longint=-infinite;
   i,j:integer;
begin
   for i:=0 to k do
     if solve(1,i)>ans then ans:=solve(1,i);
   writeln(ans);
  
   {===For Debug===
   for i:=1 to n do
   begin
      for j:=1 to k do write(minf[i,j]:3);
      writeln;
   end;
   for i:=1 to n do writeln(tree[i].left,' ',tree[i].right);
   }
end;

{====main====}
begin
   assign(input,'wolf.in');
   reset(input);
   assign(output,'wolf.out');
   rewrite(output);

   readp;
   init;
   sssp;
   writep;

   close(input);
   close(output);
end.




Problem 4
program garden;

const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));

type
   arr=array[1..10]of integer;
   rec=record x,y:integer;end;

var
   map:array[0..11,0..11]of boolean;
   ans:array[1..100]of rec;
   n,m,max:integer;
   step:integer=1;
   state:arr;

procedure readp;
var
   i,j:integer;
   ch:char;
begin
   readln(m,n);
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         read(ch);
         map[i,j]:=(ch='1');
         inc(max,ord( map[i,j] ))
      end;
   readln;
   end;
end;

procedure writep;
var
   i:integer;
begin
   for i:=1 to step do
      writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );
end;

procedure solve(x,y:integer);
var
   tx,ty,d:integer;
   step_cache:integer;
   state_cache:arr;
begin
   step_cache:=step;
   state_cache:=state;
   if step=max then
   begin
      writep;
      exit;
   end;

   for d:=1 to 4 do
   begin
      tx:=x+dir[d,1];
      ty:=y+dir[d,2];
      while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
      begin
         inc(step);
         ans[step].x:=tx;
         ans[step].y:=ty;
         state[tx]:=state[tx] or ( 1 shl (ty-1) );
         tx:=tx+dir[d,1];
         ty:=ty+dir[d,2];
      end;

      tx:=tx-dir[d,1];
      ty:=ty-dir[d,2];
      if (tx<>x) or (ty<>y) then solve(tx,ty);
      state:=state_cache;
      step:=step_cache;
   end;
end;

{====main====}
var
   i,j:integer;
begin
   assign(input,'garden.in');
   reset(input);
   assign(output,'garden.out');
   rewrite(output);

   readp;
   for i:=1 to n do
   for j:=1 to m do
     if map[i,j] then
     begin
        ans[1].x:=i;
        ans[1].y:=j;
        state[i]:=1 shl (j-1);
        solve(i,j);
        state[i]:=0;
     end;

   close(input);
   close(output);
end.

依然欢迎大家来挑错

注：本日志请勿转载！

    我的第一篇日记是这一年的7月10日写的，因此这一年的5月16日具体发生了什么我已经忘记了。直到看到了这一年的年度总结，我才想起这一天是如何度过的。在04年的年度总结中，我写到：

    年初，我的第一次恋爱（与ZJ）因我的过分要求和渴望、学习压力、突发事件等各方面原因而渐渐走向危险的一端，酝酿半年的感情灾难在5月份突然爆发，一年历程的感情抛物线在2003年12月31日走到最高点，在2004年5月16日落在了x轴下方。2004年5月16日，我的16岁生日的晚上22:20，我到了ZJ的楼下疯狂地呼唤她，幻想能听见她的回答。此后，我俩有意回避，直到她和我进入不同的高中。

    很遗憾，至于那天以及那天的前后到底发生了些什么，上述文字是我唯一能记起的东西。我记得我下了晚自习后快速跑到她回家的必经之路，但却没有等到她。等她的过程中我遇见了另一个同学（忘记是谁了）。后来我沿路返回，又选了另外一条路跑到了她家楼下。很久以后某天我因别的事走过与这完全相同的路线，才发现当时我跑过的路有多么长。很多人说失恋那天会下雨，这是不正确的。我记得那天没有下雨。
    根据一项不完全统计，痴情的我似乎以后注定要踏上OI之路。

    05年10月11日前日记都是在我的PDA上写的，使用的DayNotez软件。10月11日那天在学校大礼堂观看英语歌比赛时PDA撞在了椅子的金属支架上，完全坏了，此后自己用Delphi写了一个程序继续在电脑上写日记。再后来我成功抢救回了PDA上的旧日记，但有一段日记少了几个字节，这段日记包括这年5月16日的日记。
    在这篇不完整的日记里，我看到我当天起床后的第一件事是上网更改了QQ资料的年龄。这是我最后一次更改QQ资料，一个多月后我就放弃QQ开始使用MSN了。当天上午的数学任课老师发生了变动。中午妈妈送了贺卡和一块小蛋糕。下午某个可能是来上门推销的工作人员在我们班的教室安装了一套非常破的英语教学软件，作为教室电脑的管理员我整理了很久。当时我是地理科代表，正负责收书费。到了晚自习时钱仍没有收齐，自己垫钱交给了地理老师。
    晚自习看了科幻世界的一篇文章，王晋康《一生的故事》。它比起《Stories of Your Life》差远了，但我觉得WS可能会喜欢这样的软科幻。于是跑到11班教室去，把这期的科幻世界给她，推荐她看这篇文章，并在里面夹了一张纸条说想请她周末看电影。下了晚自习后我出去在校门口的小书店买了《月亮孩子》。印象中这本书我没有看完，因为我后来渐渐不喜欢看科幻小说了。日记中我写道，WS和DQ没有送我生日礼物。WS和DQ是我认识的好朋友，属于非常少有的那种很感性的女生。她们没有送我生日礼物的唯一可能的原因就是忘记或记错了我的生日。后来我告诉她们我的生日已经过了，20日她们合送了一件短袖T恤。月底我开始喜欢上DQ，年底分手，分手那天的感情记录在了这里。DQ喜欢用23这个名字，因为她的名字中有个字写出来很像数字“23”。
    日记的最后我简单地写道：“晚雨，思ZJ”。那天下了晚自习后我淋着雨站在ZJ经常出现的地方，有一种她似乎随时会出现的感觉。耳边隐隐约约听到她的声音在说，你怎么又没带伞。日记中类似的语言是最后一次出现了。曾经有人向我倾诉说他逃脱不了失恋的阴影，怎么也忘不了那个她。我告诉他，失恋的阴影消失得比你想象中的快，一年以后你将很难再想起她来。
    这可能是我心理最复杂的一个生日。

    这一天离我后来完全停课的时间恰好一个月。谁也没有想到我在这个班级只剩30天的时间了。
    日记的第一句话是“生日，无感”。和前一年恰好相反，人生最重要的一天里我竟然没有任何感慨。若不是我早上来到教室发现桌子上有一颗糖，那天我将永远不会意识到我是在度过我18岁的生日。直到现在我也不知道，那颗糖是谁放在我桌子上的。这个细节我可能永远也忘不了，或许在38岁，48岁时我还会在想当初究竟是谁送了我这个小礼物。除此之外我当天没有收到任何礼物。
    那天我和数学老师讨论了一下第二天公开课的事情，因为我要帮忙制作教学课件。下午年级需要选送一个十佳学生报上去，年级主任把我和班上的一个女生叫到了办公室。我当场把机会让给了那个女生。我只在竞赛方面得过几个破奖，然而她的文艺、主持、英语等各方面能力让她小有名气。下午三四节课年级组织看电影《雷雨》，以配合几天后的语文教学。那一个多小时我一直在睡觉，甚至还梦到了一道OI题。后来语文课上老师叫大家谈《雷雨》观后感时我什么都说不出来。
    这一天是星期二，星期二的晚上有历史听写和新的一集24。晚自习的听写我挂得很惨，这天的24倒是不错。这一年是我第一次追美剧看，原来都是下载的已经结束的剧集。这天的24已经是第五季快结束了，回想一下这个学期竟是每周一集的24陪伴我度过的。

    大家或许会注意到，在这个Blog的标签里，所有以某个人作为标签的算“小猫”最大，这个名字也在友链中排第一。不知道为什么，我对这个矮矮的小女生有一种特别的感觉，直到今天。在手机里，短信数和通话时间最多的应该就是和她了。在这一天，她和我开了一系列让我恼火的玩笑——把我的手表藏在教室里的某个角落让我找。我至今仍不知道她在这一天玩这样的游戏代表什么意思。或许是我自作多情吧，有时女生的一个随意的动作也可能会让我猜想她有没有什么意图。我竭力想装作自己对某些东西看得很轻，然而实际上陷得最深的往往就是我。

    05年的9月份我开始每天记录一个词语作为当天的“单词化日记”。这个想法可能（我也忘记了）是来自安妮宝贝的一本书的彩页，上面是一张张日历，每一天的格子里都写有一个词。虽然我喜欢这种日记形式，但我仍然巨讨厌安妮宝贝这种小女生看的东西，也很不喜欢被她这些东西搞得神经兮兮的女孩子。我很高兴看到很多网友也在进行这种“单词化日记”形式的记录。任何一件事持久做下去都是有意义的，最终会获得好评，比如那个每天照大头像照了几年的人。
    这一天的单词是“暴光”，因为我的MSN Space（那时我在用MSN Space）被一中的同学发现了。OIBH上的很多重庆的OIer，还有我的很多老同学（包括ZJ）都在一中，Blog的读者将很快不再限于我们学校的OI组和班上的同学。从这次“暴光”开始，我的Blog里个人的东西慢慢地少了，日志内容也开始面向更多的OIer。年底我申请了付费空间和国际域名，搭建了私人Blog。很多人写Blog是越写越觉得没劲，但我坚持了下来，这个Blog已经快要两岁了。
    这篇日志就是生日那天我在MSN Space上写的日志。日期是17号可能是因为我是凌晨写的。从这篇日志来看，我的18岁生日是非常普通的一天。

    凌晨2:00。
    我把所有的灯都关了，一个人躺在沙发上，望着漆黑的天花板，iPod里放着S.H.E的新专辑。眼角流出两滴眼泪，并不是因为我伤心，而是因为我困了。但我不想睡觉。这一年我做的最多的事情就是睡觉了。
    前天我回了一趟学校，高三年级要照集体照留念。遇见了理科班的那一帮兄弟，大家仍然是开玩笑地疯打了一会儿。但我悲哀地发现，我几乎无法和我们班的同学交流了。除了四五个要好的朋友外我没有和我们班其他人打招呼。我甚至发现我已经认不出一些同班同学了。
    脱离集体近一年让我真正体会到了什么叫孤独。和其它高三学生一样，我的“高三”心里也是阴暗的。我不能浪费了这些时间，于是我开始学语言，做网页，写文章。只要自己能忙起来就不会觉得孤独了。19岁生日之际，我组织了一次生日邀请赛充实了一下自己的生活，收到了有史以来最多的生日祝福。

    听完了，S.H.E的新专辑非常有个性。我从沙发上起来，打开电脑开始看新的一集Lost。其实这也不算新的一集，只是上个星期留下来的。上个星期比较忙，因此有一集Lost还没看。
    这一集Lost的主角是Ben，故事中穿插了几段Ben的回忆。这一集的故事时间正好是Ben的生日，而每一个回忆的片段都发生在Ben以前某个生日。他这一生的故事由这一串回忆拼凑了起来。很巧，今天也是我的生日。我突然想知道，我的前几个生日又发生了什么。具体我是什么时候记的日记我已经记不清了，可能16岁的时候已经在写日记了吧。16岁到18岁是成人的标志，是人生最重要的阶段，在这期间我到底做过什么？
    我翻看起我的日记来。眼前是许多一闪而过的片段。我曾经失恋，曾经淋雨，我也曾经快乐，曾经辉煌。我想起了一颗糖之谜，想起了糟糕的历史听写，想起了《雷雨》，想起了《一生的故事》……我决定写下我能记起的每一个生日里发生的事。现在我的日记有14.7万字。我希望当我的日记有100万字时我还能像今天这样书写我的故事。
    每个人都有自己的故事。


Matrix67原创
本日志请勿转载！

题目在这里：http://www.matrix67.com/blog/article.asp?id=241

如果机房马上要关门了，或者你急着要和MM约会，请看简要题解：

1. 用类似于传统hanoi的递归方法可以做到3^n-1次。这显然是最多的了，因为总的状态数也只有3^n个。
2. 可以证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, ... , n-1 。
3. 在最短路树上做树状DP，需要多叉转二叉。注意几种需要输出0的情况。
4. 搜索，算是练基本功了。用位运算优化，不加任何剪枝就能过。

否则，请慢慢阅读——

Problem 1: 为什么最少
    如果你还不熟悉Hanoi塔的解法，去题目中提到的那篇日志看看吧。如果你已经熟悉Hanoi塔的解法，你会立刻想到这道题的解法：依然是递归地解决。至于怎么递归，样例已经告诉我们了：把前n-1个金片从1号柱搬到3号柱，把第n片移到2号柱，又把那n-1片从3号柱搬回1号柱，再把第n片搬到3号柱，最后把那n-1个金片又搬过来，完成整个操作。
    我们下面解决三个问题：为什么这样不会重复出现状态，这样的移动步数是多少，为什么这样的操作步数是最多的。
    为什么这样不会出现重复的状态呢？因为我们假设前n-1个金片的移动过程中没有重复状态，而三次对n-1的调用时整个状态由于第n个金片的位置不同而不同。
    这样的方法获得的操作步数是多少呢？答案是3^n-1。我们可以用数学归纳法证明，n=1时步数为2显然正确，而f(n+1)=3f(n)+2=3*(3^n-1)+2=3^(n+1)-1。
    为什么这样的操作步数是最多的呢？废话，这样的操作步数当然是最多的，因为总的状态数也只有3^n个（每个金片的三种可能的位置确定了一种状态），你的移动步骤能比这个数目还多就见鬼了。

    这道题有人用了math库，没有提供math库导致无法编译是我的失误，向大家道歉。

    Hanoi问题的变种太多了，比如多根柱子、单向移动、双色金片等等。dd上次不是也出了一题么。

    这题代码很短，我公布在下面。
program whyleast;

procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====}
var
   n,i:integer;
   ans:longint=1;
begin
   assign(input,'whyleast.in');
   reset(input);
   assign(output,'whyleast.out');
   rewrite(output);
  
   readln(n);
   for i:=1 to n do ans:=ans*3;
   writeln(ans-1);
   solve(n,1,3);
  
   close(input);
   close(output);
end.


Problem 2: 身高控制计划
    一个竞赛图是指任两个点之间都有一条有向边的图。竞赛图有很多奇妙的性质，比如一个竞赛图必然存在一条经过所有节点的路等等。
    下面我们证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, ... , n-1 ：
    如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图继续上面的过程就得到了我们的结论。
    现在我们的算法就很明确了，首先统计初始状态下的出度，然后设计某种数据结构完成两种操作：改变一个数（加一减一），询问所有数是否恰好为0, 1, 2, ... , n-1 。
    统计初始状态下的出度方法有很多，这里介绍两个。首先对身高排序，然后对于每个人进行二分，寻找有序数列中该数的4/5和5/4各在什么地方。还有一种方法也是先排序，然后从左到右扫描整个序列，并保持两个指针始终指向4/5和5/4处。每次开始处理一个新的数时都把两个指针适当地右移直到超出了这个数的4/5或5/4为止。两种方法都是O(nlogn)。别以为第二种方法是线性的哦，线性算法之前还有一个排序呢。
    操作的处理也有不少方法。最简单的方法就是统计当前图中出度的数目有多少种。就是说，用a[i]表示出度为i的点有多少个，然后不断更新a[i]>0的有多少个。当这个数目等于n时我们就认为图中没有环（因为出度可能的取值只有从0到n-1共n种）。
    注意，由于同一条边可能被操作多次，因此需要一个Hash表（开散列）来判重。具体地说，你需要判断这条边以前被操作过奇数次还是偶数次，以决定哪边的出度要增加，哪边的出度要减小。


Problem 3: 狼的复仇

    把这个问题中所有的最短路都画出来是什么样子？它一定是一棵树！为什么？首先，图肯定是连通的，因为源点到任一个点都有一条最短路；其次，图肯定无环，因为源点到任一个点只有一条最短路（环的出现将意味着某些点有更短的路存在）。仔细想一下Dijkstra的算法过程，不难想到Dijkstra算法的实质就是在建这棵树——每一次由x节点加上边x-y扩展到y节点就记作x是y的父亲。注意观察上图中左图是如何变成右图的。这样，题目变成了这种形式：在有根树上，除根节点之外的其它节点中选择一些节点，使得这些节点和它们所有祖先的权值和最大。这是一个经典的树型动态规划模型。我们用f[i,j]表示以节点i为根节点的子树花费j个单位的材料最多可以得到多大的攻击力。令节点1的材料和攻击力都为0，那么最后输出f[1,0..k]中的最大值即可。决策分为两类，要么该位置建一个塔，要么把所有材料适当地分给儿子（自己就不需要再建了）。但这样的复杂度太高，我们需要用DP嵌套或者更巧妙的多叉转二叉来解决。
    DP嵌套理解起来更简单，它主要是解决这样一个子问题：若某个节点有m个儿子，我们需要寻找当j1+j2+...+jm等于某个定值时f[儿子1,j1]+f[儿子2,j2]+...+f[儿子m,jm]的最大值。这个子问题与我的某次模拟赛中论文课题选择那道DP题几乎是一模一样，看一看那道题就明白了。下面简单描述多叉转二叉的方法。

    如果你还不知道多叉转二叉的话，这道题是一个绝好的学习材料。一棵多叉树可以用“左儿子右兄弟”的方法转为二叉树，具体的说就是把多叉树转化为这种形式：节点的左儿子才是真正的儿子，节点的右儿子只是和它同辈的兄弟。注意看上图的左图是如何变成右图的。现在，我们的f[i,j]表示在这棵二叉树上的子树花费j个材料的最大值。它有这样五种决策：
    1. 自己把材料用了；
    2. 自己把材料用了后剩下的给右边；
    3. j个材料全部用到左边去，加上自己的权值；
    4. j个材料全部用到右边去，不加自己的权值；
    5. j个材料左边用一点，右边用一点，加上自己的权值。
    注意思考决策3-5中为什么有的决策要算自己的权值，有的不算自己的权值。转化后的二叉树并不是原来的树，左边和右边的意义是不同的。在原图中对比一下你就能看到这些决策的实质了。
    状态O(nk)个，决策为O(k)，因此这道题可以在O(nk^2)的时间内解决。

    这题有很多细节需要注意。比如，建树时如何处理多条最短路优先选择编号较小节点，解决方法是在Dijkstra的更新过程中，当新的最短路与原来相同但新的父亲比原父亲编号小时仍然要更新。还有几种特殊情况需要输出0，比如所有的花费都大于k时，再比如所有的攻击力都小于0时。


Problem 4: 和MM逛花园
    这题搜索，DFS枚举方向，没什么好说的。在这里说一下位运算优化。
    用State[x]表示第x行的状态（0表示还没走过，1表示已经走过），用Map[x,y]表示地图第x行第y列的位置是否有景点。假如当前位置是(x,y)，枚举方向d后进行下面的while循环可以飞快地确定最终状态。细心的人会发现State的储存是“反”的（和实际状态左右颠倒）。这没关系，只要State的储存一直是反的就没事了。
const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));
while Map[x,y] and ( not State[x] and (1 shl (y-1) )>0) do
begin
   x:=x+dir[d,1];
   y:=y+dir[d,2];
   State[x]:=State[x] or ( 1 shl (y-1) );
   ...
end;
    我的数据都是唯一解，因此你不用麻烦着写check了。


Matrix67原创
转贴请注明出处

大家帮忙校对，我先睡觉了