puzzleup 2016

udfrog

这题应该用一个connect by就能写出来了，算法就是我们手工找的过程，但是我手头没有oracle环境...

lugionline

分支定界怎么样？
In[1]:= f[k_]:=Floor[(Sqrt[4*(4k-6)+1]-1)/2];
Table[{k,f[k],(k+k-f[k]+1)*f[k]/2},{k,2,99}]

Out[2]= {{2,1,2},{3,2,5},{4,2,7},{5,3,12},{6,3,15},{7,4,22},{8,4,26},{9,5,35},{10,5,40},{11,5,45},{12,6,57},{13,6,63},{14,6,69},{15,6,75},{16,7,91},{17,7,98},{18,7,105},{19,7,112},{20,8,132},{21,8,140},{22,8,148},{23,8,156},{24,9,180},{25,9,189},{26,9,198},{27,9,207},{28,9,216},{29,10,245},{30,10,255},{31,10,265},{32,10,275},{33,10,285},{34,10,295},{35,11,330},{36,11,341},{37,11,352},{38,11,363},{39,11,374},{40,11,385},{41,12,426},{42,12,438},{43,12,450},{44,12,462},{45,12,474},{46,12,486},{47,13,533},{48,13,546},{49,13,559},{50,13,572},{51,13,585},{52,13,598},{53,13,611},{54,14,665},{55,14,679},{56,14,693},{57,14,707},{58,14,721},{59,14,735},{60,14,749},{61,14,763},{62,15,825},{63,15,840},{64,15,855},{65,15,870},{66,15,885},{67,15,900},{68,15,915},{69,15,930},{70,16,1000},{71,16,1016},{72,16,1032},{73,16,1048},{74,16,1064},{75,16,1080},{76,16,1096},{77,16,1112},{78,17,1190},{79,17,1207},{80,17,1224},{81,17,1241},{82,17,1258},{83,17,1275},{84,17,1292},{85,17,1309},{86,17,1326},{87,18,1413},{88,18,1431},{89,18,1449},{90,18,1467},{91,18,1485},{92,18,1503},{93,18,1521},{94,18,1539},{95,18,1557},{96,18,1575},{97,19,1672},{98,19,1691},{99,19,1710}}

应当可以去掉很大部分的工作，比方50的时候 {50,13,572} ，剩余的价值不可能超过 572

solomon_007

SQL> with t as (select level n from dual connect by level <100),
  2       s(lvl,n,sumn) as (select 1 lvl,
  3                                cast(n as varchar2(4000)),
  4                                n
  5                           from t
  6                          where n =(select max(n) from t)
  7                         union all
  8                         select s.lvl + 1,
  9                                s.n||','||t.n,
10                                s.sumn + t.n
11                           from s,t
12                          where s.lvl < 20
13                            and t.n = (select max(n)
14                                         from t
15                                        where t.n not in (select column_value  from table(pkg_split.str_split(s.n)))
16                                          and ((s.lvl + 1)*s.lvl/2) = (select count(distinct x.a+y.b)
17                                                                        from (select column_value a from table(pkg_split.str_split(s.n||','||t.n))) x,
18                                                                             (select column_value b from table(pkg_split.str_split(s.n||','||t.n))) y
19                                                                       where x.a < y.b
20                                                                        )
21                                        )
22                          )
23   select * from s
24  /
       LVL N                                                                                      SUMN
---------- -------------------------------------------------------------------------------- ----------
         1 99                                                                                       99
         2 99,98                                                                                   197
         3 99,98,97                                                                                294
         4 99,98,97,95                                                                             389
         5 99,98,97,95,92                                                                          481
         6 99,98,97,95,92,87                                                                       568
         7 99,98,97,95,92,87,79                                                                    647
         8 99,98,97,95,92,87,79,70                                                                 717
         9 99,98,97,95,92,87,79,70,61                                                              778
        10 99,98,97,95,92,87,79,70,61,47                                                           825
        11 99,98,97,95,92,87,79,70,61,47,26                                                        851
        12 99,98,97,95,92,87,79,70,61,47,26,5                                                      856
12 rows selected

〇〇

solomon_007 发表于 2016-9-1 16:11
SQL> with t as (select level n from dual connect by level

为什么每步选出的一定留下?

solomon_007

两个数的和 3，4，5。。。197,不同的值只有 195，任意两个的和不同，所以 n 取值满足： n*(n-1)/2 < 195 ，所以 n<=20

solomon_007

一个SQL 不好搞，这里 PKG_SPLIT:

create or replace package pkg_split is

  type t_tab is table of varchar2(32767);

  function str_split (p_str in varchar2, p_del in varchar2 default ',')
  return t_tab pipelined;

end;
/

create or replace package body pkg_split is

  function str_split (p_str in varchar2, p_del in varchar2 default ',')
  return t_tab pipelined
  is
  begin
    for rec in (select regexp_substr(p_str,'[^'||p_del||']+', 1, level) str
                  from dual
                connect by level <= (regexp_count(p_str,p_del) + 1) ) loop

        pipe row(rec.str);
    end loop;

    return;
  end;

end;
/

就是常用的分割字符串的函数

solomon_007

〇〇 发表于 2016-9-1 16:13
为什么每步选出的一定留下?

把这个串留着好计算两两的和不同啊

solomon_007

〇〇 发表于 2016-9-1 16:13
为什么每步选出的一定留下?

我这才明白你的意思， 确实，这是象NEWKID那样的尝试猜测。。。

完全有可能存在另一个集合，总个数比12大，又<=20，而两两相加和不等，总和比这个大。。。

lugionline

好吧，我觉得我们的直觉是正确的，贪婪就是最优解
http://oeis.org/A011185

〇〇

lugionline 发表于 2016-9-1 18:05
好吧，我觉得我们的直觉是正确的，贪婪就是最优解
http://oeis.org/A011185

如果把100改为1000呢,改为10呢