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

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

看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間12年前 (2012/02/20 12:23)推噓0(0推 0噓 1→)

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

※ 引述《RockLee (Now of all times)》之銘言： : 題目敘述網址: : 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(); : } : } : } phi = (sqrt(5) + 1) / 2 prove that (x, y) such that x <= y <= floor(x * phi) is a losing position and (x, y) such that y > floor(x * phi) is a winning position 1. (x, y) is a winning position iff (y, x) is a winning position 2. (x, x) is a losing position for all x > 0 3. if (x, y) is a losing position, (x, y + k * x) and (x + k * y, y) is a winning position (k > 0) 4. if (x, y) is a losing position, (X, Y) = (x, y - k * x) or (x - k * y, y) must satisfy one of, a) X <= 0 or Y <= 0 b) (X, Y) is a winning position for x = 1, floor(x * phi) = 1 and (1, 1) is a losing position (1, k), k > 1 is a winning position HOLDS if the hypothesis holds for x <= X, for x = X + 1 (x, x) is a losing position (by 2) for x < y <= floor(x * phi) we have x < y < phi * x, since phi \notin Q => x * (phi - 1) > y - x > 0 and y - 2*x < 0 consider (y - x) * phi, (y - x) * phi < x * (phi - 1) * phi = x, and y - x <= X => ((y - x), x) is a winnig position => (x, y) is a losing position (by 4) for floor(x * phi) < y for z < x, by induction, (z, x) is a losing position iff x <= floor(z * phi) smallest z happens when x = floor(z * phi) => z * phi - 1 < x <= z * phi => z - (1 / phi) < x / phi <= z => ceil(x / phi) <= z <= ceil(x / phi) => z = ceil(x / phi) (x, z) is a losing position if ceil(x / phi) <= z <= floor(x * phi) x * phi < floor(x * phi) + 1 < x * phi + 1 x / phi <= ceil(x / phi) < x / phi + 1 => - (x / phi + 1) < -ceil(x / phi) < - x / phi => x * (phi - 1 / phi) - 1 < floor(x * phi) - ceil(x / phi) + 1 < x * (phi - 1 / phi) + 1 and phi - 1 / phi = 1 x - 1 < floor(x * phi) - ceil(x / phi) + 1 < x + 1 \therefore floor(x * phi) - ceil(x / phi) + 1 = x \therefore for any y > floor(x * phi), \exists k \in N s.t. (x, y - k * x) is a losing position. hypothesis also holds for x = X + 1 by induction, hypothesis holds for all x \in N -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.4.195