83 . 調校高棕櫚！

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

會寫程式的羊
咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩

User's AC Ratio

100.0% (16/16)

Submission's AC Ratio

95.2% (20/21)

Tags

Algo Algo25_a

Description

為了可以獲得最高品質的高棕櫚，円円族花了許多年的時間建造了一間研究所，裡面唯一的工作內容就是研究高棕櫚的基因密碼。研究了大約三個月後，他們發現兩個驚人的事實：

1. 所有高棕櫚的基因序列都可以用一個正整數 $n$ 表示。
2. 高棕櫚的基因生成機制非常奇妙，如果親代的基因序列是 $a$ ，那麼它的子代基因序列 $b$ 會等於 $a$ 的所有位數的積。舉例來說，如果 $a=96633$ ，那麼 $b$ 就會等於 $9\times 6\times 6\times 3\times 3=2916$。

現在円円們想要嘗試製造某些特定基因序列的高棕櫚出來做實驗，所以他們必須找到合適的親代來生出他們想要的目標子代。然而如你所見，要找到基因序列很大的高棕櫚並不容易（往往需要序列更大的親代），所以他們你幫忙寫一個程式，給你目標子代的基因序列 $b$ ，請告訴他們最小可以達成目標的親代基因序列 $a$ 是多少呢？

Input Format

輸入的第一行是一個正整數 $T$ ，代表円円們有幾個目標子代序列需要計算。接下來的 $T$ 行每行都是一個非負整數 $N$ ，代表目標子代的基因序列。

對於 $40\%$ 的測試資料保證 $N\leq 1000$
對於 $80\%$ 的測試資料保證 $N\leq 10^ 9$
對於 $100\%$ 的測試資料保證 $N\leq 10^{14}, T\leq 100$

Output Format

對於每組詢問，輸出最小的可達成目標的親代基因序列。如果找不到任何合適的親代基因序列，請輸出$-1$。

Sample Input 1

5
1
10
123456789
216
26

Sample Output 1

1
25
-1
389
-1

Hints

以第二筆詢問為例， $2\times 5 = 10$ ，並且 $25$ 是所有符合條件的非負整數裡面最小的一個。

Problem Source

NEOJ Problem 91

Subtasks

No. Testdata Range Constraints Score
1 0~3 40
2 0~7 40
3 0~9 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 65536 1 2 3
1 3000 65536 65536 1 2 3
2 3000 65536 65536 1 2 3
3 3000 65536 65536 1 2 3
4 3000 65536 65536 2 3
5 3000 65536 65536 2 3
6 3000 65536 65536 2 3
7 3000 65536 65536 2 3
8 3000 65536 65536 3
9 3000 65536 65536 3
Submit out of contest
Back to Top