問題はこちら->http://nabetani.sakura.ne.jp/hena/orde22numord/
1億という数にビビッて計算で解いてみました。
数の列の中にどうしても小さい数や大きい数が混ざってしまいますので、
いわゆる漸近法をつかってみました。
数の列の中の位置を求めるのに、最小値の桁未満で足切りしていますので、
条件の設定が簡単になっています。
このプログラムでは、位置を直接は使わず、1からX番目を求めて、
その中の、最小値未満で同じ桁の数の個数を足し、
大きい数は、求めた位置の数を最大値と同じ桁にしたものと最大値を比較して、
その差を足して新しい位置を求めることを繰り返すことで、目的の位置に達します。
私は、論理を厳密に突き詰められず、試行錯誤に頼る癖があり、
この問題はなかなかバグな取れずに難渋しました。
後から出された3月7日の問題のほうが先にできてしまいました。
足切りをしないプログラムも作ろうと思ったのですが成功しませんでした。
ptol->数の列での位置からD進数を表すリストを求める。
ltop->D進数を表すリストからを求める>数の列での位置をもとめる。
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X mod 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).
ptol(_,_,_,0,R,R):-!.
ptol(0,D,K,X,L,R):-
Y is (D^K-1) div (D-1),N is X div Y,M is X mod Y,K1 is K-1,
(M=:=0->(X1 is Y-1,(L==[]->N1=N;N1 is N-1));
((L==[]->N1 is N+1;N1=N),X1 is M-1)),append(L,[N1],L1),ptol(0,D,K1,X1,L1,R).
ptol(I,D,K,X,L,R):-
Y is D^I*(D^K-1) div (D-1),N is X div Y,M is X mod Y,I1 is I-1,
(M=:=0->(X1 is Y,(L==[]->N1=N;N1 is N-1));
((L==[]->N1 is N+1;N1=N),X1 is M)),append(L,[N1],L1),ptol(I1,D,K,X1,L1,R).
ptol0(K1,D,K2,X,R):-I is K1-1,K is K2-K1+1,ptol(I,D,K,X,[],R),!.
ltop(_,_,_,_,[],N,N):-!.
ltop(0,_,_,1,[X],_,X):-!.
ltop(F,0,D,K,[H|T],N,R):-
(F=:=0->H1 is H-1;H1=H),X is H1*(D^K-1) div (D-1),
K1 is K-1,N1 is N+X+1,F1 is F+1,ltop(F1,_,D,K1,T,N1,R).
ltop(F,I,D,K,[H|T],N,R):-
(F=:=0->H1 is H-1;H1=H),X is H1*D^I*(D^K-1) div (D-1),
N1 is N+X,I1 is I-1,F1 is F+1,ltop(F1,I1,D,K,T,N1,R).
ltop0(K1,D,K2,L,FN):-I is K1-1,K is K2-K1+1,ltop(0,I,D,K,L,0,FN),!.
dec(0,L,L):-!.
dec(K,L,RL):-K1 is K-1,dec(K1,L,L1),reverse(L1,[_|T]),reverse(T,RL).
solve(F,T,D,X,R):-
tenton(F,D,[],FL),tenton(T,D,[],TL),length(FL,K1),length(TL,K2),
asy(FL,F,FN,K1,TL,T,TN,K2,X,X,D,R1),ntoten(D,R1,0,R),!.
asy(FL,F,FN,K1,TL,T,TN,K2,X,TX,D,R):-
ptol0(K1,D,K2,TX,RL),length(RL,LN),
(LN>K1->(W is LN-K1,dec(W,RL,RL1),ltop0(K1,D,K1,RL1,N));ltop0(K1,D,K1,RL,N)),
ltop0(K1,D,K1,FL,FN1),(N<FN1->V is N;V is FN1-1),
length(RL,K3),(K3=K2->ntoten(D,RL,0,Y);(K4 is K2-K3,con(D,K4,RL,Y))),
(Y<T->Y1=T;Y1=Y),
(TX-X<Y1-T+V->(X1 is X+Y1-T+V,asy(FL,F,FN,K1,TL,T,TN,K2,X,X1,D,R));R=RL).
con(D,K,L,Y):-conv(K,L,L2),ntoten(D,L2,0,Y1),Y is Y1-1.
conv(K,L,L2):-length(L1,K),maplist(=(0),L1),append(L,L1,L2).
start:-str(S),split_string(S,"\s,\n","\s",L),pre(L),!.
pre([]):-!.
pre([_,B,C,D,E,F|T]):-
maplist(atom_number,[B,C,D,E,F],[B1,C1,D1,E1,F1]),E2 is E1,solve(B1,C1,D1,E2,R),
(R=:=F1->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(R->F),pre(T).
myatom_char(X,Y):-atom_chars(Y,X).
str("0 2,15,3,8 14
1 6,8,8,1 8
2 6,6,5,1 6
3 4,11,5,2 6
4 9,17,8,2 10
5 73,82,18,5 77
6 70,149,2,48 95
7 82,119,15,26 107
8 40,127,26,47 86
9 851,950,31,89 939
10 660,807,34,143 802
11 962,1227,34,186 1075
12 544,1258,25,245 869
13 1208,7380,2,803 4630
14 2,100000000,10,1 10
15 1642,6626,3,4354 2029
16 8623,15873,2,4188 12810
17 7013,16409,17,3919 10931
18 7222,13243,19,3623 10844
19 4421,87412,5,62080 60697
20 51812,61593,22,2957 54768
21 44260,67742,17,15128 59387
22 90929,696974,36,84356 175284
23 1,100000000,2,50000000 92108858
24 101262,924931,7,341846 358105
25 211114,675661,33,312769 523882
26 1,100000000,36,50000000 11855060
27 1,100000000,10,100000000 99999999
28 826566,1444644,36,186226 1012791
29 6687091,6985458,4,251580 6938670
30 4219082,6179401,12,538113 4757194
31 7781931,8634872,23,217457 7999387
32 818218,64845924,12,57752258 30039084
33 4987258,11760092,32,6741567 11728824
34 7075964,28431054,22,11548591 18624554
35 26065964,66252692,18,29196596 63208819
36 66097362,104618756,16,32740764 98838125").
2018.3.14追加
上の記事の
ltop->D進数を表すリストからを求める>数の列での位置をもとめる。
は
ltop->D進数を表すリストから数の列での位置をもとめる。
の間違いです。
また上のコードでも間違いではありませんが、asyのltop0(K1,D,K1,FL,FN1)は、
solve中にあるのがより正しいコードです。
その他の部分も整理して該当部分のみ再掲載します。
small(D,K1,RL,FN,V):-
length(RL,LN),(LN>K1->(W is LN-K1,dec(W,RL,RL1),ltop0(K1,D,K1,RL1,N));
ltop0(K1,D,K1,RL,N)),(N<FN->V is N;V is FN-1).
big(D,K2,T,RL,V):-
length(RL,K3),(K3=K2->ntoten(D,RL,0,Y1);(K4 is K2-K3,con(D,K4,RL,Y1))),
(Y1=<T->V=0;V is Y1-T).
solve(F,T,D,X,R):-
tenton(F,D,[],FL),tenton(T,D,[],TL),length(FL,K1),length(TL,K2),
ltop0(K1,D,K1,FL,FN),asy(FL,F,FN,K1,TL,T,K2,X,X,D,R1),ntoten(D,R1,0,R),!.
asy(FL,F,FN,K1,TL,T,K2,X,TX,D,R):-
ptol0(K1,D,K2,TX,RL),small(D,K1,RL,FN,VS),big(D,K2,T,RL,VB),
(TX-X<VS+VB->(X1 is X+VS+VB,asy(FL,F,FN,K1,TL,T,K2,X,X1,D,R));R=RL).