puzzleup 2011

newkid

花花威武！

“那问题就成了XY123456789以及YX123456789都能被7整除”和我的方法一样，后面的98个（任意偶数个）都可以去掉。

再拆分就成了:

XY*MOD(1000000000,7)+MOD(123456789,7)＝XY*6+1  以及YX*6+1 被7整除。接下来人肉应该不难了吧。

把7换成13, 竟然也有相似的结论，可以再试试除数17。

lastwinner

newkid 发表于 2011-12-8 22:55
花花威武！

“那问题就成了XY123456789以及YX123456789都能被7整除”和我的方法一样，后面的98个（任意偶 ...

7*13*11=1001
1001*111=111111
任意6个在一起肯定能被7整除就是从这里猜想进而被进一步证明的，前面没有详述，也不打算详述了
需要用到1/10/100/1000……等被7除后的余数来辅助证明

〇〇

以前我和tree new bee好像证明过
一个质数n
一定可以有不多于n个连续的9的倍数
比如7的倍数是6个9

udfrog

newkid 发表于 2011-10-21 00:38
笨方法：
WITH t AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') STR FROM (SELECT LEVEL-1 N FRO ...

1. select        count(*)
   
2. from        (select rownum n from dual connect by rownum<=10)
   
3. where        level=10
   
4. start with n>2
   
5. connect by nocycle prior n<>n and ceil(n/2)<>ceil(level/2);

复制代码

81楼的sql可以这么搞。
这些天一直在追10和11年的题目，发现递归with占了半壁江山阿。。。

上面代码还可以这么优化一下，这样2s就可以跑出来了

1. select 8*count(*)
   
2. from (select rownum n from dual connect by rownum<=10)
   
3. where level=10
   
4. start with n=3
   
5. connect by nocycle prior n<>n and ceil(n/2)<>ceil(level/2);

复制代码

udfrog

newkid 发表于 2011-11-3 03:20
每三名学生至少回答一道相同的问题, 那么这道相同的题就只能被这三人包了，不可能再被第四人回答（条件2）。 ...

别的思路都一样，不过最最关键的一步，问题数我怎么觉得是X*(15-C(X, 3))+C(X, 3)=15*X +(1-X)*C(X, 3)，得到最多48题，4人的时候。
其次就是，设人数为X, 则C(X-1,2)<=15，这是为什么，不应该是C(X, 3)<=15么？

newkid

udfrog 发表于 2012-8-14 21:54
别的思路都一样，不过最最关键的一步，问题数我怎么觉得是X*(15-C(X, 3))+C(X, 3)=15*X +(1-X)*C(X, 3) ...

#15 考试
Exam
A group of students have taken an exam.  We have the following information:
.Any student answered at most 15 questions.
.Any question was answered by at least 1, at most 3 students.
.Every three students answered at least 1 common question.

How many questions can this exam contain at most?

一群学生参加考试。我们已知如下信息：
每个学生最多回答15道题。
每道题最少被一名学生回答，最多被三名学生回答。
每三名学生至少回答一道相同的问题。

这场考试最多可能包含多少问题？
---------------------
每三名学生至少回答一道相同的问题, 那么这道相同的题就只能被这三人包了，不可能再被第四人回答（条件2）。

每个学生最多回答15题，说明这个学生最多被分到15组:

假设人数为X, 针对一个特定的学生A, 所有包含了A的三人组合为C(X-1,2)。根据条件三，这些组合都必须至少回答同一道题目。各组的共同题目，在不同组合之间可能重复也可能不重复，最分散的情况（X最大化），就是A回答的15道题分散到15个组合中，即包含了A的三人组合共有15组(不一定能达到但绝对不超过15)。

假设有这么个第16组，这个组合也包含了A, 那么因为A不可能回答超过15道题，这组的共同题目必须是在A回答的15道题之中。但是这个问题必定在前面15组中被回答过，也就是说它的回答人数已经达到三人了，如果有这么个第16组, 则回答人数就超过3, 违反题意。

以上推广到任意一个学生都成立, 所以有C(X-1,2)<=15。

问题数=15*X - C(X,3)*2

公式解释：根据条件三, 每三名学生至少回答一道相同的问题，这种共同题最少有C(X,3), 它只能算到一个人头上，从另外两个人的题目中扣减，因此减去C(X,3)*2

满足的55题及其分配的例子构造：

WITH s AS (SELECT LEVEL sno FROM DUAL CONNECT BY LEVEL<=5)
,c3 AS (
SELECT qno
      ,DECODE(p,1,sn1,2,sn2,3,sn3) sno
  FROM (SELECT ROWNUM as qno, s1.sno sn1,s2.sno sn2,s3.sno sn3
         FROM s s1,s s2,s s3
        WHERE s1.sno<s2.sno AND s2.sno<s3.sno
       )
      ,(SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3)
)
,q AS (
SELECT qno,sno FROM c3
UNION ALL
SELECT 10+(sno-1)*9+p qno,sno
  FROM s
      ,(SELECT LEVEL p
           FROM DUAL
          CONNECT BY LEVEL<=9
        )
)
SELECT qno,COUNT(*) FROM q GROUP BY qno;

      QNO   COUNT(*)
--------- ----------
        1          3
       22          1
       25          1
       30          1
       34          1
       42          1
       43          1
       51          1
       54          1
        6          3
       11          1
       13          1
       28          1
       29          1
       44          1
       47          1
        2          3
       14          1
       20          1
       21          1
       26          1
       31          1
        4          3
        5          3
       24          1
       32          1
       46          1
       53          1
        8          3
       17          1
       23          1
       35          1
       37          1
       38          1
       48          1
       55          1
       33          1
       40          1
       41          1
       45          1
       50          1
       52          1
        3          3
        7          3
       18          1
       27          1
       36          1
       49          1
        9          3
       10          3
       12          1
       15          1
       16          1
       19          1
       39          1

分配情况：      
WITH s AS (SELECT LEVEL sno FROM DUAL CONNECT BY LEVEL<=5)
,c3 AS (
SELECT qno
      ,DECODE(p,1,sn1,2,sn2,3,sn3) sno
  FROM (SELECT ROWNUM as qno, s1.sno sn1,s2.sno sn2,s3.sno sn3
         FROM s s1,s s2,s s3
        WHERE s1.sno<s2.sno AND s2.sno<s3.sno
       )
      ,(SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3)
)
,q AS (
SELECT qno,sno FROM c3
UNION ALL
SELECT 10+(sno-1)*9+p qno,sno
  FROM s
      ,(SELECT LEVEL p
           FROM DUAL
          CONNECT BY LEVEL<=9
        )
)
SELECT sno,LISTAGG(qno,',') WITHIN GROUP (ORDER BY qno) qnos FROM q GROUP BY sno;

       SNO
----------
QNOS
------------------------------------------------------
         1
1,2,3,4,5,6,11,12,13,14,15,16,17,18,19

         2
1,2,3,7,8,9,20,21,22,23,24,25,26,27,28

         3
1,4,5,7,8,10,29,30,31,32,33,34,35,36,37

         4
2,4,6,7,9,10,38,39,40,41,42,43,44,45,46

         5
3,5,6,8,9,10,47,48,49,50,51,52,53,54,55

newkid

udfrog 发表于 2012-8-14 19:56
81楼的sql可以这么搞。
这些天一直在追10和11年的题目，发现递归with占了半壁江山阿。。。

其实就是把WHERE挪到CONNECT BY, 剪枝是越早越好。

udfrog

newkid 发表于 2012-8-15 01:02
#15 考试
Exam
A group of students have taken an exam.  We have the following information:

你的是对的.
我把C(X, 3)就当成每个学生被占去的公共题目数了，得C(X, 3)*3/X才行，也就是C(X-1, 2).
多谢nk“大白天”热心回复

udfrog

其实我看到你86楼“相同的思路”时，真感觉很爽。我当时的情况是第一题完全懵，到这个题拿到纸上比划比划发现是组合数的问题，也就觉得找到了这样问题的“建模”方法，第一反应也是第一题也可以这么搞。

udfrog

newkid 发表于 2011-11-10 22:37
假设序号和为N的总个数为F(n), 以n=26为例，可以按开始字母分类：

Z开头：1个

16题有一个比较简单的办法。
对于所有和是26的组合，可以看成都是由26个A这个串演化来的，演化规则是：
26个A，中间有25个空，每个空可以填一个逗号或者不填，不以逗号分隔的A，最后都要加起来，那么这就能得到power(2, 25)个结果，比方A,AAAAAAAAAAAAAAAAAAAAAAAA,A，就得到AXA，所以和是26的，有power(2, 25)个。而这里面，以A开头的，自然就有power(2, 24)个，依此类推。
只有当和是1的时候，只有一个A，没有空来放逗号，所以总数S是奇数，以A开头占(S+1)/2，那么中间的就是A开头排在最后的，就是AY了。