作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Google Code Jam 2010, Round 1A - C
時間Mon Feb 20 00:45:52 2012
題目敘述網址:
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
1F：推 scwg:golden ratio 02/20 00:58
2F：→ RockLee:感謝 S 大迅速的回覆. 有人可以進一步開示一下, 02/20 06:14
3F：→ RockLee:這個題目是如何推導到用 golden ratio 來解的嗎? 02/20 06:14
4F：→ RockLee:<_.._> 02/20 06:15
5F：→ LPH66:或者可以搜尋「歐氏對局」 02/20 15:09
6F：→ RockLee:感謝 L 大的開示, 我找到相關的說明了 02/20 15:46