Facebook Hacker Cup 中文翻譯為 臉書駭客盃，雖然叫做駭客盃，實際上則是程式設計競賽。應該是屬於國際級的競賽吧? 這也是我第一次參加競賽以及第一次參與這類如此不同的競賽。而，這整個比賽是在線上進行，時間以格林威治標準時間為準，所以各地都有一定的時差存在。不過也剛好反映出FB的時間計算上的問題…
不過呢，可惜的是，本人我並沒有順利的晉級第二級，至於為什麼? 這就要怪我的粗心大意，沒把整個說明給看清楚囉…
Facebook Hacker Cup Qualification Round
這是資格賽，也就是預賽的部分，比賽時間共計三天，題目共三題。你只要能在這段期間內將題目解出一題以上，你就有機會晉級到下一個階段。
當一點下檔案下載的時候，電腦就會開始計算時間，你必須要在六分鐘以內將答案計算出來並且上傳給FB這樣才算完成。不過這裡我還滿好奇的，因為在結束後，我朋友交出的答案應是沒有問題的答案卻是無法晉級的，這點令我非常的不解，但不管結果如何，也是一種經驗啦~((而我則是亂下載檔案的那位傻瓜…
第一題，算是很簡單又有點需要理解的數學題目，而這題花掉了我一天多的時間去讓計算時間壓縮到0.2秒…(原本要不知道幾小時)。
Double Squares
A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3² + 1². Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3² + 1² (we don’t count 1² + 3² as being different). On the other hand, 25 can be written as 5² + 0²or as 4² + 3².
Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100Output
For each value of X, you should output the number of ways to write X as the sum of two squares.
Example input
5
10
25
3
0
1Example output
1
2
0
1
1
簡單的解釋一下這一題，他是一個雙平方數的拆解，也就是我給一個數字 X 然後這個數字要能拆成兩個平方數的總和。
那麼，我如何拆解的呢?
一開始我的想法是將數字一個一個帶入去計算，也就是利用 for 迴圈下去計算，但這方法有這嚴重的缺點，那就是達速度過於緩慢，數字只要一大，電腦就不知道要算到甚麼時候了…
之後與朋友討論這一題的解法的時候，朋友提出了一個看法：「假設我們把超過一百萬的數字除以一千，然後再下去計算，這樣會不會比較快呢?」
「為什麼要除以1000?」我問。
「你看喔，」他指著一長排由電腦輸出的結果，說：「這些結果根本不會超過它本身除以1000對吧? 所以我們如果加入這樣的判斷，那應該會快很多才對。」
「有道理，我們來試試看！」
之後用這方法果真讓計算時間大幅的縮減，並且壓在6分鐘以內計算完成，只是…只是這樣的速度還是不構快，而且答案似乎有些問題存在。
接下來，經過一些計算之後發現，每一個數字都有一個共通點，就是我將數字開根號之後所得出來的數字去掉尾數之後，再將這數字下去平方並找出另一個整數平方根，就能得出這一數字的一組雙平方(Double Square)，哇~~這真是天大的發現。然後將程式寫出之後，經過驗證，發現這方法是可行的！並且將計算時間大大的從5xx秒壓到0.5秒，這樣的速度根本就是天壤之別啊！
以下直接公布我所撰寫的程式碼，有錯還請指正指正(使用Java撰寫):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
import java.util.Scanner; import java.io.*; public class DoubleSquare { public static void main(String[] args) throws FileNotFoundException { Scanner cin = new Scanner(new FileReader("input.txt")); //Scanner cin = new Scanner("10 16 25 10 1000000 14400 65464 4 64354 4443123 2147444"); DoubleSquareCa ds = new DoubleSquareCa(); double n, i,result,time1,time2; time1 = System.currentTimeMillis(); //時間計算開始 n = cin.nextInt(); for (i = 0; i < n; i++) { result = ds.Cacul(cin.nextDouble()); //開始計算 System.out.println(result); } time2 = System.currentTimeMillis(); //計算結束 System.out.println((time2-time1)/1000+"s"); } } //計算副程式 class DoubleSquareCa { public double Cacul(double x) { double i, t, xt, ans = 0, temp = 0, temp2 = 0,temp3 = 0; //0...不知道算不算一次 if(x==0){ return 1; } //判斷開始 xt =(int) Math.sqrt(x); //將 x 原數開平方根，並去尾數 //因為兩平方數的其中一數最大不會超過自身的平方值 for (i = xt; i >= 1; i--) { if(i==temp3) return ans; //temp3是上一狀態的temp值 t = i * i; //i平方 temp2 = x - t; //x - t = temp2 temp = (int) Math.sqrt(temp2); //去尾數 if ((temp2 == temp*temp) & ((temp2+t) == x)) { //檢驗 //System.out.println("i="+i +" t="+t +" temp="+temp+" temp2="+temp2+" temp3="+temp3); temp3 = temp; ans++; } } return ans; } } |