QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623114 | #8795. Mysterious Sequence | rns_rds# | WA | 0ms | 4008kb | C++23 | 1.5kb | 2024-10-09 10:14:09 | 2024-10-09 10:14:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using Z = long double; // not necessary, maybe MINT
struct Mat {
vector<vector<Z>> a;
static int D;
const static void setD(int _D) {
D = _D;
}
Mat(int k = 0) {
a.assign(D, vector<Z>(D, 0));
for (int i = 0; i < D; i++)
a[i][i] = k;
}
Mat operator*(const Mat &x) {
Mat res;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
for (int k = 0; k < D; k++)
res.a[i][j] += a[i][k] * x.a[k][j];
return res;
}
Mat pow(long long k) {
Mat res = Mat(1.0), b = *this;
for (; k; k >>= 1) {
if (k & 1) res = res * b;
b = b * b;
}
return res;
}
};
int Mat::D = 2;
// See RNS_CONTEST_2023::D
int main() {
long double A, B;
int n;
long double x1, xn;
cin >> A >> B >> n >> x1 >> xn;
if (n == 2) {
cout << x1 << '\n'
<< xn << '\n';
return 0;
}
Mat matrix;
matrix.a[0][0] = A, matrix.a[0][1] = B;
matrix.a[1][0] = 1, matrix.a[1][1] = 0;
Mat tmp = matrix.pow(n - 2);
long double x2 = 1.0 * (xn - tmp.a[0][1] * x1) / tmp.a[0][0];
cout << setprecision(15) << fixed << x1 << '\n'
<< x2 << '\n';
for (int i = 3; i < n; i++) {
long double ans = A * x1 + B * x2;
cout << ans << '\n';
x1 = x2, x2 = ans;
}
cout << xn << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
input:
1.0 1.0 10 1 10
output:
1.000000000000000 -0.323529411764706 0.676470588235294 0.352941176470588 1.029411764705882 1.382352941176471 2.411764705882353 3.794117647058824 6.205882352941176 10.000000000000000
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
1 1 2 1 100
output:
1 100
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 1 5 50 100
output:
50.000000000000000 0.000000000000000 50.000000000000000 50.000000000000000 100.000000000000000
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
0.25 0.25 10 1 1
output:
1.000000000000000 55.875536480686695 14.218884120171674 17.523605150214592 7.935622317596567 6.364806866952790 3.575107296137339 2.484978540772532 1.515021459227468 1.000000000000000
result:
ok 10 numbers
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 4008kb
input:
0.25 0.63 6 93 12
output:
93.000000000000000 -14.204807958665045 14.300970986041022 5.458409731539583 7.014040877380192 12.000000000000000
result:
wrong answer 3rd numbers differ - expected: '55.0387980', found: '14.3009710', error = '0.7401656'