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

lastwinner

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

你的sql其实可以简化，对于9、8、7、6、5这5个数字，采用类推的方式找出规律
方法是任选其中x个数字，按题目要求可得出的最大数是什么？（connect by ..... and level<=x ，这样可以有效减小候选结果集的大小）
然后手工推演一下就可以出结果了

[ 本帖最后由 lastwinner 于 2010-10-21 09:57 编辑 ]

lastwinner

另外一个推论，N个数字各用两次组成的数（不需要满足题设 间隔不同 这个条件），相同数字之间间隔的位数的和一定是偶数
证明：
1、显然，当只有一个数字时，其只能形成形如AA的数，间隔为0，算偶数
2、多增加一个数字，则能形成ABBA、ABAB这样形式的数字，其间隔为2，也是偶数
3、假设当使用N个数字的时候，间隔也是偶数。将N个数字组成的数表示 N(1)N(2)N(3).....N(2n)，括号内加一个数表示下标
则在使用第N+1个数字的时候，可将该数字分两次插入位置1～2(n+1)中任何一处，如果该处已经有数字，则已有数字整体往后移动

插入后第N+1个数字后形成的新数，插入的形式无非是四种情况：
头前尾后插入，此时相当于是加了一组数包围在原数之外，由于中间包围了2N位数，于是间隔位数之和也是偶数
头前中间插入，此时相当于是一组数包围了原数的一部分，分包围了奇数个位数和偶数个位数两种情况去看。被包围的部分和不被包围的部分中，如果有一对相同的数字，则将该数字消去后，不影响整体的间隔位数和的奇偶性（容易得出结论，证明略）。
              假设包围了奇数个位数，则没被包围的也是奇数个位数；同样包围了偶数个位数，则没被包围的也是偶数个位数。而且，两边在消去各自范围内的相同数字后，被包围的和不被包围的位数一定是一样的。
              包围了奇数个位数时，每个位数的配对边所增加的位数间隔都是1，原先的数总体增加的间隔数值上等于该奇数，而被包围的这部分位数的个数，也是奇数，同时也是新插入的数的间隔位数，奇数＋奇数＝偶数。
              包围了偶数个位数时，同上推理，偶数＋偶数＝偶数。
              综上，当头前中间插入后，所有相同数字之间间隔的位数也是偶数。
中间尾后插入，类似上边，略。
均在中间插入，类推可得，略。


综上所述，推论得证。

nlrte13

这个题，手工从99878675……开始往后推，
可以得到结果：99878675432106520134

nlrte13

上个题，鹦鹉哥的方法，可以用数学归纳法证明

nlrte13

这个题，要用程序暴力，有很简单的思路，不用考虑数字大小，
想象是20个球，两个一组
{ A-A, B-B,  C-C, D-D …… }
要把它们按排成队，一个一个按顺序放，放了一组中的一个就要优先考虑另一个，
同时要满足条件不能有相同间隔数。
这样排好队以后，再把最前的替换成9，次前的替换成8，就是答案了。

要是按ABC顺序放置，那么把 A-9，B-8，C-7，就是答案。

lastwinner

写了一个验证的sql
select num, div, p1, p2, p2-p1 len, decode(count(case when p2-p1<0 then 1 else null end)over(),0,1,0) isValid,
sum(case when p2-p1>0 then p2-p1 else null end)over() sumnum
,decode(lag(p2-p1)over(order by p2-p1, div), p2-p1,0,1) isValid2  from
(select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select &a num, rownum-1 div from dual connect by rownum<=10))
where p1-p2<>0

输入你得出的数字，如果isvalid和isvalid2全为1，则说明合格
len-1就表示中间包含的数字了，目前凑出来的最大的数是 99878675432103526401


输入 a 的值:  99878675432103526401
原值    4: (select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select &a num, rownum-1 div from dual connect by rownum<=10))
新值    4: (select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select 99878675432103526401 num, rownum-1 div from dual connect by rownum<=10))

       NUM        DIV         P1         P2        LEN    ISVALID     SUMNUM   ISVALID2
---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
9.9879E+19          9          1          2          1          1         56          1
9.9879E+19          8          3          5          2          1         56          1
9.9879E+19          7          4          7          3          1         56          1
9.9879E+19          3         10         14          4          1         56          1
9.9879E+19          2         11         16          5          1         56          1
9.9879E+19          0         13         19          6          1         56          1
9.9879E+19          5          8         15          7          1         56          1
9.9879E+19          1         12         20          8          1         56          1
9.9879E+19          4          9         18          9          1         56          1
9.9879E+19          6          6         17         11          1         56          1

已选择10行。





按p1排序了
SCOTT@lw.lw> select num, div, p1, p2, p2-p1 len, decode(count(case when p2-p1<0 then 1 else null end)over(),0,1,0) isValid,
  2   sum(case when p2-p1>0 then p2-p1 else null end)over() sumnum
  3   ,decode(lag(p2-p1)over(order by p2-p1, div), p2-p1,0,1) isValid2  from
  4  (select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select &a num, rownum-1 div from dual connect by rownum<=10))
  5  where p1-p2<>0 order by p1;
输入 a 的值:  99878675432103526401
原值    4: (select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select &a num, rownum-1 div from dual connect by rownum<=10))
新值    4: (select num,div, instr(num, div, 1, 1) p1, instr(num, div, 1, 2) p2  from (select 99878675432103526401 num, rownum-1 div from dual connect by rownum<=10))

       NUM        DIV         P1         P2        LEN    ISVALID     SUMNUM   ISVALID2
---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
9.9879E+19          9          1          2          1          1         56          1
9.9879E+19          8          3          5          2          1         56          1
9.9879E+19          7          4          7          3          1         56          1
9.9879E+19          6          6         17         11          1         56          1
9.9879E+19          5          8         15          7          1         56          1
9.9879E+19          4          9         18          9          1         56          1
9.9879E+19          3         10         14          4          1         56          1
9.9879E+19          2         11         16          5          1         56          1
9.9879E+19          1         12         20          8          1         56          1
9.9879E+19          0         13         19          6          1         56          1

已选择10行。


基本上大的数都排在前面了，而且都按从大到小排了
不折腾了，我目前找不到一个更大数了，因为没有一个更好的方法……

lastwinner

原帖由 nlrte13 于 10-10-21 10:50 发表
这个题，手工从99878675……开始往后推，
可以得到结果：99878675432106520134

SCOTT@lw.lw> select 99878675432106520134-99878675432103526401 from dual;

99878675432106520134-99878675432103526401
-----------------------------------------
                                  2993733


比我凑的大，厉害
我没脑子了

lastwinner

原帖由 nlrte13 于 10-10-21 10:57 发表
这个题，要用程序暴力，有很简单的思路，不用考虑数字大小，
想象是20个球，两个一组
{ A-A, B-B,  C-C, D-D …… }
要把它们按排成队，一个一个按顺序放，放了一组中的一个就要优先考虑另一个，
同时要满足条件不能有相同间隔数。
这样排好队以后，再把最前的替换成9，次前的替换成8，就是答案了。

要是按ABC顺序放置，那么把 A-9，B-8，C-7，就是答案。

思路是没错，但你没证明这就是最大的取法
ABCDEEDCBA也是满足你的条件的，但这样并不能得到最大的数

lastwinner

原帖由 nlrte13 于 10-10-21 10:51 发表
上个题，鹦鹉哥的方法，可以用数学归纳法证明

253# 已经证明了，但是我没证明出这就是最大的……

nlrte13

原帖由 lastwinner 于 2010-10-21 11:13 发表



思路是没错，但你没证明这就是最大的取法
ABCDEEDCBA也是满足你的条件的，但这样并不能得到最大的数

ABCDEEDCBA不符合我的条件，首先，放了A以后，按我条件要优先考虑配对的另一个A，AA显然是合理的，所以第二位要也要放A