PUZZLEUP 2015

lugionline · 发表于 2015-9-11 10:01

newkid 发表于 2015-9-10 23:07
明白了，有点像以前那个猜数游戏，但是回馈信息太少了所以步骤将会很多。要证明一种策略是最少步骤是很困 ...

是啊，如果是master mind游戏，那就很好办了，这个题要在 C(256,20)里面找答案就非常困难了，如果是3个字母 C(27, 4)里面找，那SQL就能办到

这题的答案应当就在 20~24之间，我找了2个，都是24

lugionline · 发表于 2015-9-11 16:23

这是其中一个，整数规划出来的,20分钟，不过我一开始假定了有一个 DCBA ，如果不假定，2个小时都没结果

"AACA", "AACD", "ABAB", "ACAB", "ADBC", "ADDC", "BAAC", "BBBA", \
"BBDD", "BCBD", "BCDA", "BDCB", "CABB", "CADB", "CBCC", "CCCC", \
"CDAA", "CDAD", "DAAC", "DBBD", "DBDA", "DCBA", "DCDD", "DDCB"

lugionline · 发表于 2015-9-12 18:04

等的时间太少了，三个小时出结果，我每次都等到2小时就等不及中断了

n[464]:= K = 4;
F = Table[1, {K^K}];
B1 = Table[1, {K^K}];
B2 = Table[-1, {K^K}];
B3 = {Quotient[K^K , (K*K - K + 1)], -24};
LU = Table[{0, 1}, {i, 0, K^K - 1}];
R1 = Table[If[i == K, 0, 1], {i, K}];
R0 = Table[If[i == K, 1, 0], {i, K}];
S[n_] := DeleteDuplicates@Flatten@Table[
   FromDigits[PadLeft[IntegerDigits[n, K], K]*RotateLeft[R1, j] + RotateLeft[R0*i, j], K],
   {i, 0, K - 1}, {j, 0, K - 1}];
M1 = Table[If[MemberQ[S[j], i], 1, 0], {i, 0, K^K - 1}, {j, 0, K^K - 1}];
M2 = Table[If[i == j, -1, 0], {i, K^K}, {j, K^K}];
M3 = {Table[1, {K^K}], Table[-1, {K^K}]};
Timing[SOL = LinearProgramming[F, Join[M1, M2, M3], Join[B1, B2, B3], LU, Integers]]
CHRS = Map[StringJoin @@ (PadLeft[IntegerDigits[#, K], K] /. {0 -> "A", 1 -> "B", 2 -> "C", 3 -> "D"}) &, Flatten@Position[SOL, 1] - 1]
Length@CHRS

Out[475]= {9878.671875, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,
  1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}}

Out[476]= {"AACA", "ABAC", "ACBD", "ACDB", "ADBB", "ADDD", "BABC", \
"BADC", "BBCB", "BBCD", "BCAA", "BDAA", "CACA", "CBAC", "CCBB", \
"CCDD", "CDBD", "CDDB", "DAAB", "DAAD", "DBBA", "DBDA", "DCCC", "DDCC"}

Out[477]= 24

newkid · 发表于 2015-9-13 00:20

lugionline 发表于 2015-9-12 18:04
等的时间太少了，三个小时出结果，我每次都等到2小时就等不及中断了

n[464]:= K = 4;

这个确定是最优解？果然NB。
9878.671875是所用的时间？

lugionline · 发表于 2015-9-13 08:34

newkid 发表于 2015-9-13 00:20
这个确定是最优解？果然NB。
9878.671875是所用的时间？

确定是最优解，除非代码写错了，9878是计算整数规划的时间，前面构造矩阵时间基本可以忽略
关于mathematica是否牛逼可以参考这里感受一下
http://www.zhihu.com/question/27834147

newkid · 发表于 2015-9-13 10:17

lugionline 发表于 2015-9-13 08:34
确定是最优解，除非代码写错了，9878是计算整数规划的时间，前面构造矩阵时间基本可以忽略
关于mathemat ...

必须给跪！

〇〇 · 发表于 2015-9-13 17:07

newkid 发表于 2015-9-13 10:17
必须给跪！

这题太难了，完全看不懂

newkid · 发表于 2015-9-16 21:57

#8 ADDITION

A+B=C. In this operation all of the 10 digits forming these three numbers are different. What can be the maximum value for C?

Example: 324+765=1089.
But 1089 is not the maximum value.

A + B = C。在这个操作中, 构成这三个数的10位数字是各不相同的。C的最大值是什么？

例如：324 + 765 = 1089。
但1089是不是最大值。

------------
总算有个SQL可以做的题了。

solomon_007 · 发表于 2015-9-17 10:15

#8
暴力解法: 最大 6021
SQL> with t as (select level-1 n from dual connect by level <=10),
  2    t1 as (
  3  select str,to_number(substr(str,1,a)) a,to_number(substr(str,a+1,b)) b, to_number(substr(str,a+b+1,c)) c
  4 from (
  5       select replace(sys_connect_by_path(n,','),',','') str
  6          from t
  7          where level = 10
  8       connect by nocycle prior n <> n
  9       ) s,
10       (select 2 a,4 b, 4 c from dual
11          union all
12       select 4,2,2 from dual
13          union all
14       select 3,3,4 from dual
15       ) r
16 where to_number(substr(str,1,a)) + to_number(substr(str,a+1,b)) =  to_number(substr(str,a+b+1,c))
17  )
18  select *
19 from t1
20 where c = (select max(c) from t1)
21  /
STR                                                                                     A       B       C
-------------------------------------------------------------------------------- ---------- ---------- ----------
3459876021                                                                            34    5987    6021
3759846021                                                                            37    5984    6021
4359786021                                                                            43    5978    6021
4859736021                                                                            48    5973    6021
7359486021                                                                            73    5948    6021
7859436021                                                                            78    5943    6021
8459376021                                                                            84    5937    6021
8759346021                                                                            87    5934    6021
8 rows selected

lugionline · 发表于 2015-9-17 10:34

In[2]:= Last@Sort@Select[
Flatten[Table[{i + j, i, j}, {i, 10000}, {j, 100}], 1],
Length[Union @@ IntegerDigits /@ #] == 10 &]

Out[2]= {6021, 5987, 34}

[每日一题] PUZZLEUP 2015