辞書順に数を並べる 2018.3.3

問題の概要

4つの数 m, n, b, x を指定する。
m 以上 n 以下の整数を b 進数で表記した文字列を考える。
これらの文字列を辞書順に整列したとき、若い方から x 番目になる数を 10 進数で答えよ。

例えば。

(m, n, b, x) = ( 2, 15, 3, 8 ) のとき。
2 以上 15 以下の整数を 3 進数で表記した結果を辞書順に整列すると

順序	文字列(3進数)	値(10進数)
1	10	3
2	100	9
3	101	10
4	102	11
5	11	4
6	110	12
7	111	13
8	112	14
9	12	5
10	120	15
11	2	2
12	20	6
13	21	7
14	22	8

となる。

8 番目は 10進数で 14 なので「 14 」を出力すれば良い。

入力

入力は、m, n, b, x をコンマ区切りで並べたもの。いずれも 10進数。

出力

出力は、b 進数で表現したときに辞書順で x 番目になる値を、10進数で。

補足

順序の先頭は 1。0 ではない。
0＜m≦n≦一億で、0＜x≦(n-m+1) 。2≦b≦36。いずれも整数。
不正な入力に対処する必要はない。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。
この問題は2018年3月3日に開催されるオフラインリアルタイムどう書くE22 の問題です。イベントについては Doorkeeper のページの方を御覧下さい。

サンプルデータ

#	入力	期待
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`

C/C++/Java 用のテストデータ

/*0*/ test( "2,15,3,8", "14" );
/*1*/ test( "6,8,8,1", "8" );
/*2*/ test( "6,6,5,1", "6" );
/*3*/ test( "4,11,5,2", "6" );
/*4*/ test( "9,17,8,2", "10" );
/*5*/ test( "73,82,18,5", "77" );
/*6*/ test( "70,149,2,48", "95" );
/*7*/ test( "82,119,15,26", "107" );
/*8*/ test( "40,127,26,47", "86" );
/*9*/ test( "851,950,31,89", "939" );
/*10*/ test( "660,807,34,143", "802" );
/*11*/ test( "962,1227,34,186", "1075" );
/*12*/ test( "544,1258,25,245", "869" );
/*13*/ test( "1208,7380,2,803", "4630" );
/*14*/ test( "2,100000000,10,1", "10" );
/*15*/ test( "1642,6626,3,4354", "2029" );
/*16*/ test( "8623,15873,2,4188", "12810" );
/*17*/ test( "7013,16409,17,3919", "10931" );
/*18*/ test( "7222,13243,19,3623", "10844" );
/*19*/ test( "4421,87412,5,62080", "60697" );
/*20*/ test( "51812,61593,22,2957", "54768" );
/*21*/ test( "44260,67742,17,15128", "59387" );
/*22*/ test( "90929,696974,36,84356", "175284" );
/*23*/ test( "1,100000000,2,50000000", "92108858" );
/*24*/ test( "101262,924931,7,341846", "358105" );
/*25*/ test( "211114,675661,33,312769", "523882" );
/*26*/ test( "1,100000000,36,50000000", "11855060" );
/*27*/ test( "1,100000000,10,100000000", "99999999" );
/*28*/ test( "826566,1444644,36,186226", "1012791" );
/*29*/ test( "6687091,6985458,4,251580", "6938670" );
/*30*/ test( "4219082,6179401,12,538113", "4757194" );
/*31*/ test( "7781931,8634872,23,217457", "7999387" );
/*32*/ test( "818218,64845924,12,57752258", "30039084" );
/*33*/ test( "4987258,11760092,32,6741567", "11728824" );
/*34*/ test( "7075964,28431054,22,11548591", "18624554" );
/*35*/ test( "26065964,66252692,18,29196596", "63208819" );
/*36*/ test( "66097362,104618756,16,32740764", "98838125" );

順序	文字列(3進数)	値(10進数)
1	10	3
2	100	9
3	101	10
4	102	11
5	11	4
6	110	12
7	111	13
8	112	14
9	12	5
10	120	15
11	2	2
12	20	6
13	21	7
14	22	8

順序	文字列(3進数)	値(10進数)
1	10	3
2	100	9
3	101	10
4	102	11
5	11	4
6	110	12
7	111	13
8	112	14
9	12	5
10	120	15
11	2	2
12	20	6
13	21	7
14	22	8

順序	文字列(3進数)	値(10進数)
1	10	3
2	100	9
3	101	10
4	102	11
5	11	4
6	110	12
7	111	13
8	112	14
9	12	5
10	120	15
11	2	2
12	20	6
13	21	7
14	22	8