/
BridgeCrossing.java
114 lines (103 loc) · 3.24 KB
/
BridgeCrossing.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BridgeCrossing {
public int minTime(int[] times) {
List<Integer> rest = Arrays.stream(times).sorted().boxed().collect(Collectors.toList());
int result = 0;
while (!rest.isEmpty()) {
int size = rest.size();
if (size == 1) {
result += rest.remove(rest.size() - 1);
} else if (size == 2) {
result += rest.remove(rest.size() - 1);
rest.remove(rest.size() - 1);
} else if (size == 3) {
result += rest.remove(rest.size() - 1);
result += rest.remove(rest.size() - 1);
result += rest.remove(rest.size() - 1);
} else {
result += rest.remove(rest.size() - 1);
result += rest.get(0);
result += Math.min(rest.get(1) * 2, rest.get(0) + rest.remove(rest.size() - 1));
}
}
return result;
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
private static boolean KawigiEdit_RunTest(int testNum, int[] p0, boolean hasAnswer, int p1) {
System.out.print("Test " + testNum + ": [" + "{");
for (int i = 0; p0.length > i; ++i) {
if (i > 0) {
System.out.print(",");
}
System.out.print(p0[i]);
}
System.out.print("}");
System.out.println("]");
BridgeCrossing obj;
int answer;
obj = new BridgeCrossing();
long startTime = System.currentTimeMillis();
answer = obj.minTime(p0);
long endTime = System.currentTimeMillis();
boolean res;
res = true;
System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
if (hasAnswer) {
System.out.println("Desired answer:");
System.out.println("\t" + p1);
}
System.out.println("Your answer:");
System.out.println("\t" + answer);
if (hasAnswer) {
res = answer == p1;
}
if (!res) {
System.out.println("DOESN'T MATCH!!!!");
} else if ((endTime - startTime) / 1000.0 >= 2) {
System.out.println("FAIL the timeout");
res = false;
} else if (hasAnswer) {
System.out.println("Match :-)");
} else {
System.out.println("OK, but is it right?");
}
System.out.println("");
return res;
}
public static void main(String[] args) {
boolean all_right;
all_right = true;
int[] p0;
int p1;
// ----- test 0 -----
p0 = new int[] {1, 2, 5, 10};
p1 = 17;
all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
// ------------------
// ----- test 1 -----
p0 = new int[] {1, 2, 3, 4, 5};
p1 = 16;
all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
// ------------------
// ----- test 2 -----
p0 = new int[] {100};
p1 = 100;
all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
// ------------------
// ----- test 3 -----
p0 = new int[] {1, 2, 3, 50, 99, 100};
p1 = 162;
all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
// ------------------
if (all_right) {
System.out.println("You're a stud (at least on the example cases)!");
} else {
System.out.println("Some of the test cases had errors.");
}
}
// END KAWIGIEDIT TESTING
}
// Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!