2022 PUZZLEUP

newkid

把二进制写法简化一下，去掉正方形的条件：
with  t as(select level i from dual connect by level<=10),
ab(a,b,bit_1) as(select t.i a,j.i b, power(2,t.i-1)+power(2,j.i-1) bit from t,t j where t.i<>j.i), ---- 没必要排大小
cd(c,d,bit_2) as(select a,b,bit_1 from ab),
ef(e,f,bit_3) as(select a,b,bit_1 from ab),
gh(g,h,bit_4) as(select a,b,bit_1 from ab),
xy(x,y,bit_5) as(select a,b,bit_1 from ab)
select a,b,c,d,e,f,g,h,x,y
from ab,cd,ef,gh,xy
where a+b=c+d and e+f=g+h and a-x=c
      and e-y=g  -------- 和图中相反，但不影响结果
      -- and a+b=e+f  ------ 必须是正方形
      and bit_1+bit_2+bit_3+bit_4+bit_5 = power(2,10)-1
;


找到一个更大一点的(17*9)的长方形：
10          7          9          8          6          3          4          5          1          2

〇〇

11题和12题是第4题和第5题的重复，不知怎么想的

newkid

那两道题表达不清，重新出一遍，希望这次能说清楚。

〇〇

重新出的
No: 12       January 04, 2023

ONE AND TWO

ONE AND TWO

You will generate a number using only the digits 1 and 2. Our condition is that no sequence of 3 or more digits repeats more than two times. What is the largest number satisfying this condition?

Example: If the number is “ABCDE…”,
Three-digit sequences are: “ABC”, “BCD”, “CDE”, …
Four-digit sequences are: “ABCD”, “BCDE”, …
编号：12
2023年1月4日
一和二

您将只使用数字1和2生成一个数字。我们的条件是，3个或更多数字的序列重复次数不超过两次。满足这个条件的最大数字是多少？

示例：如果数字是“ABCDE…”，

三位数序列是：“ABC”、“BCD”、“CDE”、…

四位数序列是：“ABCD”、“BCDE”、…

newkid

这就是第五题我最初理解的意思，只不过当时的题目说不能出现两次，而现在改成不能出现多于两次，两次还是允许的。

dhhb

〇〇 发表于 2023-1-4 20:24
重新出的No: 12       January 04, 2023ONE AND TWOONE AND TWOYou will generate a number using only the ...

SQL> with t as
  2  (select  '1' v from dual
  3  union
  4  select  '2' v from dual  ),
  5  t2 ( v)
  6  as
  7  (select * from t
  8  union all
  9  select  t2.v||t.v from t2,t where (instr(t2.v||t.v ,substr(t2.v||t.v,length(t2.v||t.v)-2),1,3)=0  )
10  )
11  select  to_char(max(cast(v as number)) ) from t2;

TO_CHAR(MAX(CAST(VASNUMBER)))
--------------------------------------------------------------------------------
222212212112111122

newkid

已给楼上转章。

with t (s,cnt)
as (
select cast(level as varchar2(200)),1 from dual connect by level<=2
union all
select t.s||n,t.cnt+1
  from t,(select level n from dual connect by level<=2)
where instr(t.s,substr(t.s,-2)||n,1,2)=0
)
select to_char(max(to_number(s))) from t;


TO_CHAR(MAX(TO_NUMBER(S)))
----------------------------------------
222212212112111122

这道题用手算也不难，两个数字的三位数总共8个，各出现两次，错一位叠起来总长度是8*2+2=18位，目标是把这18位凑出来。
因为要最大，先把2222摆上去。接下来就像深度优先的回溯算法，先拼2，如果次数超出就拼1, 如果凑不足18位就回退。

newkid

No: 13       January 11, 2023

ARTS AND SPORTS GROUPS

ARTS AND SPORTS GROUPS

Arts and sports groups will be formed in a class of 12 students.

-Each group consists of 3 students.
-Each student will take part in at least one art and at least one sports group.
-For any pair of students, the number of arts groups and the number of sports groups that both students are members are the same.
-No three students can be in the same arts group and sports group.

What is the minimum total number of arts and sports groups created to meet these conditions?

又改题了，原第九题作废，现在要求最小数字。

newkid

暴力法解第13题6个顶点：


drop table t;
create table t as
with d as (
select replace(sys_connect_by_path(c,','),',') s from (
(select chr(64+level) c from dual connect by level<=6)
)
connect by nocycle c>prior  c and level<=3
)
,s as (  --------- 所有三角形的边，六个顶点总共15条
select s,power(10,row_number() over(order by s)-1) h  ------ 每条边用十进制的一位表示
  from d
where length(s)=2
)
--------- 所有三角形，六个顶点总共20个
select /*+ materialize */ t1.s,t1.h,t1.rn
     ,sum(s.b) b   ------- 每个三角形的三个顶点所对应的三个二进制位
from (
select d.s
      ,sum(s.h) h ------- 每个三角形的三条边所对应的三个十进制位
      ,row_number() over(order by d.s) rn
  from d,s
where length(d.s)=3
       and s.s in (substr(d.s,1,2),substr(d.s,2,2),substr(d.s,1,1)||substr(d.s,3,1))
group by d.s
) t1
,(select s,power(2,row_number() over(order by s)-1) b from d where length(s)=1) s ---- 六个顶点分别用一个二进制位表示
where instr(t1.s,s.s)>0
group by t1.s,t1.h,t1.rn
;


create table r1 (s varchar2(100),cnt1 number,cnt2 number,b1 number,b2 number,h1 number,h2 number,cnt number);

create table r2 as select * from r1 where 1=0;


declare
   v_cnt number:=2;
   v_rowcount number;
   v_result varchar2(100);
begin
      execute immediate 'truncate table r1';

insert into r1
select listagg(s||rn,',') within group(order by s) s  ----- 当前解法的所有三角形
      ,1 as cnt1   ------ 1组三角形总数
      ,1 as cnt2   ------ 2组三角形总数
      ,sum(decode(rn,1,b)) as b1   ------ 1组覆盖哪些顶点
      ,sum(decode(rn,2,b)) as b2   ------ 2组覆盖哪些顶点
      ,sum(decode(rn,1,h)) as h1   ------ 1组覆盖哪些边
      ,sum(decode(rn,2,h)) as h2   ------ 2组覆盖哪些边
      ,2 as cnt
  from t
where s in ('ABC','ABD') ------- 以ABC,ABD为起点，假设ABC分在1组，ABD分在2组
;

   loop
      v_cnt := v_cnt+1;
      execute immediate 'truncate table r2';

      insert into r2
select r.s||','||t.s||n
      ,decode(n,1,cnt1+1,cnt1)
      ,decode(n,2,cnt2+1,cnt2)
      ,decode(n,1,r.b1+t.b-bitand(r.b1,t.b),r.b1) ----- 二进制的"OR"算法，表示覆盖哪些顶点
      ,decode(n,2,r.b2+t.b-bitand(r.b2,t.b),r.b2)
      ,decode(n,1,r.h1+t.h,r.h1)  --------- 1组覆盖的每个边的累计
      ,decode(n,2,r.h2+t.h,r.h2)  --------- 2组覆盖的每个边的累计
      ,V_CNT
  from r1 r,t,(select level-1 n from dual connect by level<=3) ----0: 这个三角形不属于任何组; 1:该三角形属于1组; 2:该三角形属于2组
where t.rn=V_CNT
       and r.cnt1<10
       and r.cnt2<10
       and instr(r.h1,'3')=0 -------因为有六个顶点，每条边最多对应四个三角形(6-2=4)，索引每条边最多被每组覆盖两次，这个十进制位表示累计数，只能出现0,1,2
       and instr(r.h2,'3')=0
       ;
      
      v_rowcount :=sql%rowcount;
      if v_rowcount=0 then
         exit;
      end if;
      
      dbms_application_info.set_client_info ('cnt='||v_cnt||' rowcount='||v_rowcount);      

      select min(s) into v_result
      from (
      select *
      from r2
      where b1=power(2,6)-1
          and b2=power(2,6)-1
          and h1=h2
      order by cnt1+cnt2
      )
      where rownum=1;
      
      if v_result is not null then
         dbms_output.put_line('solution found:'||v_result);
         exit;
      end if;
      
      execute immediate 'truncate table r1';
      
      insert into r1 select * from r2;
      
      commit;
      
      
   end loop;
end;
/


ABC1,ABD2,ABE0,ABF0,ACD0,ACE0,ACF2,ADE0,ADF1,AEF0,BCD0,BCE2,BCF0,BDE1,BDF0,BEF0,CDE0,CDF0,CEF1,DEF2


第一组：
ABC,ADF,BDE,CEF

第二组：
ABD,ACF,BCE,DEF

newkid

----------------
#7 PAWNS 新思路：改良过的暴力法，利用推理把关注范围缩小到用代码可以求出结果。纯推理方法应该也有但是我没想出来。

把图中的每一列看作一个九位二进制数，假设S是一个满足条件的最大集，每个元素就是其中一个9位二进制数，任意两个元素的XOR结果至少有5个二进制位为1。

推论：要么#1: S里面包含全零，要么#2: 可以找到另外一个一样大的集合，里面包含全零。

#2证明：假设S本身不包含全零，则任取一个元素C作为基准，把集合中所有的元素全部XOR C，那么C就变成了全零，而集合仍然满足条件。因为本来任意两个元素AB,  A XOR B 满足条件，现在分别XOR C，就变成了了 A XOR C XOR B XOR C，C和C互相抵消，结果仍然是A XOR B


把全零作为一个基本元素，则最大集可以分别为以下两种情况：
#1:包含四个零(其他元素可能含有一个，两个，三个零)；
#2:不含四个零，但含三个零（其他元素可能有两个零，但不含一个零，一个零和三个零XOR就凑不出五个1）；

全1不可以出现。任意一个A,不可能和全零XOR满足条件，同时和全1 XOR也满足条件。
不可能包含五个以上的零（因为和全零异或之后，1不够5位）
也不可能只有两个或一个零，因为凑不出五个1，XOR抵消了。


图中的行顺序是和结果无关的。给定一个集合，任意调换所有元素所在的同一行，不影响结果。假设有一个元素包含四个零，那么可以通过调换把四个零全部排在最上面，或者最下面，而不影响结果（注意在调换时所有元素所在的同一行必须一起调换）。由于这个原因，满足条件的最大集有很多个，但它们都是类似的，我们只需关注其中一个。

#1:
集合中已经有两个基本元素：

A:００００１１１１１
B:０００００００００

构造其他候选元素：
四个零: 最多只能有一个零出现在左边四位中。如果有2,3,4个零出现在左边四位，那么和A的XOR就凑不够五个1。
        左边零的位置：四种，右边C(5,3)，所以总共有4*C(5,3)=40
        或者四个零全在右边，共有C(5,4)=5种
三个零：只能有一个零出现在左边四位中。如果有2,3个零出现在左边四位，那么和A的XOR就凑不够五个1。
　　　　左边零的位置：四种，右边C(5,2)，所以总共有4*C(5,2)=40
        或者三个零全在右边，共有C(5,3)=10种
两个零：两个零必须全在右边，共有C(5,2)=10种
一个零：这个零必须在右边，共有C(5,1)=5种
共计110种, 用110位二进制表示，ORACLE的NUMBER可以支持。

create table e(e varchar2(10), id number,bit number, e2 number);

insert into e(e,id,bit,e2)
with n as (select level n from dual connect by level<=5)
,L1 as (select regexp_replace('1111','1','0',level,1) s1 from dual connect by level<=4) --- 左边一个零
,R3 AS (select lpad(power(10,n1.n-1)+power(10,n2.n-1),5,'0') s2 ---- 三个零（两个1）在右边
         from n n1,n n2
       where n1.n<n2.n
       )
,R2 AS (select lpad(11111-TO_NUMBER(S2),5,'0') s2 ---- 两个零（三个1）在右边
         from R3
       )
,s as (
select e,row_number() over(order by e) as id,power(2,row_number() over(order by e)-1) as bit from
(
  ---------- 四个零的情形
  select L1.s1||r3.s2 as e
    from L1  --- 左边一个零, 三个零（两个1）在右边
        ,r3
  UNION ALL
  select '1111'||regexp_replace('00000','0','1',level,1) s2 from dual connect by level<=5  ---左边全1, 右边四个零
  ---------- 三个零的情形
  UNION ALL
  SELECT L1.s1||r2.s2
   FROM L1  --- 左边一个零， 两个零（三个1）在右边
       ,r2
  UNION ALL ---- 左边全1, 三个零（两个1）在右边
  select '1111'||s2
    FROM R3
  ---------- 两个零的情形
  UNION ALL ---- 左边全1, 两个零（三个1）在右边
  select '1111'||s2
    FROM R2
  ---------- 一个零的情形
  UNION ALL
  select '1111'||regexp_replace('11111','1','0',level,1) from dual connect by level<=5
  )
)
select e,id,bit,sum(bit2) as e2  ------- 所有和当前边异或之后满足条件的其他边的二进制位之和
  from (
select e1.*,e2.bit bit2,replace(lpad(to_number(e1.e)+to_number(e2.e),9,'0'),'2','0') xor
from s e1,s e2
where e1.id<>e2.id
)
where regexp_count(xor,'1')>=5
group by e,id,bit;



with t(s,cnt,bit,last_id) as (
select cast(id as varchar2(100)),1,e2,id from e
union all
select t.s||','||e.id,t.cnt+1,bitand(t.bit,e.e2),e.id
from t,e
where bitand(t.bit,e.bit)>0
      and t.last_id<e.id
)
select * from (select * from t order by cnt desc,s) where rownum=1;

S
--------------------------------------
       CNT        BIT    LAST_ID
---------- ---------- ----------
1,28,55,79
         4          0         79


select S from e where e.id in (1,28,55,79);

E         
----------
０１１１０００１１     
１０１１０１１００     
１１０１１０１０１     
１１１０１１０１０     

#2:
集合中已经有两个基本元素：
A:０００１１１１１１
B:１１１１１１１１１

构造其他候选元素：
三个零：三个零必须全在右边，共有C(6,3)=20种
两个零：两个零必须全在右边，共有C(6,2)=15种
共计35种, 用35位二进制表示，ORACLE的NUMBER可以支持。



DELETE e;
-- create table e(e varchar2(10), id number,bit number, e2 number);

insert into e(e,id,bit,e2)
with n as (select level n from dual connect by level<=6)
,s as (
select e,row_number() over(order by e) as id,power(2,row_number() over(order by e)-1) as bit from
   (
     select '111'||lpad(power(10,n1.n-1)+power(10,n2.n-1)+power(10,n3.n-1),6,'0') e ---- 三个零（三个1）在右边
       from n n1,n n2,n n3
     where n1.n<n2.n and n2.n<n3.n
     UNION ALL
     select '111'||lpad(power(10,n1.n-1)+power(10,n2.n-1)+power(10,n3.n-1)+power(10,n4.n-1),6,'0') s2 ---- 两个零（四个1）在右边
       from n n1,n n2,n n3,n n4
     where n1.n<n2.n and n2.n<n3.n and n3.n<n4.n
   )
)
select e,id,bit,sum(bit2) as e2  ------- 所有和当前边异或之后满足条件的其他边的二进制位之和
  from (
select e1.*,e2.bit bit2,replace(lpad(to_number(e1.e)+to_number(e2.e),9,'0'),'2','0') xor
from s e1,s e2
where e1.id<>e2.id
)
where regexp_count(xor,'1')>=5
group by e,id,bit;


------ 以下代码同上面"四个零"的情形


with t(s,cnt,bit,last_id) as (
select cast(id as varchar2(100)),1,e2,id from e
union all
select t.s||','||e.id,t.cnt+1,bitand(t.bit,e.e2),e.id
from t,e
where bitand(t.bit,e.bit)>0
      and t.last_id<e.id
)
select * from (select * from t order by cnt desc,s) where rownum=1;

S
------------------------------
       CNT        BIT
---------- ----------
1,32
         2          0


所以S最大为6个元素：
０１１１０００１１
１０１１０１１００
１１０１１０１０１
１１１０１１０１０
００００１１１１１
０００００００００

这个答案比想象中的小，不知道上面推理过程有没有错误。