QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622959 | #8795. Mysterious Sequence | rns_rds# | WA | 1ms | 3988kb | C++23 | 3.1kb | 2024-10-09 08:55:43 | 2024-10-09 08:55:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
using Z = 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++)
res.a[i][j] = a[i][j] + x.a[i][j];
return res;
}
Mat operator-(const Mat &x) {
Mat res;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
res.a[i][j] = a[i][j] - x.a[i][j];
return res;
}
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), b = *this;
for (; k; k >>= 1) {
if (k & 1) res = res * b;
b = b * b;
}
return res;
}
friend istream &operator>>(istream &stream, Mat &M) {
for (int i = 0; i < D; i++) {
for (int j = 0; j < D; j++) {
stream >> M.a[i][j];
}
}
return stream;
}
friend ostream &operator<<(ostream &stream, const Mat &M) {
for (int i = 0; i < D; i++) {
for (int j = 0; j < D; j++) {
if (j) stream << ' ';
stream << M.a[i][j];
}
stream << '\n';
}
return stream;
}
Z det() {
vector<vector<Z>> work(D, vector<Z>(D, 0));
Z rlt = 1;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
work[i][j] = a[i][j];
for (int i = 0; i < D; i++) {
for (int ii = i + 1; ii < D; ii++) {
if (work[ii][i] != 0) {
Z tmp = work[i][i] / work[ii][i];
for (int j = i; j < D; j++)
work[i][j] -= work[ii][j] * tmp;
for (int j = i; j < D; j++)
swap(work[i][j], work[ii][j]);
rlt *= -1;
}
}
if (work[i][i] == 0) return 0;
rlt *= work[i][i];
}
return rlt;
}
};
int Mat::D = 2;
// See RNS_CONTEST_2023::D
int main() {
double A, B;
int n;
double x1, xn;
cin >> A >> B >> n >> x1 >> xn;
Mat matrix;
matrix.a[0][0] = A, matrix.a[0][1] = B;
matrix.a[1][0] = 1, matrix.a[1][1] = 0;
matrix = matrix.pow(n - 2);
double x2 = (xn - matrix.a[0][1] * x1) / matrix.a[0][0];
cout << setprecision(7) << fixed << x1 << '\n'
<< x2 << '\n';
for (int i = 3; i <= n; i++) {
double ans = x1 + x2;
cout << ans << '\n';
x1 = x2, x2 = ans;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3768kb
input:
1.0 1.0 10 1 10
output:
1.0000000 -0.3235294 0.6764706 0.3529412 1.0294118 1.3823529 2.4117647 3.7941176 6.2058824 10.0000000
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
1 1 2 1 100
output:
1.0000000 100.0000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
1 1 5 50 100
output:
50.0000000 0.0000000 50.0000000 50.0000000 100.0000000
result:
ok 5 numbers
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3820kb
input:
0.25 0.25 10 1 1
output:
1.0000000 55.8755365 56.8755365 112.7510730 169.6266094 282.3776824 452.0042918 734.3819742 1186.3862661 1920.7682403
result:
wrong answer 3rd numbers differ - expected: '14.2188841', found: '56.8755365', error = '3.0000000'