PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Google Code Jam 2010, Round 1A - C

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/02/20 00:45)推噓1(1推 0噓 5→)

留言6則, 3人參與討論串1/2 (看更多)

題目敘述網址: http://code.google.com/codejam/contest/544101/dashboard#s=p2 雖然小弟的 algorithm 也能在限定時間內跑完 small set 及 large set, 但是看了前幾名的 algorithm, 似乎都有用到 (sqrt(5.0) + 1.0) / 2.0, 有高手可以解釋一下這個神秘的數字是什麼意思嗎? [第一名解答 in C++, <_.._>] #include <iostream> #include <sstream> #include <string> #include <vector> #include <deque> #include <queue> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) template <class T> inline string itos(T n) {return (n)<0?"-"+itos(-(n)):(n)<10?(string)("")+(char)('0'+(n)):itos((n)/10)+itos((n)%10);} typedef long long ll; int case_number; #define printg case_number++, printf("Case #%d: ",case_number), printf #define gout case_number++, printf("Case #%d: ",case_number), cout double golden = (sqrt(5.0) + 1.0) / 2.0; ll main2(int A1, int A2, int B1, int B2){ // A * golden < B ll ans = 0; for(int A=A1;A<=A2;A++){ int x = (int)(A * golden) + 1; x = max(x,B1); if(x <= B2) ans += B2 - x + 1; } return ans; } int main(void){ int number_of_test_cases,i; scanf("%d",&number_of_test_cases); REP(i,number_of_test_cases){ int A1,A2,B1,B2; scanf("%d%d%d%d",&A1,&A2,&B1,&B2); ll ans = main2(A1,A2,B1,B2) + main2(B1,B2,A1,A2); gout << ans << endl; } return 0; } [小弟的解答 in Java, 或許還有可以改進的空間, 互相漏氣求進步囉…] import java.io.*; class GCJ_2010_1A_C { private static final int MAX_NUMBER = 1000000; private static int[] loseBegin = new int[MAX_NUMBER + 1]; private static int[] loseEnd = new int[MAX_NUMBER + 1]; public static void calculateLoseRange() { loseBegin[1] = 1; loseEnd[1] = 1; loseBegin[2] = 2; loseEnd[2] = 3; for (int i = 3; i <= MAX_NUMBER; i++) { int begin = loseBegin[i - 1]; while (loseEnd[begin] < i) { begin++; } loseBegin[i] = begin; loseEnd[i] = begin + i - 1; } } public static void main(String[] args) { try { BufferedReader input = new BufferedReader(new FileReader(args[0])); BufferedWriter output = new BufferedWriter(new FileWriter(args[1])); calculateLoseRange(); String line = input.readLine(); int T = Integer.parseInt(line); for (int i = 1; i <= T; i++) { line = input.readLine(); int A1 = Integer.parseInt(line.substring(0, line.indexOf(' '))); line = line.substring(line.indexOf(' ') + 1); int A2 = Integer.parseInt(line.substring(0, line.indexOf(' '))); line = line.substring(line.indexOf(' ') + 1); int B1 = Integer.parseInt(line.substring(0, line.indexOf(' '))); line = line.substring(line.indexOf(' ') + 1); int B2 = Integer.parseInt(line); long count = 0; for (int j = A1; j <= A2; j++) { int lose = Math.max(0, Math.min(B2, loseEnd[j]) - Math.max(B1, loseBegin[j]) + 1); int win = (B2 - B1 + 1) - lose; count += win; } String result = "Case #" + i + ": " + count; System.out.println(result); // output.write(result); output.newLine(); } input.close(); output.close(); } catch (Exception e) { e.printStackTrace(); } } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.126.30.95