Puzzleup 2010 比赛快开始了，大家用SQL解答啊

lastwinner

原帖由 newkid 于 10-11-19 02:49 发表

抽屉原则用于证明有重复, 怎么证明不重复？

我的想法是，按文中的思路，以“不失一般性”为切入点开始推理即可

newkid

最后一题，比较简单：

#20 Digital Watch

You have a digital watch showing the hour, the minute and the second in 24-hour notation. (example: 00:12:59, 23:45:00 etc.) At some time you look at your watch and observe that these six digits are all different. If you replace all the digits with the number of pieces used to show the corresponding numeral in the digital layout, then you get a new time, which also has the property of consisting of six different digits.

At what time, the difference between those two times are maximum?

Example: If the time was 01:23:45, then we get 62:55:45 from the number of pieces on the digital layout. But it is not a valid time in 24-hour notation.

The number of pieces for all digits in digital layout are as follows: (six for 0, two for 1, five for 2, five for 3, four for 4, five for 5, six for 6, three for 7, seven for 8, six for 9)

Enter your answer as six digits, without using spaces or colons. That is to say, enter 012345 for 01:23:45.

你有一个数字手表，用24小时制显示时分秒。（例如：00:12:59, 23:45:00等）在某个时间点你发现六个数字各不相同。如果你把这些数字用它们的显示笔划数代替，那么你得到一个新的时间，而且六位仍然各不相同。

在什么时刻，这两个时间的差距最大？

例子：假如时间是01:23:45, 那么我们从各个数字的显示笔划数得到的新时间是 62:55:45。但这不是一个有效的时间。

所有数字的显示笔划数如下：(注：这是七段数码管的显示笔划数)
0: 6段
1: 2段
2: 5段
3: 5段
4: 4段
5: 5段
6: 6段
7: 3段
8: 7段
9: 6段


SELECT t,new_t
  FROM ( SELECT tm.*
               ,RANK() OVER(ORDER BY ABS(TO_DATE('20100101'||t,'YYYYMMDDHH24MISS')-TO_DATE('20100101'||new_t,'YYYYMMDDHH24MISS')) DESC) rnk
           FROM (SELECT *
                   FROM (SELECT h||m||s AS t
                               ,TRANSLATE(h||m||s,'0123456789','6255456376') new_t
                           FROM (SELECT LPAD(ROWNUM-1,2,'0') AS h FROM DUAL CONNECT BY ROWNUM<=24)
                               ,(SELECT LPAD(ROWNUM-1,2,'0') AS m FROM DUAL CONNECT BY ROWNUM<=60)
                               ,(SELECT LPAD(ROWNUM-1,2,'0') AS s FROM DUAL CONNECT BY ROWNUM<=60)
                        )
                  WHERE SUBSTR(new_t,1,2) BETWEEN '00' AND '23'
                        AND SUBSTR(new_t,3,2) BETWEEN '00' AND '59'
                        AND SUBSTR(new_t,5,2) BETWEEN '00' AND '59'
                        AND LENGTH(TRANSLATE('0123456789','$'||t,'$'))=4
                        AND LENGTH(TRANSLATE('0123456789','$'||new_t,'$'))=4
                ) tm
       )
WHERE rnk=1;

T                        NEW_T
------------------------ ----------
172048                   235647

lastwinner

直觉觉得效率低
倒着来感觉效率会高一些
即先用234567组成合法时间，再倒推

lastwinner

按这思路，手工也会很快的

newkid

那你就来试试看。总共才86400秒，效率再低也不会差。
等我有空来写个递归，可以中间判断重复数字。

lastwinner

原帖由 newkid 于 10-11-24 23:33 发表
那你就来试试看。总共才86400秒，效率再低也不会差。
等我有空来写个递归，可以中间判断重复数字。

234567，总共没几个变化
两个translate＋两个abs()＋一个greast搞定
就是语句可能会长点

newkid

递归：

WITH tm AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') ms
  FROM (SELECT TO_CHAR(ROWNUM+3) rn
          FROM DUAL
         CONNECT BY ROWNUM<=4
       )
WHERE LEVEL=4
CONNECT BY NOCYCLE rn<>PRIOR rn
)
,t(ms,new_ms,len) AS (
  SELECT ms,'',1 FROM tm WHERE SUBSTR(ms,1,1) IN (4,5) AND SUBSTR(ms,3,1) IN (4,5)
  UNION ALL
  SELECT ms,new_ms||rn,len+1
    FROM t
        ,(SELECT TO_CHAR(ROWNUM-1) rn FROM DUAL CONNECT BY ROWNUM<=10)
   WHERE len<5
         AND (SUBSTR(ms,len,1),rn) IN ((4,4),(5,2),(5,3),(5,5),(6,0),(6,6),(6,9),(7,8))
)
SELECT t1,t2
  FROM (SELECT '17'||new_ms t1
              ,'23'||ms t2
              ,RANK() OVER(ORDER BY ABS(TO_DATE('2010010123'||ms,'YYYYMMDDHH24MISS')-TO_DATE('2010010117'||new_ms,'YYYYMMDDHH24MISS')) DESC) rnk
         FROM T
        WHERE len=5
        )
WHERE rnk=1;

lastwinner

原帖由 newkid 于 10-11-24 23:33 发表
那你就来试试看。总共才86400秒，效率再低也不会差。
等我有空来写个递归，可以中间判断重复数字。

with d as (select rownum+1 r from dual connect by rownum<=6),
mo as (select '234567' src, '174208' mmin, '174598' mmax from dual),
validtime as (select replace(sys_connect_by_path(r,','),',') vt from d where level=6 start with r=2 connect by nocycle r<>prior r and (level in(1,3,5) or level=2 and prior r||r<='23' or level=4 and prior r||r<='59' or level=6 and prior r||r<='59'))
select max(t)keep(dense_rank last order by it) t ,max(vt)keep(dense_rank last order by it) vt from
(select greatest(abs(t1-vt), abs(t2-vt)) it, case when abs(t1-vt) > abs(t2-vt) then t1 else t2 end t, vt from
    (
        select vt, case when substr(t1,1,2)<='23' and substr(t1,3,2)<='59' and substr(t1,5,2)<='59' then t1 else vt end t1,
                case when substr(t2,1,2)<='23' and substr(t2,3,2)<='59' and substr(t2,5,2)<='59' then t2 else vt end t2
            from (select vt, translate(vt, src, mmin) t1, translate(vt, src, mmax) t2 from validtime, mo)
    )
)

做这个题还写代码真是折腾自己
mo要写成union就好处理多了，懒得修改了 -_-

咋又成了 connect by 和with的较量了呢，郁闷～～～

newkid

你这个不够严密吧？你只管两头(mmin,mmax)中间的其他数呢？万一两头的不符合条件偏偏答案就在中间呢？

〇〇

穷举保险