2011年12月17日 星期六

11258 - String Partition

John是一位ACM程式題目的出題者,他這次想出一題超簡單的題目,給定一列非負整數,請將所有數值相加。

但是他在產生輸入資料時犯了一個錯誤,就是忘了在一列整數之間輸出用來分隔的空白字元,這導致所有數值都連在一起變成一列字串。

最後他將問題改成:請將該字串分割成數個以非零開頭的32位元有號整數(但可包含0),請找出使所有數字的總和最大的分割方式,並輸出其總和。

Input
輸入資料的第一列有一個整數N(<= 500)表示測試資料的組數,每組資料一列包含最多200個位數的數字。

Output
請依題意輸出最大的數字總和。

Sample input

6
1234554321
5432112345
000
121212121212
2147483648
11111111111111111111111111111111111111111111111111111

Sample output
1234554321
543211239
0
2121212124
214748372
5555555666


原文出處

沒有留言:

張貼留言