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

〇〇

http://www.puzzleup.com/2010/

〇〇

Competition Rules and Regulations
1. The competition starts on 14th July 2010 and consists of 20 problems which will be posted every week.  

2. New problems will be posted every Wednesday at 11:00 (GMT). Each new problem is finalized in the following 24 hours (i.e. checked for possible revisions, changes, extra information, etc.) and the answering period starts on Thursdays at 11:00 (GMT).

3. Competitors may start the competition at any time during the 24 week period, and answer problems from past weeks.  

4. Each user may join the competition with a single name/membership.  

5. Do not write explanations when answering problems. Respond numerically unless the opposite is requested. Otherwise your answer will be evaluated as wrong.

6. Competitors may be required to justify their answers. In such cases, the particular problem is evaluated according to the justification/explanation.  

7. For your comments and suggestions you can use the [comments] section. Please do not discuss/share answers or tips in your messages. Also please keep in mind that every message will be read, but since this section is not a "forum", not all of them will be published or answered.  

8. Each correct answer is 100 points and users may additionally collect two types of extra points. These are given depending on (a) the answering day of each user and (b) the percentage of correct answers given by all users to the same problem. More specifically:  
   
  a. Competitors receive 5 points for each answer they provide on the first answering day (Thursday 11:00 - Friday 10:59 GMT) of the first week, 4 points for each answer on the second day (Friday 11:00 - Saturday 10:59 GMT), 3 for each answer on the third day (Saturday 11:00 - Sunday 10:59 GMT), 2 for each answer on the fourth day (Sunday 11:00 - Monday 10:59 GMT), 1 for each answer on the fifth day (Monday 11:00 - Tuesday 10:59 GMT). No extra points are given for correct answers to problems from past weeks.  

  b. (100-the correct answer percentage of all users) is added to the total points.  
    For example: Suppose that a competitor has answered a certain problem on the fifth day and the same problem was answered correctly by 30 of the 50 competitors who responded. In this case, 100 points for answering the problem correctly, another 1 point for answering on the fifth day, and 40 extra points (because 30 out of 50 users answered that problem correctly) will be given. The competitor receives 141 points (100 + 1 +[ 100-(100*30/50) ] = 141 ) in total.  

9. Competitors may change their answers but this is limited to 4 times only (5 answering options in total). 20 points will be subtracted from 100 points as each change is made by the competitor. (1st answer-no change:100 points, 2nd answer:80 points, 3rd answer:60 points, 4th answer: 40 points, 5th answer: 20 points).  

10. The scoreboard is updated approximately once a month. The points on the scoreboard correspond to correct answers for randomly chosen problems and include bonus points. (The number of randomly chosen problems is equal to half of the total number of problems). The final calculation will be made at the end of the competition, and the competitors will be able to  examine their scores for all the problems for a 1 week period.

11. Certificates will be e-mailed to the winners; the 10 competitors with the highest points. There are no rewards.  

12. The answers and the solutions will not be announced. The ideas behind the reason for this can be found in the passage taken from the speech made by Emrehan Halici regarding this rule.  

13. The problems in the competition are composed by Emrehan Halýcý, and fall into three different groups:  

    a. Different versions of formerly published, poorly-known problems  

    b. Problems based on a mathematical theory or formula  

    c. Original problems  

14. Any problem may be cancelled due to reasons such as faulty problems, or similar problems published in another commonly used medium. In such cases, the cancellation will be announced on the PuzzleUp website and scores will be re-calculated. Objections regarding these problems are to be evaluated at the end of the competition. The deadline for objections will be announced at the end of answering period.  

15. The PuzzleUp board has the right to make amendments on these rules. Once amendments have been made, they will be stated in the rules page, and announced on the main page.  

16. The PuzzleUp board has the right to disqualify any competitor who violates these rules or any other ethical rule.  

17. All competitors are expected to have read and accepted these rules.

newkid

20周，这么长的周期？
记得你去年也贴了好几个问题，但能用上SQL的并不多，而且他们网站都没有答案，也不知道做对了没有。

〇〇

No: 01       July 14, 2010

Equilateral Triangles You are using a drawing program on a computer. You place several equilateral triangles of the same size on the screen. You observe that you can cover any of these triangles by moving the other triangles without rotating. What is the minimum number of triangles you have to place on the screen to ensure that this observation holds true for every case? [ You can answer this problem starting from Thursday at 11:00 (GMT) ] today's bonus: -- points answers: # 0     popularity: 75.0 %     difficulty: 75.0 %

newkid

看不懂，放两个一样大小的不就行了吗（角度也要一样）？
这个肯定和SQL没什么关系。

newkid

Round Table
A group of people is sitting around a round table. They give a coffee break. When they return to the table after the break, they sit down randomly. Interestingly, they notice that the six closest persons sitting next to each one of them (three to the left, and three to the right) are completely different from the six closest persons in the previous setting.

At least how many persons should be there?

newkid

圆桌问题：
一群人围着圆桌而坐。他们起来喝完咖啡，随机坐回座位，发现相邻的六人（左边三位和右边三位）和先前完全不同。满足这种情形的最少人数是多少？


用11GR2的SQL模拟一下，因为最少要13人，从N=13开始把N逐步增加, 发现N=17的时候有了答案：

VAR N NUMBER;
EXEC :N := 17;

WITH t (n,str,cnt,first2,first3,last2,last3) AS (
SELECT 1,CAST(',1,' AS VARCHAR2(1000)),1,-9999,-9999,-9999,-9999 FROM DUAL
UNION ALL
SELECT rn
      ,t.str||rn||','
      ,t.cnt+1
      ,DECODE(t.cnt,1,rn,t.first2)
      ,DECODE(t.cnt,2,rn,t.first3)
      ,t.n
      ,t.last2
  FROM t,(SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM<:N)
WHERE INSTR(t.str,','||rn||',')=0
       AND t.cnt<:N
       AND NOT (ABS(rn-t.n)<=3
                OR ABS(rn-t.last2)<=3
                OR ABS(rn-t.last3)<=3
                OR (t.cnt>=:N-3 OR t.cnt<4) AND rn IN (2,3,4,:N,:N-1,:N-2)
                OR t.cnt>=:N-2 AND ABS(rn-t.first2)<=3
                OR t.cnt =:N-1 AND ABS(rn-t.first3)<=3
                OR rn=2    AND (n>:N-2 OR t.last2>:N-2  OR t.last3>:N-2  )
                OR rn=3    AND (n>:N-1 OR t.last2>:N-1  OR t.last3>:N-1  )
                OR rn=:N-1 AND (n=2 OR t.last2=2        OR t.last3=2     )
                OR rn=:N   AND (n<4 OR t.last2 IN (2,3) OR t.last3 IN (2,3))
                )                  
)
SELECT TRIM(BOTH ',' FROM str) FROM t WHERE cnt=:N
;

另一类似写法：
WITH d AS (
SELECT ROWNUM+1 rn
      ,ROWNUM+1-3 min1
      ,ROWNUM+1+3 max1
      ,CASE WHEN ROWNUM+1<=3 THEN :N + ROWNUM+1 -3
            WHEN ROWNUM+1>=:N-2 THEN 1
            ELSE 0
       END min2
      ,CASE WHEN ROWNUM+1<=3 THEN :N
            WHEN ROWNUM+1>=:N-2 THEN ROWNUM+1 + 3 - :N
            ELSE 0
       END max2
FROM DUAL CONNECT BY ROWNUM<:N
)
,t (n,str,cnt,first2,first3,last2,last3) AS (
SELECT 1,CAST(',1,' AS VARCHAR2(1000)),1,-9999,-9999,-9999,-9999 FROM DUAL
UNION ALL
SELECT rn
      ,t.str||rn||','
      ,t.cnt+1
      ,DECODE(t.cnt,1,rn,t.first2)
      ,DECODE(t.cnt,2,rn,t.first3)
      ,t.n
      ,t.last2
  FROM t,d
WHERE INSTR(t.str,','||rn||',')=0
       AND t.cnt<:N
       AND NOT (   t.n     BETWEEN d.min1 AND d.max1 OR t.n     BETWEEN d.min2 AND d.max2
                OR t.last2 BETWEEN d.min1 AND d.max1 OR t.last2 BETWEEN d.min2 AND d.max2
                OR t.last3 BETWEEN d.min1 AND d.max1 OR t.last3 BETWEEN d.min2 AND d.max2
                OR t.cnt>=:N-3 AND (1        BETWEEN d.min1 AND d.max1 OR 1        BETWEEN d.min2 AND d.max2)
                OR t.cnt>=:N-2 AND (t.first2 BETWEEN d.min1 AND d.max1 OR t.first2 BETWEEN d.min2 AND d.max2)
                OR t.cnt =:N-1 AND (t.first3 BETWEEN d.min1 AND d.max1 OR t.first3 BETWEEN d.min2 AND d.max2)
                )
)
SELECT TRIM(BOTH ',' FROM str) FROM t WHERE cnt=:N
;


LTRIM(REPLACE(STR,''),',')
------------------------------------------------
1,5,9,13,17,4,8,12,16,3,7,11,15,2,6,10,14
1,14,10,6,2,15,11,7,3,16,12,8,4,17,13,9,5

两个答案其实是一样的，只是顺时针和逆时针而已。

[ 本帖最后由 newkid 于 2010-7-24 04:12 编辑 ]

lastwinner

sql不是万能的

newkid

Sums of Square Numbers

Which is the smallest number that can be expressed as the sum of six different square numbers, but cannot be expressed as the sum of five different square numbers?

WITH d AS (SELECT ROWNUM*ROWNUM n FROM DUAL CONNECT BY ROWNUM<=10)
,t(lvl,n,s,str) AS (
SELECT 1,n,n,TO_CHAR(n) FROM d
UNION ALL
SELECT lvl+1,d.n,t.s+d.n,t.str||'+'||d.n
  FROM d,t
WHERE t.lvl<=5 AND t.n<d.n
)
SELECT s,str FROM
(SELECT t1.*
  FROM (SELECT * FROM t WHERE lvl=6) t1
      ,(SELECT * FROM t WHERE lvl=5) t2
WHERE t1.s = t2.s(+)
       AND t2.s IS NULL
ORDER BY t1.s
)
WHERE ROWNUM=1;

         S STR
---------- ---------------------------------
        91 1+4+9+16+25+36

〇〇

直接就是最小的那个啊,只要证明没有2个平方数之和也是平方数
9+16虽然是25，但是，25已经存在，不算different