2022 PUZZLEUP

newkid

用我的方法很容易推导出公式：

var n number;
exec :n:=8;

select (power(:n*(:n-1)/2,2)-(2*power(:n,3)-3*power(:n,2)+:n)/6)*4 from dual;


(POWER(:N*(:N-1)/2,2)-(2*POWER(:N,3)-3*POWER(:N,2)+:N)/6)*4
-----------------------------------------------------------
                                                       2576

solomon_007

#2

--3*3
SQL>
SQL> with t(n,r,c) as (select level,ceil(level/3),decode(mod(level,3),0,3,mod(level,3))
  2                      from dual
  3                     connect by level <= 3*3),
  4       L(lvl,nlist,pre_r,pre_c,last_r,last_c,nsum,c_cnt,r_cnt,turn_cnt) as (select 1,
  5                                               cast(n as varchar2(1000)),
  6                                               null,
  7                                               null,
  8                                               t.r,
  9                                               t.c,
10                                               power(2,t.n),
11                                               1,
12                                               1,
13                                               0
14                                          from t
15                                         union all
16                                        select L.lvl + 1,
17                                               L.nlist||','||t.n,
18                                               L.last_r,
19                                               L.last_c,
20                                               t.r,
21                                               t.c,
22                                               L.nsum + power(2,t.n),
23                                               case when abs(L.last_c - t.c) = 1 then L.c_cnt + 1 else L.c_cnt end,
24                                               case when abs(L.last_r - t.r) = 1 then L.r_cnt + 1 else L.r_cnt end,
25                                               case when L.pre_c <> t.c and L.pre_r <> t.r then L.turn_cnt + 1 else L.turn_cnt end
26                                          from L,t
27                                         where abs(L.last_r - t.r) + abs(L.last_c - t.c) = 1
28                                           and bitand(L.nsum,power(2,t.n)) = 0
29                                           and case when L.turn_cnt = 0 then 1
30                                                    when L.turn_cnt = 1 and (L.pre_c = t.c or L.pre_r = t.r) then 1
31                                                    else 0
32                                               end = 1
33                                           and L.turn_cnt <=1 )
34  select count(distinct nsum) from L where turn_cnt = 1 and c_cnt <> r_cnt
35  /

COUNT(DISTINCTNSUM)
-------------------
                 16


--8*8
SQL>
SQL> with t(n,r,c) as (select level,ceil(level/8),decode(mod(level,8),0,8,mod(level,8))
  2                      from dual
  3                     connect by level <= 8*8),
  4       L(lvl,nlist,pre_r,pre_c,last_r,last_c,nsum,c_cnt,r_cnt,turn_cnt) as (select 1,
  5                                               cast(n as varchar2(1000)),
  6                                               null,
  7                                               null,
  8                                               t.r,
  9                                               t.c,
10                                               power(2,t.n),
11                                               1,
12                                               1,
13                                               0
14                                          from t
15                                         union all
16                                        select L.lvl + 1,
17                                               L.nlist||','||t.n,
18                                               L.last_r,
19                                               L.last_c,
20                                               t.r,
21                                               t.c,
22                                               L.nsum + power(2,t.n),
23                                               case when abs(L.last_c - t.c) = 1 then L.c_cnt + 1 else L.c_cnt end,
24                                               case when abs(L.last_r - t.r) = 1 then L.r_cnt + 1 else L.r_cnt end,
25                                               case when L.pre_c <> t.c and L.pre_r <> t.r then L.turn_cnt + 1 else L.turn_cnt end
26                                          from L,t
27                                         where abs(L.last_r - t.r) + abs(L.last_c - t.c) = 1
28                                           and bitand(L.nsum,power(2,t.n)) = 0
29                                           and case when L.turn_cnt = 0 then 1
30                                                    when L.turn_cnt = 1 and (L.pre_c = t.c or L.pre_r = t.r) then 1
31                                                    else 0
32                                               end = 1
33                                           and L.turn_cnt <=1 )
34  select count(distinct nsum) from L where turn_cnt = 1 and c_cnt <> r_cnt
35  /

COUNT(DISTINCTNSUM)
-------------------
               2576

老办法！

newkid

solomon_007 发表于 2022-10-28 11:53
#2 --3*3SQL> SQL> with t(n,r,c) as (select level,ceil(level/3),decode(mod(level,3),0,3,mod(level,3)) ...

欢迎回来玩！你现在还搞不搞ORACLE?
你这个写法是把每个L形都找出来了，在这道题里面没有必要这么具体。OO的坐标写法就很简单。

solomon_007

newkid 发表于 2022-10-28 21:30
欢迎回来玩！你现在还搞不搞ORACLE?你这个写法是把每个L形都找出来了，在这道题里面没有必要这么具体。OO的 ...

大哥好！ 还在搞！ 平时偶尔也潜水上来看看。
OO的坐标的是有个最简洁的写法，但记不得了，又不想翻老帖，就用自己的笨办法。

solomon_007

OO的坐标写法，找到了，好像是这个写法：

SQL> select level n, trunc((level-1)/3) r, mod(level-1,3) c from dual connect by level<=3*3;

         N          R          C
---------- ---------- ----------
         1          0          0
         2          0          1
         3          0          2
         4          1          0
         5          1          1
         6          1          2
         7          2          0
         8          2          1
         9          2          2

9 rows selected

newkid

#3 FOUR DIGITS

How many positive integers are there where only the digits 1, 2, 3 and 4 are used and no digit is used more than the number it represents?

If the problem was asked for the digits 1 and 2 the answer would be 8

1, 2, 12, 21, 22, 122, 212, 221


有多少个正整数只用到数字 1、2、3 和 4，而且每个数字的使用次数都不超过它所代表的数？

如果问的是数字 1 和 2，答案将是 8:
1, 2, 12, 21, 22, 122, 212, 221

---------
这道题就是牛蛙所不齿的中学排列组合题。

〇〇

貌似newkid的贴被吃掉了，
第3题：
How many positive integers are there where only the digits 1, 2, 3 and 4 are used and no digit is used more than the number it

represents?

If the problem was asked for the digits 1 and 2 the answer would be 8

1, 2, 12, 21, 22, 122, 212, 221

如果只使用数字1、2、3和4，并且没有数字出现的次数比它所表示的数更多，那么有多少这样的正整数？



如果问题被问到数字1和2，答案将是8

with recursive t as (select n::varchar from generate_series(1,4) t(n)),
s as (select 1 lv, n from t
union all
select lv+1,t.n||s.n n from s,t where
regexp_count(s.n,t.n)<t.n::int
)
select
count (1)
from s
;

solomon_007

#2

SQL>
SQL> with t as (select level n from dual connect by level<=4),
  2       s(lvl,N) as (select 1,cast(n as varchar2(100)) from t
  3                     union all
  4                    select lvl + 1,
  5                           s.N||t.n
  6                      from s,t
  7                     where regexp_count(S.N,t.n,1) < t.n
  8                     )
  9  select count(*) from s
10  /

  COUNT(*)
----------
     38847


太简单了。

solomon_007

搞错了，这是第 #3 题。

newkid

暴力法，和你们差不多：
with n as (select level n from dual connect by level<=4)
,t(num) as (
select cast(n as varchar2(20)) from n
union all
select t.num||n
  from t,n
where regexp_count(t.num,n)<n
)
select count(*) from t;

  COUNT(*)
----------
     38847

PL/SQL排列公式：
declare
  s number :=0;
  
  function f(n in number) return number ---- 阶乘
  as
  begin
    return case when n in (0,1) then 1 else n*f(n-1) end;
  end;
begin
  -------- i,j,k,l 分别表示1,2,3,4的使用次数
  for i in 0..1 loop
      for j in 0..2 loop
          for k in 0..3 loop
              for l in 0..4 loop
                  if i+j+k+l>0 then
                     s := s+f(i+j+k+l)/(f(i)*f(j)*f(k)*f(l));
                  end if;
              end loop;
          end loop;
      end loop;
  end loop;
  dbms_output.put_line(s);
end;
/

38847

PL/SQL procedure successfully completed.
  
  
用SQL实现上述算法：
with f(n,f) as (  ------- 构造阶乘表
select 0,1 from dual
union all
select n+1,f*(n+1) from f where n<(select sum(level) from dual connect by level<=4)
)
,t(n,s,f) as (
select 1,level-1,1 from dual connect by level<=2
union all
select t.n+1,t.s+f.n,t.f*f.f
  from t
       ,f
where t.n<4 and f.n<=t.n+1
)     
select sum(f.f/t.f) from t,f where t.n=4 and t.s>0 and t.s=f.n;

SUM(F.F/T.F)
------------
       38847

现在转不了徽章，等系统恢复了转给你们。