問題はこちら->http://nabetani.sakura.ne.jp/hena/orde24tancho/
配列を二つ使いますのでJuliaを使用しました。
k桁目の数字がxの単調増加数の数が、
k-1桁目の数字がx+1以上の単調増加数の合計になることを利用して解きます。
bxbの配列numを作り、配列の最初から、x-1桁目がyの単調増加数の数を、
num[x,y]=num[x-1,y+1]+num[x-1,y+2]+...で求めます。(一桁目はnum[2,])
同時にすべての配列の値を合計していき、それがnになる手前のx,yでnとの差を求め、
get関数で桁をさかのぼってさらにnとの差を計算し、またyをansに登録します。
num[1,b]=1は一桁目の１からb-1にそれぞれ１が入るようにするためものです。
str="0 16,333 38e
1 2,100 -
2 2,1 1
3 2,2 -
4 11,8 8
5 14,9 9
6 11,12 13
7 7,16 34
8 20,16 g
9 2,17 -
10 8,26 56
11 16,51 3c
12 3,77 -
13 2,100 -
14 9,110 1347
15 22,127 78
16 24,142 79
17 30,158 5s
18 20,213 139
19 6,216 -
20 9,244 235678
21 13,253 57c
22 19,265 19c
23 24,314 13k
24 16,333 38e
25 32,353 eo
26 25,490 1dg
27 26,498 1bd
28 10,500 2456789
29 10,543 -
30 3,897 -
31 11,1000 1345789a
32 9,1307 -
33 9,1412 -
34 26,1678 79e
35 8,1942 -
36 12,1950 234589ab
37 2,2245 -
38 18,2670 5ace
39 5,3013 -
40 5,3048 -
41 14,3099 157acd
42 27,3440 13hm
43 13,3698 235689ab
44 36,5592 dqs
45 10,9505 -
46 27,9833 49ej
47 16,10000 123467e
48 24,14090 14bfk
49 29,15270 5mnq
50 17,20000 23458cg
51 36,20000 37bc
52 25,24346 256bk
53 21,27815 146adi
54 25,28030 2aflm
55 25,34448 3cefi
56 36,44811 abpu
test 36,30000000000 134689bdefhijkrstuwyz"
function solve(b,n)
function get(x,y,m)
if x==1
return
end
ans[x]=y
for y1 in y+1:b-x+2
m=m -num[x-1,y1]
if m < 1
get(x-1,y1,m+num[x-1,y1])
break
end
end
end
function str()
s=""
for m in b:-1:1
n=ans[m]
if n>9
s=s*string(Char(n+87))
elseif n>0
s=s*string(n)
end
end
return s
end
sum=0
num=Array(Int,b,b)
ans=Array(Int8,b)
fill!(num,0)
num[1,b]=1
for x in 2:b,
y in 1:b-x+1
for k in 1:b-x-y+2
num[x,y] += num[x-1,y+k]
end
sum += num[x,y]
if sum>=n
get(x,y,n-sum+num[x,y])
return str()
break
end
end
return "-"
end
function main(str)
str1=split(str,"\n")
for s in str1
s1=split(s," ")
s2=split(s1[2],",")
b=parse(s2[1])
n=parse(s2[2])
ans=solve(b,n) #strip 前後の空白削除
if strip(s1[3])==ans
sel="pass"
else
sel="fail"
end
print(sel," ",s1[3]," ",ans,"\n")
end
end
main(str)
2018.6.1追加
Prologに移植しました。
sumを使わずにnから配列の内容を次々に引いています。またansにリストを使っています。
ar(B,F):-functor(F,x,B),twoar(F,B,B). %list->array
twoar(_,0,_). % two dimension array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V). %ar[X,Y]
cal2(F,X,Y,N,YR,NR):-
data(F,X,Y,V),(N>V->(N1 is N-V,Y1 is Y+1,cal2(F,X,Y1,N1,YR,NR));(YR=Y,NR=N)).
cal1(_,2,_,_,L,L):-!.
cal1(F,X,Y,N,L,R):-Y1 is Y+1,X1 is X-1,cal2(F,X1,Y1,N,YR,NR),cal1(F,X1,YR,NR,[YR|L],R).
cal(B,_,_,X,_,_,_,_,[0]):-X>B,!.
cal(B,N,F,X,Y,K,S,L,R):-
K>B-X-Y+2,Y<B-X+2,!,(N>S->(data(F,X,Y,S),N1 is N-S,Y1 is Y+1,cal(B,N1,F,X,Y1,1,0,L,R));
cal1(F,X,Y,N,[Y],R)).
cal(B,N,F,X,Y,_,S,L,R):-
Y>B-X+1,!,X1 is X+1,cal(B,N,F,X1,1,1,S,L,R).
cal(B,N,F,X,Y,K,S,L,R):-
X1 is X-1,YK is Y+K,data(F,X1,YK,V),S1 is S+V,K1 is K+1,cal(B,N,F,X,Y,K1,S1,L,R).
ntos(0,"-"):-!.
ntos(X,S):-X<10,!,X1 is X+48,atom_codes(S,[X1]).
ntos(X,S):-X1 is X+87,atom_codes(S,[X1]).
solve(B,N,R):-
ar(B,F),B1 is B-1,foreach(between(1,B1,X),data(F,1,X,0)),data(F,1,B,1),
cal(B,N,F,2,1,1,0,[],R),!.
disp(R,Q):-
reverse(R,R1),maplist(ntos,R1,L),atomics_to_string(L,"",S),
(S==Q->Str=" yes ";Str=" no "),write(Str),write(S),write("\n").
start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).
pre([]).
pre([_,B,N,Q|T]):-
atom_number(B,NB),atom_number(N,NN),solve(NB,NN,R),disp(R,Q),pre(T).
%start.
str("0 16,333 38e
1 2,100 -
2 2,1 1
3 2,2 -
4 11,8 8
5 14,9 9
6 11,12 13
7 7,16 34
8 20,16 g
9 2,17 -
10 8,26 56
11 16,51 3c
12 3,77 -
13 2,100 -
14 9,110 1347
15 22,127 78
16 24,142 79
17 30,158 5s
18 20,213 139
19 6,216 -
20 9,244 235678
21 13,253 57c
22 19,265 19c
23 24,314 13k
24 16,333 38e
25 32,353 eo
26 25,490 1dg
27 26,498 1bd
28 10,500 2456789
29 10,543 -
30 3,897 -
31 11,1000 1345789a
32 9,1307 -
33 9,1412 -
34 26,1678 79e
35 8,1942 -
36 12,1950 234589ab
37 2,2245 -
38 18,2670 5ace
39 5,3013 -
40 5,3048 -
41 14,3099 157acd
42 27,3440 13hm
43 13,3698 235689ab
44 36,5592 dqs
45 10,9505 -
46 27,9833 49ej
47 16,10000 123467e
48 24,14090 14bfk
49 29,15270 5mnq
50 17,20000 23458cg
51 36,20000 37bc
52 25,24346 256bk
53 21,27815 146adi
54 25,28030 2aflm
55 25,34448 3cefi
56 36,44811 abpu
test 36,30000000000 134689bdefhijkrstuwyz").