「The Clocks」というタイトルの USACO の質問にコードを送信しました。
これは質問へのリンクです: http://ace.delos.com/usacoprob2?a=wj7UqN4l7zk&S=clocks
これは出力です:
コンパイル中... コンパイル: OK 実行中... テスト 1: テスト OK [0.173 秒、13928 KB] テスト 2: テスト OK [0.130 秒、13928 KB] テスト 3: テスト OK [0.583 秒、13928 KB] テスト 4: テスト OK [0.965 秒、13928 KB] > Run 5: 実行エラー: あなたのプログラム (`clocks') は 割り当てられた 1 秒のランタイム (1.584 で終了または停止しました) 秒) テスト ケース 5 が表示された場合。13928 KB の メモリー。 ------ Run 5 のデータ ------ 6 12 12 12 12 12 12 12 12 ---------------------------- プログラムはデータを stdout に出力しました。データは次のとおりです。 ------------------- 時間:_0.40928452 ------------------- テスト 5: ランタイム 1.584>1 (13928 KB)
プログラムが終了する前に完了するのにかかった時間 (秒単位) を出力するようにプログラムを作成しました。
ご覧のとおり、終了するまでに 0.40928452 秒かかりました。では、一体どうして実行時間が 1.584 秒になったのでしょうか? 私はそれについて何をすべきですか?
これが役立つ場合のコードは次のとおりです。
import java.io.*;<br>
import java.util.*;
class clocks {
public static void main(String[] args) throws IOException {
long start = System.nanoTime();
// Use BufferedReader rather than RandomAccessFile; it's much faster
BufferedReader f = new BufferedReader(new FileReader("clocks.in"));
// input file name goes above
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("clocks.out")));
// Use StringTokenizer vs. readLine/split -- lots faster
int[] clock = new int[9];
for (int i = 0; i < 3; i++) {
StringTokenizer st = new StringTokenizer(f.readLine());
// Get line, break into tokens
clock[i * 3] = Integer.parseInt(st.nextToken());
clock[i * 3 + 1] = Integer.parseInt(st.nextToken());
clock[i * 3 + 2] = Integer.parseInt(st.nextToken());
}
ArrayList validCombination = new ArrayList();;
for (int i = 1; true; i++) {
ArrayList combination = getPossibleCombinations(i);
for (int j = 0; j < combination.size(); j++) {
if (tryCombination(clock, (int[]) combination.get(j))) {
validCombination.add(combination.get(j));
}
}
if (validCombination.size() > 0) {
break;
}
}
int [] min = (int[])validCombination.get(0);
if (validCombination.size() > 1){
String minS = "";
for (int i=0; i<min.length; i++)
minS += min[i];
for (int i=1; i<validCombination.size(); i++){
String tempS = "";
int [] temp = (int[])validCombination.get(i);
for (int j=0; j<temp.length; j++)
tempS += temp[j];
if (tempS.compareTo(minS) < 0){
minS = tempS;
min = temp;
}
}
}
for (int i=0; i<min.length-1; i++)
out.print(min[i] + " ");
out.println(min[min.length-1]);
out.close(); // close the output file
long end = System.nanoTime();
System.out.println("time: " + (end-start)/1000000000.0);
System.exit(0); // don't omit this!
}
static boolean tryCombination(int[] clock, int[] steps) {
int[] temp = Arrays.copyOf(clock, clock.length);
for (int i = 0; i < steps.length; i++)
transform(temp, steps[i]);
for (int i=0; i<temp.length; i++)
if (temp[i] != 12)
return false;
return true;
}
static void transform(int[] clock, int n) {
if (n == 1) {
int[] clocksToChange = {0, 1, 3, 4};
add3(clock, clocksToChange);
} else if (n == 2) {
int[] clocksToChange = {0, 1, 2};
add3(clock, clocksToChange);
} else if (n == 3) {
int[] clocksToChange = {1, 2, 4, 5};
add3(clock, clocksToChange);
} else if (n == 4) {
int[] clocksToChange = {0, 3, 6};
add3(clock, clocksToChange);
} else if (n == 5) {
int[] clocksToChange = {1, 3, 4, 5, 7};
add3(clock, clocksToChange);
} else if (n == 6) {
int[] clocksToChange = {2, 5, 8};
add3(clock, clocksToChange);
} else if (n == 7) {
int[] clocksToChange = {3, 4, 6, 7};
add3(clock, clocksToChange);
} else if (n == 8) {
int[] clocksToChange = {6, 7, 8};
add3(clock, clocksToChange);
} else if (n == 9) {
int[] clocksToChange = {4, 5, 7, 8};
add3(clock, clocksToChange);
}
}
static void add3(int[] clock, int[] position) {
for (int i = 0; i < position.length; i++) {
if (clock[position[i]] != 12) {
clock[position[i]] += 3;
} else {
clock[position[i]] = 3;
}
}
}
static ArrayList getPossibleCombinations(int size) {
ArrayList l = new ArrayList();
int[] current = new int[size];
for (int i = 0; i < current.length; i++) {
current[i] = 1;
}
int[] end = new int[size];
for (int i = 0; i < end.length; i++) {
end[i] = 9;
}
l.add(Arrays.copyOf(current, size));
while (!Arrays.equals(current, end)) {
incrementWithoutRepetition(current, current.length - 1);
l.add(Arrays.copyOf(current, size));
}
int [][] combination = new int[l.size()][size];
for (int i=0; i<l.size(); i++)
combination[i] = (int[])l.get(i);
return l;
}
static int incrementWithoutRepetition(int[] n, int index) {
if (n[index] != 9) {
n[index]++;
return n[index];
} else {
n[index] = incrementWithoutRepetition(n, index - 1);
return n[index];
}
}
static void p(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + " ");
}
System.out.println("");
}
}