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

newkid

本周的题相对简单：
#18 Three Digits

You have a number where any numeral appears at most twice. The sum of all neighboring three digits in this number is a square number.

What is the maximum possible value for this number?

Example: 74504 is such a number because no numeral appears more than twice and 7+4+5, 4+5+0 and 5+0+4 are square numbers.

有一个数，每一位最多出现两次，所有相邻的三位数值和都是一个平方数。这个数可能的最大值是多少？
比如：74504就是这样一个数，它的所有位都不超过两次，并且7+4+5, 4+5+0 和 5+0+4都是平方数。

WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<=9
   UNION ALL
   SELECT t.str||n
     FROM t,(SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
    WHERE INSTR(str,n,1,2)=0 AND (LENGTH(str)<=2 OR SUBSTR(str,-1,1)+SUBSTR(str,-2,1)+n IN (4,9,16,25))
   )
SELECT MAX(str) KEEP(DENSE_RANK FIRST ORDER BY LENGTH(str) DESC) FROM T;


9871801306376

lastwinner

原帖由 newkid 于 10-11-10 22:41 发表
本周的题相对简单：
#18 Three Digits

You have a number where any numeral appears at most twice. The sum of all neighboring three digits in this number is a square number.

What is the maximum possible value for this number?

Example: 74504 is such a number because no numeral appears more than twice and 7+4+5, 4+5+0 and 5+0+4 are square numbers.

有一个数，每一位最多出现两次，所有相邻的三位数值和都是一个平方数。这个数可能的最大值是多少？
比如：74504就是这样一个数，它的所有位都不超过两次，并且7+4+5, 4+5+0 和 5+0+4都是平方数。

WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<=9
   UNION ALL
   SELECT t.str||n
     FROM t,(SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
    WHERE INSTR(str,n,1,2)=0 AND (LENGTH(str)<=2 OR SUBSTR(str,-1,1)+SUBSTR(str,-2,1)+n IN (4,9,16,25))
   )
SELECT MAX(str) KEEP(DENSE_RANK FIRST ORDER BY LENGTH(str) DESC) FROM T;


9871801306376

9＋8＋7＝24，明显不是一个平方数

另外，(4,9,16,25)也应改为(1,4,9,16,25)
1004这样的数字显然是满足 相邻三位和为平方数的 要求的一个数

newkid

说得对，我又太粗心了。

WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<=9
   UNION ALL
   SELECT t.str||n
     FROM t,(SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
    WHERE INSTR(str,n,1,2)=0 AND (LENGTH(str)<2 OR SUBSTR(str,-1,1)+SUBSTR(str,-2,1)+n IN (1,4,9,16,25))
   )
SELECT MAX(str) KEEP(DENSE_RANK FIRST ORDER BY LENGTH(str) DESC) FROM T;


988010367367

nlrte13

原帖由 newkid 于 2010-11-11 00:48 发表
说得对，我又太粗心了。

WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM

我算的也是这个结果，988010367367 ^^

费奇11

原帖由 newkid 于 2010-11-3 22:35 发表
#17 Points

There are X points on a plain paper. Using three different colors, you will draw lines connecting each point with every other point. The condition is that none of the triangles formed by these connections would be monochromic.

What is the maximum possible value for X?

纸上有X个点，你用三种颜色的线把它们两两相连，条件是不能出现单色的三角形。X可能的最大值是多少？

请问如何证明X=16时不会出现单色三角形？劳烦将理论证明方法（不要计算机暴力法，不要实践结果图）发我邮箱 liangyj1128@163.com，谢谢！

lastwinner

原帖由 费奇11 于 10-11-17 10:53 发表



请问如何证明X=16时不会出现单色三角形？劳烦将理论证明方法（不要计算机暴力法，不要实践结果图）发我邮箱 liangyj1128@163.com，谢谢！

抽屉原则，自己往下翻几楼就能看到证明了

newkid

#19 Odd Numerals
When all integers from 1 to X are written on a piece of paper, the number of odd numerals used are two times X.

What is the maximum possible value for X?

Example: If all integers from 1 to 15 are written, the number of odd numerals used is 14.

把整数1到X写下来，其中奇数数位被使用的次数是X的两倍。X最大可能为多少？
例如，把整数1到15写下来，其中奇数数位被使用了14次。


如果是求最小的：
WITH t(n,cnt) AS (
  SELECT 1,1 FROM DUAL
  UNION ALL
  SELECT n+1,LENGTH(n+1)-LENGTH(TRANSLATE('$'||(n+1),'$13579','$'))+1+cnt
    FROM t
   WHERE n*2<>cnt
  )
SELECT MAX(n),MAX(cnt) FROM t;  

    MAX(N)   MAX(CNT)
---------- ----------
      1998       3996

最大的应该也不难，把公式总结出来即可。

lastwinner

原帖由 newkid 于 10-11-17 23:07 发表
#19 Odd Numerals
When all integers from 1 to X are written on a piece of paper, the number of odd numerals used are two times X.

What is the maximum possible value for X?

Example: If all integers from 1 to 15 are written, the number of odd numerals used is 14.

把整数1到X写下来，其中奇数数位被使用的次数是X的两倍。X最大可能为多少？
例如，把整数1到15写下来，其中奇数数位被使用了14次。


如果是求最小的：
WITH t(n,cnt) AS (
  SELECT 1,1 FROM DUAL
  UNION ALL
  SELECT n+1,LENGTH(n+1)-LENGTH(TRANSLATE('$'||(n+1),'$13579','$'))+1+cnt
    FROM t
   WHERE n*2cnt
  )
SELECT MAX(n),MAX(cnt) FROM t;  

    MAX(N)   MAX(CNT)
---------- ----------
      1998       3996

最大的应该也不难，把公式总结出来即可。

奇数数位 翻译做  奇数数字更好一点吧

nlrte13

10096？
奇怪的数字

〇〇

只是猜测
SQL> with t as (select level l,
  2  length(translate('$'||level,'$02468','$'))-1 j
  3  from dual connect by level<=1E6)
  4  select * from
  5  (
  6  select * from
  7  (select L,sum(j)over(order by L)sj from t
  8  )where sj=2*L
  9  order by 1 desc )
10  where rownum<=10;

         L         SJ
---------- ----------
     10096      20192
     10095      20190
     10083      20166
     10082      20164
     10076      20152
     10075      20150
     10063      20126
     10062      20124
     10056      20112
     10055      20110

已选择10行。