Skip to content

Instantly share code, notes, and snippets.

@yarrr-ru

yarrr-ru/C.java Secret

Created Mar 4, 2019
Embed
What would you like to do?
import java.io.*;
import java.util.*;
import java.math.*;
public class C implements Runnable {
private static BufferedReader in;
private static PrintWriter out;
private static StringTokenizer st;
private static Random rnd;
class Row {
long[] first;
BigDecimal second;
public Row(long[] first, BigDecimal second) {
this.first = first;
this.second = second;
}
}
int reduceToRowEchelonForm(Row[] matrix, int cols) {
int rank = 0;
for (int column = 0; column < cols; ++column) {
boolean found = false;
for (int row = rank; row < matrix.length; ++row) {
if (matrix[row].first[column] != 0) {
found = true;
Row swap = matrix[row];
matrix[row] = matrix[rank];
matrix[rank] = swap;
break;
}
}
if (!found) {
continue;
}
for (int r = rank + 1; r < matrix.length; ++r) {
while (matrix[r].first[column] != 0) {
long multiplier = matrix[r].first[column] / matrix[rank].first[column];
for (int c = column; c < cols; ++c) {
matrix[r].first[c] -= multiplier * matrix[rank].first[c];
}
matrix[r].second = matrix[r].second
.subtract(new BigDecimal(multiplier).multiply(matrix[rank].second));
if (matrix[r].first[column] != 0) {
Row swap = matrix[r];
matrix[r] = matrix[rank];
matrix[rank] = swap;
}
}
}
++rank;
}
return rank;
}
private void solve() throws IOException {
int y = nextInt(), c = nextInt();
--y;
int q = nextInt();
int row_len = 2 * c + y;
ArrayList<Row> known_rows_all = new ArrayList<>();
for (int i = 0; i < y; ++i) {
double x = nextDouble();
if (x > -0.5) {
long[] row = new long[row_len];
row[2 * c + i] = 1;
known_rows_all.add(new Row(row, new BigDecimal(Math.log(x))));
}
}
for (int cur_y = 0; cur_y <= y; ++cur_y) {
for (int id = 0; id < c; ++id) {
double x = nextDouble();
if (x > -0.5) {
long[] row = new long[row_len];
row[id] = 1;
row[id + c] = cur_y;
for (int t = 0; t < cur_y; ++t) {
row[2 * c + t] = 1;
}
known_rows_all.add(new Row(row, new BigDecimal(Math.log(x))));
}
}
}
Row[] known_rows = known_rows_all.stream().toArray(Row[]::new);
int initial_rank = reduceToRowEchelonForm(known_rows, row_len);
Row[] copy = new Row[initial_rank + 1];
for (int i = 0; i <= initial_rank; i++) {
copy[i] = new Row(new long[row_len], new BigDecimal(0));
}
BigDecimal[] drow = new BigDecimal[row_len];
for (int qq = 0; qq < q; ++qq) {
int id = nextInt(), cur_y = nextInt();
--id;
--cur_y;
Row new_row = copy[initial_rank];
new_row.first[id] = 1;
new_row.first[id + c] = cur_y;
for (int t = 0; t < cur_y; ++t) {
new_row.first[2 * c + t] = 1;
}
for (int i = 0; i < row_len; i++) {
drow[i] = new BigDecimal(new_row.first[i]);
}
for (int i = 0; i < initial_rank; i++) {
System.arraycopy(known_rows[i].first, 0, copy[i].first, 0, row_len);
copy[i].second = known_rows[i].second;
}
int new_rank = reduceToRowEchelonForm(copy, row_len);
if (initial_rank == new_rank) {
BigDecimal ans = new BigDecimal(0);
for (int i = 0; i < initial_rank; ++i) {
int first = 0;
while (known_rows[i].first[first] == 0) {
++first;
}
BigDecimal mult = drow[first].divide(new BigDecimal(known_rows[i].first[first]));
for (int j = first; j < row_len; ++j) {
drow[j] = drow[j].subtract(mult.multiply(new BigDecimal(known_rows[i].first[j])));
}
ans = ans.add(mult.multiply(known_rows[i].second));
}
out.println(Math.exp(ans.doubleValue()));
} else {
out.println(-1.0);
}
}
}
public static void main(String[] args) {
new C().run();
}
public void run() {
try {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
rnd = new Random();
solve();
out.close();
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
}
private String nextToken() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = in.readLine();
if (line == null)
return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
private double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment