二進数を回す

概要

2つの数値bとnを与える。
平面上に、非負の整数（以下、p）が書かれた丸を並べる。
丸は下図の通り、b 角形の頂点と辺上にある。
辺上の丸は、一番内側が 0個、次が1個、そして2個… となっている。
内側の多角形から順に付番する。真上が最小で、そこから時計回りに付番する。
※ 下図は内側から4層まで描いているが、実際には無限にある。

b=3

b=5

b=11

n（n は入力から来る）を二進数で表したときの各桁に合わせて、丸を塗る。
n の 2進数表現の右から p+1 桁目（つまり、2 の p 乗を表す桁）が 1 なら p と書かれた丸を塗り、0 なら塗らない。
ここで、 0≤r<b である整数 r を考える。
できた図形の「塗る」「塗らない」情報を時計回りに (r÷b)回転回して、回したあとのパターンを数値に戻すことを考える(下図)。

入力の状態:
b=4 n=2345678 (=1000111100101011001110 (2))

r=0 (0/4 回転)

→ 数値に戻すと
2345678
(=1000111100101011001110 (2))

r=1 (1/4 回転)

→ 数値に戻すと
1973037
(=111100001101100101101 (2))

r=2 (2/4 回転)

→ 数値に戻すと
15764651
(=111100001000110010101011 (2))

r=3 (3/4 回転)

→ 数値に戻すと
8680119
(=100001000111001010110111 (2))

数値に戻した結果が最大になるような r と、最小になるような r を求めよ。

入力

入力として、b と n を空白区切りで与える。
b は 3以上の整数。普通に 10進数で記述される。
n も基本は 10進数での記述なんだけど、二進数でゼロが続く場所に、ゼロの個数を [3] のように書くこともある。
例えば n の表記が
654[3]210
なら

654 の 2進数表記 1010001110
3 個の 0
210 の 2進数表記 11010010

をつなげた 101000111000011010010 を二進数だと思って読んだ数値が n となるので、 n=1339602。

出力

最小となる r と最大となる r をスラッシュ ( / ) 区切りで。いずれも 10進数。
最小となる r や最大となる複数ある場合、小さい順にコンマ ( , ) 区切りで並べる。
入力が 5 654[3]210 なら、b=5、n は 654[3]210 を解釈した値である 1339602 となる。 r がとりうる値は 0〜4。下図の通り。

上図の通り回転した結果の数値が最小となる r は 4、最大となる r は 3 となる。
したがって 4/3 を出力すれば良い。

補足

"[ ]" 内の数値も "[ ]" 外の数値も、ゼロになることはない。
先頭が "[数値]" になることはない。
"12[3][4]56" のように、"[数値]" が連続することはない。
不正な入力に対処する必要はない。
入力はJSONでもいいし、このページや図のページの HTML を解析してテストケースを作ってもいい。
実装ができた方は実装例集積所などでお知らせくださると見つけやすくて助かります。
この問題は2025年9月13日開催のオフラインリアルタイムどう書く P.2用に作った問題です。

サンプルデータ

#(図へのリンク)	入力	期待
0	`5 654[3]210`	`4/3`
1	`3 1`	`0/2`
2	`3 7`	`0,1,2/0,1,2`
3	`4 10`	`1,3/0,2`
4	`5 17`	`1/4`
5	`3 511`	`0,1,2/0,1,2`
6	`3 512`	`0/2`
7	`5 21845`	`1/4`
8	`3 262143`	`0,1,2/0,1,2`
9	`3 262144`	`0/2`
10	`10 14516136`	`0/8`
11	`3 259582688`	`0/2`
12	`3 1073741823`	`0,1,2/0,1,2`
13	`3 1073741824`	`0/2`
14	`33 518321832`	`30/4`
15	`5 1073741567`	`3/4`
16	`5 1073741815`	`1/2`
17	`5 1073741823`	`0,1,2,3,4/0,1,2,3,4`
18	`5 1073741824`	`0/4`
19	`123 518321832`	`120/94`
20	`7 5[2]`	`5/2`
21	`3 1[45]`	`0/2`
22	`7 1[80]1`	`5/4`
23	`10 1[65]1`	`9/8`
24	`6 23[38]1`	`0/4`
25	`6 1[1000]1`	`2/1`
26	`7 1[10000]1`	`1/0`
27	`43 123[269]1`	`40/39`
28	`8 1[100000]1`	`4/3`
29	`8 3[6]6[5]34`	`2,6/1,5`
30	`9 1[1000000]1`	`1/0`
31	`10 1[10000000]1`	`3/2`
32	`684 2345[6964]1`	`659/657`
33	`100 1[12]1[631]1`	`92/88`
34	`3163 765[32654]1`	`2958/2957`
35	`6 138547332[57]9`	`0,3/2,5`
36	`8 12345[100000]1`	`4/3`
37	`8 8947848[15]136`	`2,6/3,7`
38	`7 2216757314[69]9`	`0/3`
39	`7853 8765[82626]1`	`7034/7033`
40	`9 34567[1000000]1`	`1/0`
41	`15 798915[4]205064`	`12/11`
42	`1000 1[123]1[7231]1`	`692/660`
43	`15 12483[4]12788040`	`12/8`
44	`15 12483[4]12788042`	`3/11`
45	`15 12483[4]12790090`	`9/11`
46	`49157 9753[311326]1`	`45061/45058`
47	`5 1398101[5]4805983`	`1/2`
48	`5 89478473[2]611679`	`0,1,2,3,4/0,1,2,3,4`
49	`5 89478473[2]613727`	`2/1`
50	`1000 1[234]1[11148]1`	`771/723`
51	`1000 1[345]1[16148]1`	`809/808`
52	`19661 98765[204802]1`	`18023/18019`
53	`10 1234567[10000000]1`	`3/2`
54	`7 1186774455377[99]123`	`4/5`
55	`10000 1[1234]1[105157]1`	`8969/8721`
56	`18 12[50]54[64]18[55]30`	`17/16`
57	`9 264557485[120]649018346`	`7/2`
58	`7 5461[1]89478485[1]89478485`	`6/1`
59	`13 102[9]956[9]641[123]882[9]73`	`10/1`
60	`48 1[23]1[23]1[23]1[23]21[18]84`	`46/45`
61	`50 1[24]1[24]1[24]1[29]21[20]84`	`7,32/19,44`
62	`8 255[8]255[8]255[8]255[224]223`	`1/4`
63	`10 63[4]63[4]63[4]63[4]63[90]959`	`2/5`
64	`100 123[274]654321[185]4321[97]1`	`4/98`
65	`12 7[9]7[9]7[9]7[9]7[9]7[170]3276`	`2,6,10/1,5,9`
66	`6 1[16]1[16]1[16]1[16]1[16]1[814]2`	`5/4`
67	`65 45[33]45[33]45[33]45[33]45[209]`	`9,22,35,48,61/7,20,33,46,59`
68	`100 895[10]895[10]895[10]895[10]895`	`0,20,40,60,80/13,33,53,73,93`
69	`65 45[33]45[33]45[33]45[33]45[208]1`	`9/59`
70	`8 21845[1]21845[1]349525[1]89478485`	`0,2,4,6/1,3,5,7`
71	`284 877[203]877[203]877[203]877[856]`	`70,141,212,283/66,137,208,279`
72	`7 33[10]809[6]1135001[10]5761[6]168968`	`3/5`
73	`666 116[298]320[755]975[274]638[275]631`	`329/175`
74	`97914 943208[20323]465546[196660]476743`	`48531/48522`
75	`9891 7945[4755]1907[5867]8563[4854]6020`	`9463/7073`
76	`284 1[1]877[203]877[203]877[203]877[856]`	`70/279`
77	`921 679845[1515]679845[1515]679845[7453]`	`659/656`
78	`174 45[81]45[81]45[81]45[81]45[81]45[544]`	`22,51,80,109,138,167/20,49,78,107,136,165`
79	`11 142884933[20]9[63]11363[26]4868371[21]1`	`10/5`
80	`174 45[81]45[81]45[81]45[81]45[81]45[543]1`	`22/165`
81	`10 5461[1]349525[1]5592405[1]22369621[1]43690`	`1,3,5,7,9/0,2,4,6,8`
82	`32151 73861[1119]67102[76462]93250[18847]87550`	`32143/32142`
83	`244 454767[286]454767[286]454767[286]454767[2464]`	`57,118,179,240/53,114,175,236`
84	`12 153391689[2]19173961[2]299593[2]37449[2]4793490`	`2,5,8,11/1,4,7,10`
85	`244 454767[286]454767[286]454767[286]454767[2460]15`	`57/236`
86	`47655 321472[13843]247107[88808]358721[197388]434131`	`47579/44111`
87	`3126 45[1557]45[1557]45[1557]45[1557]45[1557]45[9400]`	`514,1035,1556,2077,2598,3119/512,1033,1554,2075,2596,3117`

#(図へのリンク)

入力

期待

5 654[3]210

4/3

3 1

0/2

3 7

0,1,2/0,1,2

4 10

1,3/0,2

5 17

1/4

3 511

0,1,2/0,1,2

3 512

0/2

5 21845

1/4

3 262143

0,1,2/0,1,2

3 262144

0/2

10 14516136

0/8

3 259582688

0/2

3 1073741823

0,1,2/0,1,2

3 1073741824

0/2

33 518321832

30/4

5 1073741567

3/4

5 1073741815

1/2

5 1073741823

0,1,2,3,4/0,1,2,3,4

5 1073741824

0/4

123 518321832

120/94

7 5[2]

5/2

3 1[45]

0/2

7 1[80]1

5/4

10 1[65]1

9/8

6 23[38]1

0/4

6 1[1000]1

2/1

7 1[10000]1

1/0

43 123[269]1

40/39

8 1[100000]1

4/3

8 3[6]6[5]34

2,6/1,5

9 1[1000000]1

1/0

10 1[10000000]1

3/2

684 2345[6964]1

659/657

100 1[12]1[631]1

92/88

3163 765[32654]1

2958/2957

6 138547332[57]9

0,3/2,5

8 12345[100000]1

4/3

8 8947848[15]136

2,6/3,7

7 2216757314[69]9

0/3

7853 8765[82626]1

7034/7033

9 34567[1000000]1

1/0

15 798915[4]205064

12/11

1000 1[123]1[7231]1

692/660

15 12483[4]12788040

12/8

15 12483[4]12788042

3/11

15 12483[4]12790090

9/11

49157 9753[311326]1

45061/45058

5 1398101[5]4805983

1/2

5 89478473[2]611679

0,1,2,3,4/0,1,2,3,4

5 89478473[2]613727

2/1

1000 1[234]1[11148]1

771/723

1000 1[345]1[16148]1

809/808

19661 98765[204802]1

18023/18019

10 1234567[10000000]1

3/2

7 1186774455377[99]123

4/5

10000 1[1234]1[105157]1

8969/8721

18 12[50]54[64]18[55]30

17/16

9 264557485[120]649018346

7/2

7 5461[1]89478485[1]89478485

6/1

13 102[9]956[9]641[123]882[9]73

10/1

48 1[23]1[23]1[23]1[23]21[18]84

46/45

50 1[24]1[24]1[24]1[29]21[20]84

7,32/19,44

8 255[8]255[8]255[8]255[224]223

1/4

10 63[4]63[4]63[4]63[4]63[90]959

2/5

100 123[274]654321[185]4321[97]1

4/98

12 7[9]7[9]7[9]7[9]7[9]7[170]3276

2,6,10/1,5,9

6 1[16]1[16]1[16]1[16]1[16]1[814]2

5/4

65 45[33]45[33]45[33]45[33]45[209]

9,22,35,48,61/7,20,33,46,59

100 895[10]895[10]895[10]895[10]895

0,20,40,60,80/13,33,53,73,93

65 45[33]45[33]45[33]45[33]45[208]1

9/59

8 21845[1]21845[1]349525[1]89478485

0,2,4,6/1,3,5,7

284 877[203]877[203]877[203]877[856]

70,141,212,283/66,137,208,279

7 33[10]809[6]1135001[10]5761[6]168968

3/5

666 116[298]320[755]975[274]638[275]631

329/175

97914 943208[20323]465546[196660]476743

48531/48522

9891 7945[4755]1907[5867]8563[4854]6020

9463/7073

284 1[1]877[203]877[203]877[203]877[856]

70/279

921 679845[1515]679845[1515]679845[7453]

659/656

174 45[81]45[81]45[81]45[81]45[81]45[544]

22,51,80,109,138,167/20,49,78,107,136,165

11 142884933[20]9[63]11363[26]4868371[21]1

10/5

174 45[81]45[81]45[81]45[81]45[81]45[543]1

22/165

10 5461[1]349525[1]5592405[1]22369621[1]43690

1,3,5,7,9/0,2,4,6,8

32151 73861[1119]67102[76462]93250[18847]87550

32143/32142

244 454767[286]454767[286]454767[286]454767[2464]

57,118,179,240/53,114,175,236

12 153391689[2]19173961[2]299593[2]37449[2]4793490

2,5,8,11/1,4,7,10

244 454767[286]454767[286]454767[286]454767[2460]15

57/236

47655 321472[13843]247107[88808]358721[197388]434131

47579/44111

3126 45[1557]45[1557]45[1557]45[1557]45[1557]45[9400]

514,1035,1556,2077,2598,3119/512,1033,1554,2075,2596,3117

概要

入力

出力

補足

サンプルデータ

JSON 形式のテストデータ