Puzzleup 2010 比赛快开始了，大家用SQL解答啊

nlrte13

马里奥哥的算式 20+(20-4)/2*(20/2)=100
把 20 换成大于 4 的偶数，也是成立的

newkid

红嘴绿鹦哥果然强大，又会画图又会EXCEL还会SQL, ...
至于我那个公式，就是一个质朴的农民数学家从切大饼得到的灵感：
先用N条边把N个点围成大饼状。
面朝大饼，可以看到上下各一条边，不妨想像它们是平行的。剩下的N-4个点平均分布在左右两侧。把左右点两两配对，画上线，不妨也想像它们是平行的，这样共有(N-4)/2条。
至此大饼已经被切成了若干个四边形。
旋转一下，如法炮制。这“上下各一条边”共有N/2种取法。所以总共是 (N-4)/2 × N/2
加上外面的N条边，总共是 N +(N-4)/2 × N/2
只对偶数N有效。

lastwinner

质朴农民数学家的算法：  N +(N-4)/2 × N/2 = N^2/4 （N为偶数时有效）

我的累加法：
y=f(n)= 0+1+1+....+trunc(n/2)   (n>0)
当n为奇数时，y=f(n)=0+1+1+....+trunc((n-1)/2)+trunc(n/2) = 2*(1+2+...+(n-1)/2)  ..........(1)
由S=1+2+...+n=n(n+1)/2 ， 可推出 (1)式等价于
2*((n-1)/2 * ((n-1)/2+1)/2)  = (n-1)(n+1)/4=(n^2-1)/4

当n为偶数时，y=f(n)=0+1+1+....+trunc((n-1)/2)+trunc(n/2) = 2*(1+2+...+(n-2)/2)+n/2  ..........(2)
类似于1的推理， (2)式等价于
((n-2)/2*((n-2)/2+1))/2 + n/2*(n/2+1)/8 = 2n^2/8=n^2/4

嗯，相当匹配…………





SCOTT@lw.lw> select n, y1, sum(y1)over(order by n,y1) Y, decode(n/2,trunc(
n/2), (n*n)/4, (n*n-1)/4)  ck1 from (select rownum n, trunc(rownum/2) y1 from
dual connect by rownum<21);

         N         Y1          Y        CK1
---------- ---------- ---------- ----------
         1          0          0          0
         2          1          1          1
         3          1          2          2
         4          2          4          4
         5          2          6          6
         6          3          9          9
         7          3         12         12
         8          4         16         16
         9          4         20         20
        10          5         25         25
        11          5         30         30
        12          6         36         36
        13          6         42         42
        14          7         49         49
        15          7         56         56
        16          8         64         64
        17          8         72         72
        18          9         81         81
        19          9         90         90
        20         10        100        100

已选择20行。

已用时间:  00: 00: 00.04

newkid

#15 Number Pairs

We have a number that is written by using numerals exactly twice. The number of digits between each pair is different.

What is the possible maximum value for this number?

Example: 987897 is such a number (There are 3 digits between two 9's, one digit between two 8's, and two digits between two 7's).

有一个数，每一位数都出现正好两次。每一对之间的间隔位数都各不相同。这个数最大可能为多少？

例如，987897就是一个符合条件的数，两个9之间间隔3位，两个8之间间隔1位，两个7之间间隔2位，3<>1<>2

lastwinner

沙发，还没到周四呢，怎么就出来了……

lastwinner

0～9总共10个数字，每个用两次，总共20次
由于要求每个数字必须用两次，而每个两个相同数字之间的位数又要不一样
在两个相同数字之间可以不隔任何其他数的前提下（相当于之间的位数为0），可以构造出一个较大的值，即：
98765432100123456789
但这个数未必就是最大的数，我们考虑将两个9并在一起，将两个0分开，可得
99876543210123456780，两个0之间是8位数，两个9之间是0位，而其他相同数字之间的位数由于中间的0减少了一个，都变成了互不相等的奇数，因而满足题目要求，而且这是一个更大的数

先想到这里，洗澡去

newkid

我写了个SQL跑不出来，等会看看有没有希望人肉优化。

上一道题你的解法有个地方还没通：你怎么证明N+1个顶点是在N个顶点的基础上添加？为什么不可以把原来N个顶点的边拿掉一些，然后再和新加入的N+1点重新连接？

lastwinner

是的，我没有证明，我不会……
只是推演了一段之后发现了规律，所以得出公式

最多能从画法上以穷举的方式证明我的做法可以得到最多的连接（当N<=某个数时），但是无法从理论上证明这么做一定可以得到最多的连接（按此方法推演，分叉太多，人力难以完成）

lastwinner

“由于要求每个数字必须用两次，而每个两个相同数字之间的位数又要不一样”
准确的说法应是
“由于要求每个数字如果用到的话必须用两次，而每个两个相同数字之间的位数又要不一样”
——————————————————————————————————————————————————————————
接着剖析
对于形如AABBCC这样的组合，两个相同数字之间的位数的和达到最小，为0
而形如ABCCBA或者ABCABC这样的组合，两个相同数字之间的位数的和达到最大，为6
即，N个数字按每个数字必须出现两次的规则排列，两个相同数字之间的位数的和最大为N(N-1)

上面的规则将可以指引我们做一些推断，比如，假设数字分为前后不关联的两部分，前几个数字在排列的时候，两个相同数字之间的位数已经用掉了0、1、2（先不论这种情况是否存在），那后续的相同的数字的位数就至少应该是3，而且后续不同的数字至少应有N1个(N1>2)，N1满足：
3+4+5+...+N1+(N1+1)+(N1+2)<=N1(N1-1)     
=>     2N1+(N1)(N1+1)/2<=N1(N1-1)
=>     N1^2/2-7N1/2>=0
=>     N1>=7
即后续至少要有7个不同的数字组合，才能达到要求


此结论可以引导我们合理规划前后数字的距离，而不是单纯的追求大的数字放在前面，而且挨的越近越好
要是前面的N个不同的数都太靠近了，后面部分的的N1如果计算出来超过10-N，那么以这种方式组成的数字就不会达到20位，从而无法做到最大（前面已经构造出两个20位的数了）


太晚了，睡觉
newkid你继续……

newkid

N个的间隔和最大是N(N-1), 最小是N(N-1)/2 = SUM(0,1,2,3,...,N-1) 如果这个范围能再缩小就好了。现在我的SQL还是发散得厉害，16位以上就像死机一样。