2022 PUZZLEUP

〇〇 · 发表于 2022-12-16 15:54

三名学生不能同时属于同一个艺术小组和同一个体育小组。任意三行不存在1排成一个矩形的情况

〇〇 · 发表于 2022-12-16 15:56

对于任何两个学生，他们同时所属的的艺术小组数和体育小组数是相同的。任意两行，为1的奇数列和偶数列一样多

solomon_007 · 发表于 2022-12-16 20:11

newkid 发表于 2022-12-15 05:19
#9 ARTS AND SPORTS GROUPS Arts and sports groups will be formed in a class of 12 students. -Each gro ...

你能先给个提示吗？看了半天有点绕，条件判断的确不好表示。 12名学生，3个一组，最多220兴趣小组。2种类型，艺术和体育，所以最大440个组。 3名学生不能同一个组，所以减半，混合最大220个组。前两个条件，每个学生对这两类组都至少一个，那参加的越多不是越大吗？第二个条件，这不是等价于说每个学生都是相同的吗？。。。

〇〇 · 发表于 2022-12-16 20:33

能先从4个学生开始推算吗？

newkid · 发表于 2022-12-17 09:02

solomon_007 发表于 2022-12-16 20:11
你能先给个提示吗？看了半天有点绕，条件判断的确不好表示。 12名学生，3个一组，最多220兴趣小组。2种 ...

题目后来改了，要求的是“最大”的小组数目，原先漏掉“最大”，很容易就凑出来。

看来你对这个条件有疑问：
对于任何两个学生，他们同时所属的的艺术小组数和体育小组数是相同的。

任选两名学生，看看有哪些小组是他们同时参加的。假设在艺术小组中有N个他们两人是同组（每组中肯定还有一个人，因为小组固定三人），体育小组有M个是两人同组，要求 N=M

我觉得可以从一个简化的6人班级来入手，C(6,3)=20也就是最多总共20个组。把六人排成六边形，每三人为顶点画三角形，蓝色表示艺术，红色表示体育。假设顶点ABC是蓝色，则不可以再画红色的ABC上去，因为有上面那个条件，肯定得有一个红色的 ABD, 以及红色 BCE, 以及红色ACF之类的，争取把20个三角形（红蓝各一半）在这六个顶点安排出来。如果能画满来看看有什么规律，能否推广到12个。

newkid · 发表于 2022-12-17 11:05

手工写了六个20组的分配法，没有仔细验证：
艺术组：
ABC
AEF
ACE
CDE
BCF
BEF
BDE
ABD
ADF
CDF

体育组：
ABF
BCD
DEF
BDF
ABE
ADE
ACD
ACF
BCE
CEF

〇〇 · 发表于 2022-12-18 10:01

本帖最后由〇〇于 2022-12-18 10:46 编辑

newkid 发表于 2022-12-17 11:05
手工写了六个20组的分配法，没有仔细验证：艺术组：ABCAEFACECDEBCFBEFBDEABDADFCDF体育组：ABFBCDDEFBDFAB ...

看你的结果,有这些规律：
在10个艺术组中，单个A出现5次，单个AB出现两次，
体育组也满足上述

〇〇 · 发表于 2022-12-18 10:42

要求能平均分配到体育艺术组，必须每种都是偶数，比如单个A后跟两个字母=5*4/2=10种，单个AB后跟一个字母=4种。12个应该也能凑成

〇〇 · 发表于 2022-12-18 12:59

本帖最后由〇〇于 2022-12-18 18:38 编辑

6人的穷举法
with recursive
a(a)as(values('A'),('B'),('C'),('D'),('E'),('F')),
b(a,b,c,d)as(select a.a,b.a,a.a||b.a,pow(10,row_number()over(order by a.a,b.a)-1)::bigint from a,a b where a.a<b.
t(a,b,c) as
(values
('A', 'B', 'C'),
('A', 'B', 'D'),
('A', 'B', 'E'),
('A', 'B', 'F'),
('A', 'C', 'D'),
('A', 'C', 'E'),
('A', 'C', 'F'),
('A', 'D', 'E'),
('A', 'D', 'F'),
('A', 'E', 'F'),
('B', 'C', 'D'),
('B', 'C', 'E'),
('B', 'C', 'F'),
('B', 'D', 'E'),
('B', 'D', 'F'),
('B', 'E', 'F'),
('C', 'D', 'E'),
('C', 'D', 'F'),
('C', 'E', 'F'),
('D', 'E', 'F')
),
v as(select t.a||t.b||t.c s,(pow(10,(ascii(t.a)-65))+pow(10,(ascii(t.b)-65))+pow(10,(ascii(t.c)-65)))::bigint b ,
(select sum(b.d) from b where instr(t.a||t.b||t.c,b.a) and instr(t.a||t.b||t.c,b.b))::bigint c from t)
select * from v;
┌─────────┬────────┬─────────────────┐
│ s │ b │       c       │
│ varchar │ int64  │    int64    │
├─────────┼────────┼─────────────────┤
│ ABC    │ 111 │       100011 │
│ ABD    │ **1 │       1000** │
│ ABE    │  10011 │       10001001 │
│ ABF    │ 100011 │    100010001 │
│ ACD    │ 1** │    1000000110 │
│ ACE    │  **01 │    1000000**0 │
│ ACF    │ 100** │ 100000010010 │
│ ADE    │  11001 │ 1000000001100 │
│ ADF    │ **001 │  100000000**00 │
│ AEF    │ 110001 │ 100000000011000 │
│ BCD    │ 1110 │    1001100000 │
│ BCE    │  **10 │    100**00000 │
│ BCF    │ 100110 │ 100100100000 │
│ BDE    │  1**0 │ 1000011000000 │
│ BDF    │ **010 │  10000**000000 │
│ BEF    │ 110010 │ 100000110000000 │
│ CDE    │  11100 │ **1000000000 │
│ CDF    │ **100 │  **01000000000 │
│ CEF    │ 1**00 │ 100110000000000 │
│ DEF    │ 111000 │ 111000000000000 │
├─────────┴────────┴─────────────────┤
│ 20 rows                3 columns │
└────────────────────────────────────┘

with recursive
a(a)as(values('A'),('B'),('C'),('D'),('E'),('F')),
b(a,b,c,d)as(select a.a,b.a,a.a||b.a,pow(10,row_number()over(order by a.a,b.a)-1)::bigint from a,a b where a.a<b.a),
t(a,b,c) as
(values
('A', 'B', 'C'),
('A', 'B', 'D'),
('A', 'B', 'E'),
('A', 'B', 'F'),
('A', 'C', 'D'),
('A', 'C', 'E'),
('A', 'C', 'F'),
('A', 'D', 'E'),
('A', 'D', 'F'),
('A', 'E', 'F'),
('B', 'C', 'D'),
('B', 'C', 'E'),
('B', 'C', 'F'),
('B', 'D', 'E'),
('B', 'D', 'F'),
('B', 'E', 'F'),
('C', 'D', 'E'),
('C', 'D', 'F'),
('C', 'E', 'F'),
('D', 'E', 'F')
),
v as(select t.a||t.b||t.c s,(pow(10,(ascii(t.a)-65))+pow(10,(ascii(t.b)-65))+pow(10,(ascii(t.c)-65)))::bigint b ,
(select sum(b.d::hugeint) from b where instr(t.a||t.b||t.c,b.a) and instr(t.a||t.b||t.c,b.b)) c from t),
r as(select 1 lv, v.s,v.b,v.c from v where v.b=111
union all
select lv+1,r.s||v.s,r.b+v.b,r.c+v.c from v,r where lv<20 and substr(r.s,-3)<v.s and (r.b+v.b)::varchar not  SIMILAR TO '.*(6).*' and (r.c+v.c)::varchar not  SIMILAR TO '.*(3).*')
select max(len(s)) from r;

┌─────────────┐
│ max(len(s)) │
│ int64 │
├─────────────┤
│       30 │
└─────────────┘

select s from r where len(s)=30 limit 4;
┌────────────────────────────────┐
│             s             │
│          varchar          │
├────────────────────────────────┤
│ ABCABDACEADFAEFBCFBDEBEFCDECDF │
│ ABCABDACFADEAEFBCEBDFBEFCDECDF │
│ ABCABEACDADFAEFBCFBDEBDFCDECEF │
│ ABCABEACFADEADFBCDBDFBEFCDECEF │
└────────────────────────────────┘

〇〇 · 发表于 2022-12-18 19:12

with recursive
a(a)as(values('A'),('B'),('C'),('D'),('E'),('F')),
b(a,b,c,d)as(select a.a,b.a,a.a||b.a,pow(10,row_number()over(order by a.a,b.a)-1)::bigint from a,a b where a.a<b.a),
v as(select t.a||t1.a||t2.a s,(pow(10,(ascii(t.a)-65))+pow(10,(ascii(t1.a)-65))+pow(10,(ascii(t2.a)-65)))::bigint b ,
(select sum(b.d::hugeint) from b where instr(t.a||t1.a||t2.a,b.a) and instr(t.a||t1.a||t2.a,b.b)) c from a t,a t1,a t2 where t.a<t1.a and t1.a<t2.a),
r as(select 1 lv, v.s,v.b,v.c from v where v.b=111
union all
select lv+1,r.s||v.s,r.b+v.b,r.c+v.c from v,r where lv<20 and substr(r.s,-3)<v.s and (r.b+v.b)::varchar not  SIMILAR TO '.*(6).*' and (r.c+v.c)::varchar not  SIMILAR TO '.*(3).*')
select max(len(s)) from r;
┌─────────────┐
│ max(len(s)) │
│ int64 │
├─────────────┤
│       30 │
└─────────────┘
Run Time (s): real 0.156 user 0.140401 sys 0.015600

with recursive
a(a)as(values('A'),('B'),('C'),('D'),('E'),('F'),('G'),('H'),('I'),('J')),
b(a,b,c,d)as(select a.a,b.a,a.a||b.a,pow(10::hugeint,row_number()over(order by a.a,b.a)-1) from a,a b where a.a<b.a),
v as(select t.a||t1.a||t2.a s,(pow(10::hugeint,(ascii(t.a)-65))+pow(10::hugeint,(ascii(t1.a)-65))+pow(10::hugeint,(ascii(t2.a)-65)))::hugeint b ,
(select sum(b.d::hugeint) from b where instr(t.a||t1.a||t2.a,b.a) and instr(t.a||t1.a||t2.a,b.b)) c from a t,a t1,a t2 where t.a<t1.a and t1.a<t2.a),
r as(select 1 lv, v.s,v.b,v.c from v where v.b=111
union all
select lv+1,r.s||v.s,r.b+v.b,r.c+v.c from v,r where lv<20 and substr(r.s,-3)<v.s and (r.b+v.b)::varchar not  SIMILAR TO '.*(6).*' and (r.c+v.c)::varchar not  SIMILAR TO '.*(3).*')
select max(len(s)) from r;
Error: Conversion Error: Type DOUBLE with value 1e+39 can't be cast because the value is out of range for the destination type INT128

由于溢出，duckdb没法算了

12人能否这么构造：
先构造两个交集为0的6人，然后从220个的组合中去掉这40个再找？

[每日一题] 2022 PUZZLEUP

浏览过的版块