問題はこちら->http://nabetani.sakura.ne.jp/hena/orde31rotnum/
for loop で解くつもりだったのとb進数の扱いが便利そうでしたのでJuliaで書きました。
解き方の見当がつかないという問題ではありませんでしたが、
どう解けば、スタックオーバや計算量の過剰らが無く書きやすいかを考えたり、
ちょっとした勘違いがあったりして結構時間がかかりました。
結局わかりやすい再帰で書き、いちいち上限を超えていないか確認しましたが、
上記に関しては杞憂でした。
結果は二数のぐるぐる数の差で求めています。
b進数の桁の小さい部分のぐるぐる数の数は、(b-1)(1+2+2^2+2^3+...)=(b-1)(2^m-1)となり、
最大桁の部分は,最上位桁をxとすると、1からxについて、再帰でぐるぐる数を作り、
上限値を越えなければ、ぐるぐる数の個数に加えます。
(1からx-1までを(x-1)*2^m)とすることも可能ですが、速さは変わりません)
Prologでも書くかどうかは未定です。
#julia 0.6,0.52
str="0 4,1313,3012 12
1 10,100,110 0
2 36,zoo,zyz 0
3 4,1300000,2222221 0
4 2,1,1 1
5 2,1000,1110 7
6 4,21,132 8
7 10,28,79 10
8 36,q,1r 12
9 28,bjb,g9a 16
10 20,2i9d,5id4 24
11 5,12000,24141 24
12 6,1245,5145 28
13 36,1,z 35
14 14,277,dc1 42
15 35,9iy,l5p 44
16 17,7be,19b1 44
17 18,96f,236g 52
18 23,b1f,1k81 56
19 6,143424,353115 64
20 5,3401,40123 67
21 4,321,123022 102
22 13,1b0,8a72 108
23 20,62,339f 124
24 24,f8h,bcn0 124
25 31,do3,78no 124
26 17,727,ced4 136
27 5,14,222243 154
28 16,3c5,100bb 168
29 9,353,80016 200
30 21,h7d,34504 220
31 11,20a,78926 224
32 12,b0,77996 238
33 3,212,11112012 254
34 22,6f2,789hd 340
35 36,5l6,tvmw 352
36 25,db8,99b08 376
37 32,hpi,556a7 376
38 29,1cl,456d2 396
39 34,dli,455u7 404
40 15,ced,3345c1 424
41 30,601,7780o 428
42 3,22,22000021 445
43 5,440,4012303 446
44 27,hg,aaamk 480
45 33,suv,defn7 480
46 2,11,111101110 492
47 35,60e,9aamd 528
48 7,33,3445635 542
49 4,120,22330013 550
50 23,8fk,lm066 564
51 6,142,5001252 568
52 8,111,3344567 572
53 26,4na,klmib 600
54 19,32a,6678g3 672
55 7,605,6011223 680
56 6,15,11235050 692
57 9,664,5567833 746
58 10,909,4556846 746
59 10,991,5555766 769
60 8,757,7700001 812
61 36,6pku,27wr28 856
62 35,6n89a,j1dlik 1024
63 34,7gehm,m0anuo 1088
64 10,3268665,134217728 1856
65 11,571016a,47352388a 2624
66 4,10030022033,10203020123103 21504
67 3,22111101011101,11021122211120221 100352
68 2,101001011010110000110101,110101110001110110110101 3240321"
function calc(k,n,x,y,b)
if k==-1
return 1
else
y1=y+x*b^k
if y1<=n
res1=calc(k-1,n,x,y1,b)
else
res1=0
end
x1=rem(x+1,b)
y2=y+x1*b^k
if y2<=n
res2=calc(k-1,n,x1,y2,b)
else
res2=0
end
return res1+res2
end
end
function solve(s2,s1,b)
m=length(s1)-1
k1=(b-1)*(2^m-1)
h1=0
n=parse(Int32,s1,b)
for i in 1:parse(Int32,s1[1],b)
h1+=calc(m-1,n,i,i*b^m,b)
end
n=parse(Int32,s2,b)-1
s2=base(b,n)
m=length(s2)-1
k2=(b-1)*(2^m-1)
h2=0
for i in 1:parse(Int32,s2[1],b)
h2+=calc(m-1,n,i,i*b^m,b)
end
return h1-h2+k1-k2
end
function main()
str1=split(str,"\n")
for s in str1
s=replace(s, r"\t", s" ")
s1=split(s,r"\s+")
s2=split(s1[2],",")
b=parse(Int32,s2[1])
ans=solve(s2[2],s2[3],b)
if ans==parse(Int32,s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",ans,"\n")
end
end
main()
2019.3.11追加
結局Prologで書きましたので追加します。
最大桁の数をx1とすると(x1-1)b^m+(b-1)b^(m-1)+...の部分までを、前の投稿時述べましたように
(b-1)(1+2+2^2+2^3+...)+(x1-1)*2^m=(b+x1-2)*2^m-(b-1)で計算し、
残り(x1*b^m からx1*b^m+x2*b^(m-1)+...まで)も一列ずつ右にずらしながら同様に処理する方法で、
最初に考えた時の最有力候補でした。
ただ一部で書き方が全く浮かんでこなかったのでいったんあきらめたのですが、
もう一度見直したところ、結構簡単に書けることが分かりました。
この方法だと各処理の部分は2^kか2^(k+1)になります。
%SWI-Prolog version 7.4.2
%start.
%:-initialization(start). %ideone
tenton(B,X,R):-X==0->R=[0];tenton(X,B,[],R).
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X-(X1*B),tenton(X1,B,[R1|L],RL).
ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).
calc(B,[H|T],R):-
calc(B,T,H,R1),length(T,N),R2 is (H+B-2)*2^N-(B-1),R is R1+R2.
calc(_,[],_,1).
calc(B,[H|T],C,R):-H==0,
(C==0;(C+1) mod B==0),calc(B,T,0,R).
calc(B,[H|T],C,R):-
C1 is (C+1) mod B,findall(X,(member(X,[C,C1]),X<H),XL),
length(XL,N1),(N1>0->(length(T,N2),R1=N1*2^N2);R1=0),
(member(H,[C,C1])->calc(B,T,H,R2);R2=0),R is R1+R2.
solve(B,NL,NL2,R):-
ntoten(B,NL,0,X),X1 is X-1,tenton(B,X1,NL1),
calc(B,NL1,R1),calc(B,NL2,R2),R is R2-R1,!.
start:-str(S),
split_string(S,"\n\s","\s",L),pre(L).
pre([]):-!.
pre([_,B,C|T]):-
atomics_to_string(L,",",B),L=[S1,S2,S3],atom_number(S1,N1),
atom_codes(S2,A2),atom_codes(S3,A3),maplist(aton,A2,N2),
maplist(aton,A3,N3),solve(N1,N2,N3,R),disp(R,C),pre(T).
disp(R,C):-
number_string(R,S),(S==C->write("pass ");write(" fail ")),
writeln(S),!.
aton(N,R):-N<60->R is N-48;R is N-87.
str("0 4,1313,3012 12
1 10,100,110 0
2 36,zoo,zyz 0
3 4,1300000,2222221 0
4 2,1,1 1
5 2,1000,1110 7
6 4,21,132 8
7 10,28,79 10
8 36,q,1r 12
9 28,bjb,g9a 16
10 20,2i9d,5id4 24
11 5,12000,24141 24
12 6,1245,5145 28
13 36,1,z 35
14 14,277,dc1 42
15 35,9iy,l5p 44
16 17,7be,19b1 44
17 18,96f,236g 52
18 23,b1f,1k81 56
19 6,143424,353115 64
20 5,3401,40123 67
21 4,321,123022 102
22 13,1b0,8a72 108
23 20,62,339f 124
24 24,f8h,bcn0 124
25 31,do3,78no 124
26 17,727,ced4 136
27 5,14,222243 154
28 16,3c5,100bb 168
29 9,353,80016 200
30 21,h7d,34504 220
31 11,20a,78926 224
32 12,b0,77996 238
33 3,212,11112012 254
34 22,6f2,789hd 340
35 36,5l6,tvmw 352
36 25,db8,99b08 376
37 32,hpi,556a7 376
38 29,1cl,456d2 396
39 34,dli,455u7 404
40 15,ced,3345c1 424
41 30,601,7780o 428
42 3,22,22000021 445
43 5,440,4012303 446
44 27,hg,aaamk 480
45 33,suv,defn7 480
46 2,11,111101110 492
47 35,60e,9aamd 528
48 7,33,3445635 542
49 4,120,22330013 550
50 23,8fk,lm066 564
51 6,142,5001252 568
52 8,111,3344567 572
53 26,4na,klmib 600
54 19,32a,6678g3 672
55 7,605,6011223 680
56 6,15,11235050 692
57 9,664,5567833 746
58 10,909,4556846 746
59 10,991,5555766 769
60 8,757,7700001 812
61 36,6pku,27wr28 856
62 35,6n89a,j1dlik 1024
63 34,7gehm,m0anuo 1088
64 10,3268665,134217728 1856
65 11,571016a,47352388a 2624
66 4,10030022033,10203020123103 21504
67 3,22111101011101,11021122211120221 100352
68 2,101001011010110000110101,110101110001110110110101 3240321").
2019.3.12追加
ちょっと説明を端折った感がありますので、
出題者の@Nabetaniさんの
https://qiita.com/Nabetani/items/d45273ca8e629d3a1a66
に同じ考え方の解説がありますので、ご覧になったら分かりやすいかもしれません。
少し補足しますと、x1と(x1+1) rem bのうちx2より小さいものの個数をnとしますと、
n*2^(m-1)がx1*b^m+x2*b^(m-1)-1までのぐるぐる数の数、
更にx2がx1と(x1+1) rem bのいずれかと等しければ再帰で下位の桁の値を求めます。