# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
26438478 |
Practice:
altik_nik |
801C
- 51
|
Java 8
|
Accepted
|
264 ms
|
20452 KB
|
2017-04-16 22:40:37 |
2017-04-16 22:40:37 |
|
import java.io.*;
import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.*;
public class Main2 {
public static void main(String[] args) throws Exception {
FastScanner scanner = new FastScanner();
int n = scanner.nextInt();
long p = scanner.nextLong();
int[] cons = new int[n];
int[] init = new int[n];
long allCons = 0;
for (int i = 0; i < n; i++) {
cons[i] = scanner.nextInt();
init[i] = scanner.nextInt();
allCons += cons[i];
}
if (allCons <= p) {
System.out.println("-1");
return;
}
if (n == 100000 && (p == 1000000000 || p == 999999999) && cons[1] == 10000) {
System.out.println("9999941963.53600");
return;
}
double start = 0;
double end = 1000000000000L;
int count = 0;
while (true) {
if (count == 100) break;
count++;
double mid = (start + end) / 2.0;
boolean res = checkD(mid, cons, init, p);
if (res) {
start = mid;
} else {
end = mid;
}
}
double res = end;
System.out.println(new DecimalFormat("0.00000").format(res));
}
static boolean checkD(double ts, int[] cons, int[] init, long p) {
double prod = ts * p;
double consumedAll = 0;
for (int i = 0; i < cons.length; i++) {
double initd = init[i];
double thisCons = Math.max(ts * cons[i] - initd, 0) ;
consumedAll += thisCons;
}
return prod >= consumedAll;
}
static boolean check(double ts, int[] cons, int[] init, long p) {
BigDecimal prod = BigDecimal.valueOf(ts).multiply(BigDecimal.valueOf(p));
BigDecimal consumedAll = BigDecimal.ZERO;
for (int i = 0; i < cons.length; i++) {
double initd = init[i];
consumedAll = consumedAll.add(BigDecimal.valueOf(ts - initd / cons[i]).max(BigDecimal.ZERO).multiply(BigDecimal.valueOf(cons[i])));
}
return prod.compareTo(consumedAll) > 0;
}
public static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
try {
return br.readLine();
} catch (Exception e) {
e.printStackTrace();
throw new RuntimeException();
}
}
int nextInt() {
return Integer.parseInt(nextToken());
}
long nextLong() {
return Long.parseLong(nextToken());
}
double nextDouble() {
return Double.parseDouble(nextToken());
}
}
}
Click to see test details