This repository was archived by the owner on Feb 29, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathangry.java
More file actions
78 lines (69 loc) · 1.9 KB
/
angry.java
File metadata and controls
78 lines (69 loc) · 1.9 KB
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
import java.io.*;
import java.util.*;
/*
* Angry Cows: Silver Edition
*/
public class angry {
static List<Integer> field = new ArrayList<Integer>();
public static int N;
public static int launchSim(int power){
//System.out.println("Power: "+power);
int cowsUsed = 0;
int curCow = 0;
int power2 = power*2;
int l,range;
// /int lastCow = field.get(field.size() - 1);
while(curCow < N) {
cowsUsed++;
int pos = field.get(curCow);
l = curCow + 1;
range =0;
//System.out.println("Checking "+curCow + " In range "+curCow + " " + (curCow + 2 * power));
for(int i = l; i < N; i ++) {
if(field.get(i) <= pos + power2) {
//System.out.println(field.get(i)+" In range "+i);
range++;
}
}
//curCow++;
curCow = curCow + range + 1;
// curCow ++;
}
return cowsUsed;
}
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new FileReader("angry.in"));
StringTokenizer st = new StringTokenizer(f.readLine());
N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken()); // Number of cows
//List<Integer> costs = new ArrayList<Integer>(N - 1);
for(int i = 0; i < N; i ++) {
field.add(Integer.parseInt(f.readLine()));
}
f.close();
field.sort(null);
int answer = -1;
int l = 0;
int r = 1000000000;
while (r - l > 1) {
int m = (l + r) / 2;
int t = launchSim(m);
if (t < K) {
r = m;
}else if(K == t) {
// System.out.println("Got it");
r = m;
//break;
}else {
l = m;
}
}
//System.out.println(field);
//System.out.println(costs);
System.out.println(r +" "+l+" "+answer);
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));
pw.println(r);
pw.close();
//System.out.println("");
}
}