PUZZLEUP 2014

lastwinner

newkid 发表于 2014-8-6 00:00
那就要看怎么理解题意了。
我的理解是TEXT中一半字符是A, 另外一半是B，所以才有这个WHERE。如果不是这么 ...

All possible three-letter codes that can be created with A and B are included in the text.
没注意这句，有了这句，26#+27#就可以搞定了
28#的思路用在证明11字符以上的情况

newkid

#2 Sum and Product

There are three integers such that 0<x<y<z<16. The sum of these numbers is given to the mathematician A, and the product is given to the mathematician B. These conditions are known by A, and B, and their task is to find these three numbers. They make the following conversation:


A:"I can’t find the numbers, and I can see that you can’t find either."

B:"This is a helpful information, but still I can't find the numbers."

A:"Now I can find the numbers."


What are the numbers?

Enter the values of x, y, z separated with commas.

和与积

有三个整数0<x<y<z<16，它们的和被交给数学家A, 它们的积被交给数学家B, A和B知道这些条件，他们的任务是找出这三个数。
他们有如下的对话：
A: 我找不出来，我知道你也找不出来。
B: 这是很有用的信息，但我还是找不出来。
A: 现在我找出来了。

类似的题目我在本版发过：
http://www.itpub.net/thread-1306088-1-1.html

newkid

第二题应该最后也加上一句：
B: 现在我也找出来了。

B所知道的信息比我们还多，没有理由找不出来。

我已经把SQL写出来了，等看看有没更好的。其实SQL也很简单。第一个写出来的送一个章。（话说童馨MM走了以后，就没人给我发章了！）

peter1166

5,4,3  对么？
如果是， 我就整理出来准备要章了 ， 给什么章？

newkid

明天给你章。要哪个？

〇〇

newkid 发表于 2014-8-7 04:03
第二题应该最后也加上一句：
B: 现在我也找出来了。

yangtingkun在一本书里也有类似的题目

peter1166

A: 我找不出来，我知道你也找不出来。
分析：B不知道，也就是说B不可能只根据积来猜出3个数。有的数如果知道积是可以猜出3个数的，例如 X*Y*Z = 10 , 那3个数肯定是 5,2,1 。 这样的数要排除。
      A不知道，也就是说A也不可能只根据合来猜出3个数 。例如 X+Y+Z=7，可以确定肯定是 4,2,1  这样的数也要排除。但是上面B排除的数里已经包含了这类数。   
      A不知道，B也不知道。也就是说，A不知道，B也许知道是不行可以的。
      例如， 如果A的合是8的话， 有两种情况，  5,2,1 和  4,3,1，这个时候A不知道， 因为两个中到底是哪个。
             但是，他们的积是  5*2*1=10 和  4*3*1=12 。 10 和 12 ，上面已经说了积是10的只有一种情况 5,2,1，已经可以唯一确定了。积是12的有两种，4,3,1和 6,2,1
             所以，如果A是8 的话， B也许知道。这个跟上面不满足，所以， A不可能是 8 。
      所以， 要把 A不知道，B也许知道的情况排除。                        
B: 这是很有用的信息，但我还是找不出来。
下面的分析就简单了， 请直接看程序理解。

WITH T AS ( -- 所有可能的结果
          SELECT STR
                 ,X,Y,Z
                 ,X+Y+Z S  -- 合计
                 ,X*Y*Z P  -- 积
                 ,COUNT(1)OVER(PARTITION BY X+Y+Z) S_CNT  -- 合，出现的次数
                 ,COUNT(1)OVER(PARTITION BY X*Y*Z) P_CNT  -- 积，出现的次数， 如果次数是1， 可以唯一确定一组数
          FROM (
                SELECT SUBSTR(STR,2) STR
                       ,REGEXP_SUBSTR(STR,'[^,]+',1,1) X
                       ,REGEXP_SUBSTR(STR,'[^,]+',1,2) Y
                       ,REGEXP_SUBSTR(STR,'[^,]+',1,3) Z
                FROM (
                      SELECT SYS_CONNECT_BY_PATH(N,',') STR
                      FROM (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL < 16)
                      WHERE LEVEL = 3
                      CONNECT BY LEVEL <= 3 AND N < PRIOR N
                     )
              )
          )
    ,T1 AS ( -- 要排除的对象
            SELECT P,S
            FROM   T
            WHERE  P_CNT = 1 -- 积，可以唯一确定一组数
            )
    ,T2 AS (
            SELECT STR, X, Y, Z, S, P
                   ,COUNT(1)OVER(PARTITION BY P) P_CNT2 -- 第一轮排除以后，积的出现次数
            FROM T
            WHERE T.P NOT IN (SELECT T1.P FROM T1) -- A不知道，B也许知道的情况排除
            AND   T.S NOT IN (SELECT T1.S FROM T1) -- B知道排除
           )
     ,T3 AS (
             SELECT T2.*
                    ,COUNT(1)OVER(PARTITION BY S) S_CNT2 -- 合出现的次数
             FROM T2
             WHERE T2.P_CNT2 > 1 -- B: 这是很有用的信息，但我还是找不出来。
            )
SELECT STR
FROM   T3  
WHERE  T3.S_CNT2 = 1 --     A: 现在我找出来了。
;

peter1166

newkid 发表于 2014-8-7 11:44
明天给你章。要哪个？

我想要 11周年纪念章 ，可否 ？

lastwinner

peter1166 发表于 2014-8-7 13:43
A: 我找不出来，我知道你也找不出来。
分析：B不知道，也就是说B不可能只根据积来猜出3个数。有的数如果知 ...

1、构造xyz，直接
with t_1 as (select rownum rn fro dual connect by rownum<=15)
, t_2 as (select rn x, rn y, rn z from t_1 x, t_1 y, t_1 z where x.rn<y.rn and y.rn<z.rn)
即可

2、和只出现一次的，也一样可以直接排除掉

3、和出现多次，并且涉及到的对应的每个积，在所有可能结果里若有一个积只出现一次，这个和一样可以排除掉，因为这些不满足“A: 我找不出来，我知道你也找不出来。”

peter1166

lastwinner 发表于 2014-8-7 14:03
1、构造xyz，直接
with t_1 as (select rownum rn fro dual connect by rownum

谢谢老师。
1. 这么写可能更好理解。 两种写法性能好像差不多。
2. 积出现一次的包含了合出现一次的， 所以没写合出现一次的排除。
3. 这个是关键， 老师的表述简单明了。