QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268176 | #7753. Energy Distribution | FISHER_ | WA | 569ms | 3860kb | C++14 | 1.6kb | 2023-11-28 12:20:25 | 2023-11-28 12:20:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int w[maxn + 5][maxn + 5];
double e[maxn + 5];
int et[maxn + 5];
double find_fraction(double x) {
double minDiff = x + 1;
int a = 0, b = 1;
for (int i = 1; i <= 1000; i++) {
int j = round(i * x);
double diff = abs(x - (double)j / i);
if (diff < minDiff) {
minDiff = diff;
a = j;
b = i;
}
}
return (double)a / b;
}
int main() {
srand(time(0));
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &w[i][j]);
double ans = 0;
int T2 = 10000;
while (T2--) {
long long es = 0;
for (int i = 1; i <= n; i++) es += et[i] = rand();
for (int i = 1; i <= n; i++) e[i] = 1. * et[i] / es;
int T = 1000;
while (T--) {
int x = rand() % n + 1, y = rand() % n + 1;
while (x == y) x = rand() % n + 1, y = rand() % n + 1;
if (x > y) swap(x, y);
double s = e[x] + e[y];
double c1 = 0, c2 = 0;
for (int i = x + 1; i <= n; i++)
if (i != y) c1 += e[i] * w[x][i];
for (int i = y + 1; i <= n; i++) c1 -= e[i] * w[y][i];
for (int i = 1; i < x; i++) c1 += e[i] * w[i][x];
for (int i = 1; i < y; i++)
if (i != x) c1 -= e[i] * w[i][y];
c2 -= w[x][y], c1 += s * w[x][y];
if (abs(c2) == 0) continue;
e[x] = max(-c1 / (2 * c2), 0.);
e[x] = min(e[x], s);
e[y] = s - e[x];
}
for (int i = 1; i <= n; i++) e[i] = find_fraction(e[i]);
double sum = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) sum += e[i] * e[j] * w[i][j];
ans = max(ans, sum);
}
printf("%.7lf", ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 518ms
memory: 3860kb
input:
2 0 1 1 0
output:
0.2500000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 510ms
memory: 3628kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.5714286
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 511ms
memory: 3648kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.5000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 542ms
memory: 3688kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.7500000
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 569ms
memory: 3844kb
input:
5 0 0 0 4 4 0 0 2 0 4 0 2 0 2 0 4 0 2 0 0 4 4 0 0 0
output:
1.0008926
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '1.0008926', error = '0.0008926'