0
我提交了关于USACO题为“时钟”的问题的代码。USACO上的时钟
这是链接到的问题：http://ace.delos.com/usacoprob2?a=wj7UqN4l7zk&S=clocks
这是输出：
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.173 secs, 13928 KB]
Test 2: TEST OK [0.130 secs, 13928 KB]
Test 3: TEST OK [0.583 secs, 13928 KB]
Test 4: TEST OK [0.965 secs, 13928 KB]
> Run 5: Execution error: Your program (`clocks') used more than the
allotted runtime of 1 seconds (it ended or was stopped at 1.584
seconds) when presented with test case 5. It used 13928 KB of
memory.
------ Data for Run 5 ------
6 12 12
12 12 12
12 12 12
----------------------------
Your program printed data to stdout. Here is the data:
-------------------
time:_0.40928452
-------------------
Test 5: RUNTIME 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("");
}
}
如果我没有记错，他们给予额外的表演时间到Java。 – alternative 2010-10-26 00:15:28