puzzleup 2016

lugionline

〇〇 发表于 2016-9-1 18:13
如果把100改为1000呢,改为10呢

一样的吧，我是先算最小值，然后用100减一下，这样出来的就是最大值了

solomon_007

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

还有这样的一个网站 牛X!

〇〇

solomon_007 发表于 2016-9-1 16:37
我这才明白你的意思， 确实，这是象NEWKID那样的尝试猜测。。。

完全有可能存在另一个集合，总个数 ...

很多竞赛题看似可以用贪心法，其实贪心法得不到最优解，原因是每一步的选择对其他步骤有影响。
数字三角形问题：有一个数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过的数的最大值。

    1
   6 3
  8 2 6
2 1 6 5
3 2 4 7 6
如果用贪心法，每次向最大的方向走，得到结果为1+6+8+2+3=20。可是明明还有另一条路，1+3+6+6+7=23。
问题出在哪？每次的选择对后面的步骤会有影响！第三级选了8，就选不到第四、五级较大的数了。

solomon_007

〇〇 发表于 2016-9-2 09:19
很多竞赛题看似可以用贪心法，其实贪心法得不到最优解，原因是每一步的选择对其他步骤有影响。
数字三角 ...

  数字三角形，这个例子简单明了，Thks!

newkid

#7
DICE PRODUCTS

There is a six-sided die with distinct positive integers on each side. Whenever it is thrown four times, it is guaranteed that the product of the four results can be divided by the sum of the numbers on six sides.

What can be the minimum sum of the numbers on six sides?


有一个六面的骰子，每一面的正整数各不相同。每当它被抛出四次，它一定可以保证四个结果的乘积可以被这六个面上的数字之和整除。

这六个面上的数字之和的最小值是什么？

-----------
猜测 81, 楼下请继续。

〇〇

abcd%(a+b+c+d+e+f)=0
and
abce%(a+b+c+d+e+f)=0
...

lugionline

这题不难吧， SQL应当也毫无压力
Out[7]= {3, 3}
Out[8]= {{dice -> {6, 9, 12, 15, 18, 21}, sum -> 81}}

solomon_007

〇〇 发表于 2016-9-8 05:35
abcd%(a+b+c+d+e+f)=0
and
abce%(a+b+c+d+e+f)=0

呵呵，我昨晚也是这样试的，但发现4个数相乘的条件太多了，写得累

〇〇

solomon_007 发表于 2016-9-8 09:30
呵呵，我昨晚也是这样试的，但发现4个数相乘的条件太多了，写得累

这样少点
abcd%(a+b+c+d+e+f)=0 and abce%(a+b+c+d+e+f)=0 =>abc(d+e)%(a+b+c+[d+e]+f)=0
设d+e=x
=>abc(x)%(a+b+c+[x]+f)=0
同理
=>abf(d+e)%(a+b+c+[d+e]+f)=0
设d+e=x
=>abf(x)%(a+b+c+[x]+f)=0
=>ab(x)(c+f)%(a+b+c+[x]+f)=0
设c+f=y
=>ab(x)(y)%(a+b+[x]+[y])=0

〇〇

〇〇 发表于 2016-9-8 11:09
这样少点
abcd%(a+b+c+d+e+f)=0 and abce%(a+b+c+d+e+f)=0 =>abc(d+e)%(a+b+c+[d+e]+f)=0
设d+e=x

with t as(select level n from dual connect by level<=400)
select * from t a,t b,t x,t y
where a.n<b.n and x.n>4*5 and y.n>3*6
and mod(a.n*b.n*x.n*y.n,(a.n+b.n+x.n+y.n))=0
and rownum<=10;

         N          N          N          N
---------- ---------- ---------- ----------
         1          2         21         24
         1          2         21         32
         1          2         21         39
         1          2         21         48
         1          2         21         60
         1          2         21         88
         1          2         21        102
         1          2         21        120
         1          2         21        144
         1          2         21        228