puzzleup2012谜题，请用SQL或PLSQL解答

〇〇

猜错了
1*57*603*2849=97922979
3*59*627*0841=93333339
3*59*841*0627=93333339
1*63*507*2849=90999909

〇〇

lastwinner 发表于 2012-11-30 03:20
WITH t1 AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,'/'),'/') s
  FROM (SELECT LEVEL-1 n FROM DUAL C ...

因为全排列的时间在那里，占了总时间的90%

lastwinner

〇〇 发表于 2012-11-30 10:35
因为全排列的时间在那里，占了总时间的90%

我这里大致占用了80%的时间（48s），connect by在这里没优势
换个写法，效率提高一倍多（17s）
总时间也提高了一倍多点（从65s到29s）

WITH p AS (select rownum n from dual connect by rownum<10),
q AS (select rownum-1 n from dual connect by rownum<=10),
t as (select o1.n a, o2.n*10+o3.n b, o4.n*100+o5.n*10+o6.n c, o7.n*1000+o8.n*100+o9.n*10+o10.n d
       from p o1, p o2, p o3, p o4, q o5, p o6, p o7, q o8, q o9, p o10
       where not (5 in (o1.n, o3.n, o6.n, o10.n) and 0 in (mod(o1.n,2), mod(o3.n,2), mod(o6.n,2), mod(o10.n,2))) and
           o2.n<>o1.n and o3.n not in (o2.n, o1.n) and o4.n not in (o3.n, o2.n, o1.n)
           and o5.n not in (o4.n, o3.n, o2.n, o1.n) and o6.n not in (o5.n, o4.n, o3.n, o2.n, o1.n)
           and o7.n not in (o6.n, o5.n, o4.n, o3.n, o2.n, o1.n) and o8.n not in (o7.n, o6.n, o5.n, o4.n, o3.n, o2.n, o1.n)
           and o9.n not in (o8.n, o7.n, o6.n, o5.n, o4.n, o3.n, o2.n, o1.n)
           and o10.n not in (o9.n, o8.n, o7.n, o6.n, o5.n, o4.n, o3.n, o2.n, o1.n)
           )
SELECT a||'*'||b||'*'||c||'*'||d||'='||p
  FROM (
       SELECT * FROM (
               SELECT a,b,c,d,TO_CHAR(a*b*c*d) p
                 FROM t
               )
       WHERE p=REVERSE(p)
       ORDER BY TO_NUMBER(p) DESC
       )
WHERE ROWNUM=1;

〇〇

lastwinner 发表于 2012-11-30 20:40
我这里大致占用了80%的时间（48s），connect by在这里没优势
换个写法，效率提高一倍多（17s）
总时间也 ...

nice

newkid

真复杂，改成递归写法可能简单些。

lastwinner

newkid 发表于 2012-11-30 22:43
真复杂，改成递归写法可能简单些。

递归写法应该是能简单一些

按你的条件，过滤前的排列数量是9!×9,大概是326万
而按我的，只有5/8/9三位可以为0，这样就可以将排列数降低到100万
再加上不能出现5和偶数乘积的情况，排列数就降低到60多万了
这无疑大大降低了计算量

newkid

#20 Test

35 students took a test of 100 problems.

-Each problem is solved by exactly one girl and one boy.
-There are at least one girl who solved exactly one problem, and at least one girl who solved exactly two problems.
-There are at least one boy who solved exactly four problems, and at least one boy who solved exactly five problems.
-The number of the problems solved by the girl who has solved the maximum number of problems is X.
-The number of the problems solved by the boy who has solved the maximum number of problems is Y.

If the minimum values for both X and Y are the same, find the number of girls who have taken the test.

35名学生参加了共有100道题的考试。
每道题都恰好有一个女生和一个男生答对。
至少有一个女生恰好答对了一道题，至少有一个女生恰好答对了两道题。
至少有一个男生恰好答对了四道题，至少有一个男生恰好答对了五道题。
答对题数最多的女生总共答对了X道题。
答对题数最多的男生总共答对了Y道题。

如果X和Y的最小值相等，找出参加考试的女生人数。
-----------
题目挺拗口，其实是纸老虎。

根据题意最少有三个女生参加考试，设为ABC, 每人答对的题是不能重叠的。
A答对1, B答对2, 100道题必须都有女生答对，此时C答对97, X=97, 因为只有一种情形，MIN(X)=97
在4人ABCD的情况下，AB照旧，当(C,D)=(1,96)时X=96, (C,D)=(2,95)时X=95, .... MIN(X)=49
以此类推, X的最小值就是把100-3平均分布到除去AB之外的所有人身上的情形。


SELECT *
  FROM (SELECT LEVEL+2 F
             ,100-1-2-FLOOR((100-1-2)/LEVEL)*LEVEL+FLOOR((100-1-2)/LEVEL) AS MIN_X
          FROM DUAL
       CONNECT BY LEVEL<=35-3-2
       ),
       (SELECT LEVEL+2 M
              ,100-4-5-FLOOR((100-4-5)/LEVEL)*LEVEL+FLOOR((100-4-5)/LEVEL) AS MIN_Y
          FROM DUAL
       CONNECT BY LEVEL<=35-3-2
       )
WHERE M+F=35 AND MIN_X=MIN_Y;

         F      MIN_X          M      MIN_Y
---------- ---------- ---------- ----------
        18          7         17          7

女生人数=18
        

lastwinner

newkid 发表于 2012-12-5 23:15
#20 Test

35 students took a test of 100 problems.

-FLOOR((100-1-2)/LEVEL)*LEVEL+FLOOR((100-1-2)/LEVEL)

直觉告诉我你这里至少第二个表达式还用FLOOR似乎有问题，于是试着验证了一下
97题16个女生分，答对最多的最小值是7题
91题15个男生分，答对最多的最小值还是7题
结果没错，不过我不能理解这是为啥

————————————————————————————————————

如果是我来处理，那么我会列个式子
ceil(97/M)=ceil(91/N)
M+N=31

可得M=16, N=15时，X=Y=7
with t as (select level M, 31-level N from dual connect by level<31 )
select M+2 girl_cnt, N+2 boy_cnt from t where ceil(97/M)=ceil(91/N)

newkid

花花说得对，我那个公式是错的，比如7题分5个人就错了，应该直接用CEIL。

udfrog

这题初看真一懵,还好nk给了信心先,"纸老虎"很关键啊.不过你这为啥要两表关联呢.

1. select        n
   
2. from        (select rownum+2 n from dual connect by rownum<=35-2-2-1)
   
3. where        ceil((100-9)/(35-n-2))=ceil((100-3)/(n-2));

复制代码