QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #261469 | #7753. Energy Distribution | yinwuxiao | WA | 0ms | 3956kb | C++14 | 3.0kb | 2023-11-22 22:04:10 | 2023-11-22 22:04:11 |
Judging History
answer
#include <iostream>
#include <cmath>
using namespace std;
const int N = 105;
const double eps = 1e-6;
int n;
double a[N][N];
int c[N],b[N][N],d[N][N];
double w[N];
int gauss() {
int c, r;
for (c = 0, r = 0; c < n; ++c) { // c列r行，遍历列
int t = r;
for (int i = r; i < n; ++i) // 寻找列主元，拿t记录
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue; // 如果列主元为0，不必考虑，当前列全为0
// 交换列主元t行与当前r行的数
for (int i = c; i < n + 1; ++i) swap(a[t][i], a[r][i]);
// 当前列主元已经被交换到了r行，需要从后向前进行处理，避免主对角线元素变成1
for (int i = n; i >= c; --i) a[r][i] /= a[r][c];
// 列主消元
for (int i = r + 1; i < n; ++i)
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; --j)
a[i][j] -= a[r][j] * a[i][c];
++r;
}
// for (int i=0;i<n;i++){
// for (int j=0;j<n+1;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }
// if (r < n) {
// for (int i = r; i < n; ++i)
// if (fabs(a[i][n]) > eps) return 2; // 0x=1 则无解
// // return 1; // 0x=0 无穷多解
// }
// 上三角阶梯型矩阵
// 直接求解即可，最后一列放置结果
for (int i = n - 1; i >= 0; --i)
{
int jl=0;
for (int j=0;j<n;j++) if (a[i][j]>0) {jl=j; break;}
for (int j = i + 1; j < n; ++j)
a[i][n] -= a[j][n] * a[i][j];
if (jl!=i){
a[jl][n]=a[i][n];
a[i][n]=0;
}
}
return 0;
}
int main() {
cin >> n;
int cnt=0;
for(int i=1;i<=n;i++){
int sum=0;
for (int j=1;j<=n;j++){
cin>>b[i][j];
sum+=b[i][j];
}
if (sum>0) c[++cnt]=i;
}
n=cnt;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d[i][j]=b[c[i]][c[j]];
for (int i=0;i<n;i++){
for (int j=0;j<n;j++)
a[i][j]=d[i+1][j+1];
a[i][n]=1;
}
for (int i=0;i<n;i++) a[n][i]=1;
a[n][n+1]=-1;
n++;
// for (int i=0;i<n;i++){
// for (int j=0;j<n+1;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }
int t = gauss();
n--;
for (int i=0;i<n;i++) w[i+1]=a[i][n+1];
// for (int i=1;i<=n+1;i++) cout<<w[i]<<endl;
double ans=0;
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
ans+=d[i][j]*w[i]*w[j];
printf("%.8lf", ans);
// if (t == 0) {
// for (int i = 0; i < n; ++i) printf("%.2lf\n", a[i][n]);
// }
// else if (t == 1) puts("Infinite group solutions");
// else puts("No solution");
return 0;
}
/*
4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3956kb
input:
2 0 1 1 0
output:
0.25000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.57142857
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.50000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.42857143
result:
wrong answer 1st numbers differ - expected: '0.7500000', found: '0.4285714', error = '0.3214286'