※ 引述《ross800127 (ROSS-MAX)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Java
: 問題(Question)：
: 這題概念就是用直式求解，我測試了一些比較小的測資，演算法上應該沒甚麼錯誤，
: 但卻不知為何的WA，原本我是用 C++ 寫，結果發現這題不用大數不行，
: 就改成 Java 的版本，最後送出結果卻是 WA，但是丟到高中生解題系統卻是對的，
: UVa 看不到錯誤的地方在哪，本來期待解題系統可以看到一些訊息。
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: 丟去測試的 Java Code
: http://ideone.com/1q00GL
: 原始的 C++ Code
: http://ideone.com/2Ne7Xk
: 補充說明(Supplement)：
: 題目網址
: http://goo.gl/9LNyP
這題Java不用BigInteger應該還是可以AC的，端看寫法。
可能很多人看到1000位數字就已開始寫自己的大數class，然後寫辦法寫得很快。
換個角度思考，其實不必這麼大費周章。
我用的資料結構如下：
char X[1005], Y[1005], Z[505], A[505];
X是一開始讀進來的數
Y是準備等待減去的數
Z是直式開方左邊的數
A是儲存之答案
關鍵在於替X, Y, Z設定準備運算之左右邊界。
然後相乘，相減的運算都在這邊界裡面。
一輪完了再擴展邊界值。
如此循環而已。
可以加速的地方應該在這個一輪之中如何去找下一個可能的數字。
用二分法是一個方法，
不過考量程式可讀性，我還是從9下搜到0，
真正跑起來也只比我以前AC的code慢40ms而已（0.376s）。
C++的版本：http://ideone.com/3aOhWJ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.112.210