作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Google Code Jam 2008, Round 1A - C
時間Thu Mar 8 00:27:11 2012
題目敘述網址:
http://code.google.com/codejam/contest/32016/dashboard#s=p2
原本小弟的 algorithm 只能在限定時間內跑完 small dataset,
將 1 <= N <= 1000 印出來觀查後, 發現似乎有以下規律:
(1) 個位數 3 -> 1 -> 5 -> 7 四個一組循環
(2) 末兩位 二十個一組循環 (N = 3 開始)
(3) 末三位 百個一組循環 (N = 3 開始)
於是加了下面一行後, 用 large dataset 驗證, 結果看來似乎是正確的:
if (N > 102) {N %= 100; if (N < 3) {N += 100;}}
但小弟目前還想不懂為何有這樣的規律,
有高手可以解釋一下這個背後是不是有我所不懂的數學原理呢?
[小弟的解答 in Java]
import java.io.*;
import java.util.*;
import java.math.*;
class C
{
private static final boolean ECHO_ON = true;
private static BufferedReader input;
private static BufferedWriter output;
private static final BigInteger BIG0 = BigInteger.valueOf(0);
private static final BigInteger BIG1 = BigInteger.valueOf(1);
private static final BigInteger BIG2 = BigInteger.valueOf(2);
private static final BigInteger BIG3 = BigInteger.valueOf(3);
private static final BigInteger BIG5 = BigInteger.valueOf(5);
private static final BigInteger BIG10 = BigInteger.valueOf(10);
private static final BigInteger BIG1000 = BigInteger.valueOf(1000);
public static BigInteger sqrt(BigInteger X)
{
BigInteger answer = BIG1;
BigInteger interval = BIG1;
for (int i = X.toString().length() / 2; i > 0; i--) interval =
interval.multiply(BIG10);
while (interval.compareTo(BIG1) >= 0)
{
while (answer.multiply(answer).compareTo(X) < 0) answer =
answer.add(interval);
answer = answer.subtract(interval);
interval = interval.divide(BIG10);
}
return answer;
}
public static void main(String[] args)
{
try
{
input = new BufferedReader(new FileReader(args[0] + ".in"));
output = new BufferedWriter(new FileWriter(args[0] + ".out"));
String line = input.readLine();
int T = getInt(line, 0);
for (int i = 1; i <= T; i++)
{
line = input.readLine();
int N = getInt(line, 0);
if (N > 102) {N %= 100; if (N < 3) {N += 100;}}
BigInteger X0 = BIG3;
BigInteger X1 = BIG1;
BigInteger Y0 = BIG1;
BigInteger Y1 = BIG0;
for (int j = N; j > 0; j /= 2)
{
if (1 == j % 2)
{
BigInteger newY0 =
X0.multiply(Y0).add(X1.multiply(Y1).multiply(BIG5));
BigInteger newY1 = X0.multiply(Y1).add(X1.multiply(Y0));
Y0 = newY0;
Y1 = newY1;
}
BigInteger newX0 =
X0.multiply(X0).add(X1.multiply(X1).multiply(BIG5));
BigInteger newX1 = X0.multiply(X1).multiply(BIG2);
X0 = newX0;
X1 = newX1;
}
BigInteger answer = Y1.multiply(Y1).multiply(BIG5);
answer = sqrt(answer);
answer = answer.add(Y0).mod(BIG1000);
String result = "Case #" + i + ": ";
String s = answer.toString();
result += (s.length() > 2) ? s.charAt(s.length() - 3) : "0";
result += (s.length() > 1) ? s.charAt(s.length() - 2) : "0";
result += (s.length() > 0) ? s.charAt(s.length() - 1) : "0";
output(result);
}
input.close();
output.close();
}
catch (Exception e)
{
e.printStackTrace();
}
}
public static int getInt(String line, int index)
{
return Integer.parseInt(getString(line, index));
}
public static String getString(String line, int index)
{
int count = 0;
line = line.trim();
while (count < index)
{
line = line.substring(line.indexOf(' ') + 1);
count++;
}
if ((-1) == line.indexOf(' '))
{
return line;
}
else
{
return line.substring(0, line.indexOf(' '));
}
}
public static void output(String s) throws Exception
{
if (ECHO_ON) {System.out.println(s);}
output.write(s);
output.newLine();
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.30.95