TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Description

這是個被蚯蚓稱霸的年代,

蚯蚓的族群主要分為幾大類,

一部分的蚯蚓很胖,我們稱之為胖蚯,

一部分的蚯蚓很神,我們稱之為金蚯,

一部分的蚯蚓很罩,我們稱之為銀蚯,

....

總之,最強大的的蚯蚓,自然就能統治全世界,且大家都以"如皮神一般"或是"如卡恩一般"稱呼之,簡稱"皮卡蚯"。

統治者皮卡蚯最喜歡做的事情就是電人。

由於首都天龍國內的蚯蚓大多都領教過皮卡蚯的電極,於是看到皮卡蚯出巡就會躲得遠遠的。

所以皮卡蚯感到相當空虛,最後他決定離開首都,在鄉下旅行。

某一天,皮卡蚯在四處旅遊和電人的時候,發現有著這裡住的蚯蚓有著非常奇怪的祭典。

這是被稱為長長蚯的一種蚯蚓,顧名思義就是身體非常長的蚯蚓。

有趣的是他們身體的每個環節上都有一個0~9的數字,如果從頭往尾巴閱讀,我們可以把牠看作是一個非常長的整數。

這個奇怪的祭典開始之後,長長蚯長老會把某一隻長長蚯切成兩半,變成兩隻長長蚯。

由於長老刀法有點不太好,所以前半段會被切成n長度,後半段會被切成n+1長度。

有趣的是,長老非常討厭0,所以在切蚯蚓的時候,長老會避開0,以至於n+1長度蚯蚓的開頭不會有0產生。

更令人訝異的是,只要把n+1長度的蚯蚓上拿掉某個環節,就會變成n長度的蚯蚓,數列會完全一模一樣。

長老最後會把兩條蚯蚓看作是n位和n+1位的整數,之後相加,成為今年的幸運數字N。

皮卡蚯相當好奇,對於一個幸運數字N,有幾種長長蚯可以照以上的規則被切成兩半,且相加後變成N,
如果把未切過長長蚯看成一個整數,所有的可能之中,第K大的長長蚯會長什麼樣子。

Input Format

每個測資檔有多筆測資。

第一行有個整數T,表示有T筆測資。
(T<=20)

每一筆測資的第一行有兩個整數N, K。

(1 <= N <= 10100000, K < 231)

Output Format

對於每筆測資,

先在第一行輸出一個整數,代表有多少組符合條件的長長蚯。

第二行則是輸出所有可能之中,第K大的長長蚯。
如果無解,則不要有第二行的存在。

Sample Input

2
21 2147483647
302 5

Sample Output

0
5
01301

Hints

對於N = 302總共有5種長長蚯符合要求。

51 + 251 = 302
27 + 275 = 302
26 + 276 = 302
21 + 281 = 302
01 + 301 = 302

第5大的就是值為1301的長長蚯,

注意,你要輸出整隻長長蚯的樣子,不是輸出牠的值

Problem Source

原TIOJ1730 / Problem Setter : yuscvscv
Source : TOI2010 第1階段 第2次模擬考試 pro4

Subtasks

No. Testdata Range Score
1 0 6
2 1 6
3 2 6
4 3 6
5 4 6
6 5 6
7 6 6
8 7 6
9 8 6
10 9 6
11 10 6
12 11 6
13 12 6
14 13 6
15 14 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6
6 4000 65536 262144 7
7 4000 65536 262144 8
8 4000 65536 262144 9
9 4000 65536 262144 10
10 4000 65536 262144 11
11 4000 65536 262144 12
12 4000 65536 262144 13
13 4000 65536 262144 14
14 4000 65536 262144 15