QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#503851#8795. Mysterious SequencePlasmatic#AC ✓1ms4024kbC++142.8kb2024-08-04 02:11:272024-08-04 02:11:27

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 02:11:27]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4024kb
  • [2024-08-04 02:11:27]
  • 提交

answer

#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

// Defines
#define fs first
#define sn second
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
// Basic type definitions
#if __cplusplus == 201703L // CPP17 only things
template <typename T> using opt_ref = optional<reference_wrapper<T>>; // for some templates
#endif
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<long long, long long>;
#undef __GNUG__
#ifdef __GNUG__
// PBDS order statistic tree
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>;
// HashSet
#include <ext/pb_ds/assoc_container.hpp>
template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>;
template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash { ll operator()(ll x) const { return x ^ RANDOM; } };
#endif
// More utilities
int SZ(string &v) { return v.length(); }
template <typename C> int SZ(C &v) { return v.size(); }
template <typename C> void UNIQUE(vector<C> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); }
template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); }
template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); }
const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f;

ld A, B;
int n;

pair<ld, ld> scale(pair<ld, ld> p, ld alpha) {
    return {p.fs * alpha, p.sn * alpha};
}

pair<ld, ld> add(pair<ld, ld> a, pair<ld, ld> b) {
    return {a.fs + b.fs, a.sn + b.sn};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> A >> B >> n;
    vector<ld> X(n + 1);
    cin >> X[1] >> X[n];

    // derive X[1..n] in terms of X[1] and X[2]
    vector<pair<ld, ld>> coeffs(n + 1); // coeffs[i] = (a, b) where X[i] = a * X[1] + b * X[2]
    coeffs[1] = {1, 0};
    coeffs[2] = {0, 1};
    for (int i = 3; i <= n; i++) {
        coeffs[i] = add(scale(coeffs[i - 1], A), scale(coeffs[i - 2], B));
    }

    // use it to reconstruct X[2] from X[1] and X[n]
    auto [alpha, beta] = coeffs[n];
    X[2] = (X[n] - alpha * X[1]) / beta;

    // reconstruct X[3..n] from X[1] and X[2]
    for (int i = 3; i <= n; i++) {
        X[i] = A * X[i - 1] + B * X[i - 2];
    }

    // output
    cout << fixed << setprecision(10);
    for (int i = 1; i <= n; i++) {
        cout << X[i] << '\n';
    }

    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4012kb

input:

1.0 1.0 10 1 10

output:

1.0000000000
-0.3235294118
0.6764705882
0.3529411765
1.0294117647
1.3823529412
2.4117647059
3.7941176471
6.2058823529
10.0000000000

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

1 1 2 1 100

output:

1.0000000000
100.0000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

1 1 5 50 100

output:

50.0000000000
0.0000000000
50.0000000000
50.0000000000
100.0000000000

result:

ok 5 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

0.25 0.25 10 1 1

output:

1.0000000000
55.8755364807
14.2188841202
17.5236051502
7.9356223176
6.3648068670
3.5751072961
2.4849785408
1.5150214592
1.0000000000

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

0.25 0.63 6 93 12

output:

93.0000000000
-14.2048079587
55.0387980103
4.8106704886
35.8771103687
12.0000000000

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

0.25 0.80 10 5 63

output:

5.0000000000
78.7695361835
23.6923840459
68.9387249583
36.1885884763
64.1981270857
45.0004025525
62.6086023067
51.6524726186
63.0000000000

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

0.25 0.99 3 18 30

output:

18.0000000000
48.7200000000
30.0000000000

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

0.28 0.64 9 6 10

output:

6.0000000000
20.9504033485
9.7061129376
16.1259697656
10.7271838144
13.3242321180
10.5961826343
11.4944396931
10.0000000000

result:

ok 9 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

0.31 0.40 7 10 49

output:

10.0000000000
240.1150639987
78.4356698396
120.3610832497
68.6862037433
69.4371564603
49.0000000000

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

0.32 0.28 5 36 6

output:

36.0000000000
10.1213768116
13.3188405797
7.0960144928
6.0000000000

result:

ok 5 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

0.35 0.65 10 86 82

output:

86.0000000000
79.5339247862
83.7368736752
81.0049568974
82.7807028029
81.6264679643
82.3767206094
81.8890563901
82.2060381327
82.0000000000

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

0.36 0.68 8 72 59

output:

72.0000000000
38.2399186426
62.7263707113
48.5846381331
60.1444018116
54.6895385827
60.5864271217
59.0000000000

result:

ok 8 numbers

Test #13:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

0.43 0.61 2 93 84

output:

93.0000000000
84.0000000000

result:

ok 2 numbers

Test #14:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

0.46 0.96 6 65 35

output:

65.0000000000
-16.6174236628
54.7559851151
9.2350264366
56.8138578714
35.0000000000

result:

ok 6 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

0.50 0.90 4 19 1

output:

19.0000000000
-6.5652173913
13.8173913043
1.0000000000

result:

ok 4 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

0.54 0.35 3 16 22

output:

16.0000000000
30.3703703704
22.0000000000

result:

ok 3 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

0.55 0.89 10 74 13

output:

74.0000000000
-48.3219370766
39.2829346079
-21.4009099638
23.1913113209
-6.2915886413
17.1798933229
3.8494274368
17.4072901476
13.0000000000

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

0.56 0.36 3 31 88

output:

31.0000000000
137.2142857143
88.0000000000

result:

ok 3 numbers

Test #19:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

0.57 0.93 7 71 48

output:

71.0000000000
-34.0805653617
46.6040777438
-5.1306014724
40.4173494625
18.2664298243
48.0000000000

result:

ok 7 numbers

Test #20:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

0.58 0.41 8 30 69

output:

30.0000000000
89.4321216828
64.1706305760
73.8861356240
69.1639171981
70.4083875808
69.1940708481
69.0000000000

result:

ok 8 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

0.58 0.49 6 31 96

output:

31.0000000000
99.5576135384
72.9334158523
91.0846118281
88.5664486279
96.0000000000

result:

ok 6 numbers

Test #22:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

0.61 0.29 8 62 25

output:

62.0000000000
34.4076512571
38.9686672669
33.7491058973
31.8878681048
29.2388402541
27.0831743054
25.0000000000

result:

ok 8 numbers

Test #23:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

0.63 0.89 9 37 85

output:

37.0000000000
-5.8878533022
29.2206524196
13.1688215854
34.3027382523
33.3309763100
51.5279521198
62.1271787514
85.0000000000

result:

ok 9 numbers

Test #24:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

0.64 0.67 2 74 42

output:

74.0000000000
42.0000000000

result:

ok 2 numbers

Test #25:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

0.65 0.56 2 94 96

output:

94.0000000000
96.0000000000

result:

ok 2 numbers

Test #26:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

0.65 0.90 10 97 23

output:

97.0000000000
-61.7035762791
47.1926754186
-24.8579796291
26.3157211178
-5.2669629397
20.2606230952
8.4291383662
23.7135007237
23.0000000000

result:

ok 10 numbers

Test #27:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

0.67 0.88 4 70 42

output:

70.0000000000
0.5478215065
61.9670404094
42.0000000000

result:

ok 4 numbers

Test #28:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

0.69 0.39 10 2 27

output:

2.0000000000
22.3659076870
16.2124763040
19.9093126477
20.0602914855
21.6062330576
22.7318144891
24.1113828899
25.5022618448
27.0000000000

result:

ok 10 numbers

Test #29:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

0.69 0.57 4 88 47

output:

88.0000000000
11.8436095976
58.3320906223
47.0000000000

result:

ok 4 numbers

Test #30:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

0.71 0.89 8 4 41

output:

4.0000000000
6.8388903627
8.4156121575
12.0616970546
16.0536997290
22.1330371862
30.0022491610
41.0000000000

result:

ok 8 numbers

Test #31:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

0.72 0.49 8 21 48

output:

21.0000000000
19.9404423699
24.6471185064
27.5167420858
31.8891423699
36.4433861284
41.8649177737
48.0000000000

result:

ok 8 numbers

Test #32:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

0.74 0.58 3 57 29

output:

57.0000000000
-5.4864864865
29.0000000000

result:

ok 3 numbers

Test #33:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

0.76 0.70 2 91 18

output:

91.0000000000
18.0000000000

result:

ok 2 numbers

Test #34:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

0.77 0.36 10 31 25

output:

31.0000000000
5.2149720850
15.1755285055
13.5625468998
15.9063513748
17.1304074426
18.9167002257
20.7328058531
22.7742725882
25.0000000000

result:

ok 10 numbers

Test #35:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

0.77 0.96 8 78 68

output:

78.0000000000
-40.0975570076
44.0048811041
-4.6098962771
38.6950657266
25.3697001835
56.6819322388
68.0000000000

result:

ok 8 numbers

Test #36:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

0.78 0.52 7 73 77

output:

73.0000000000
8.7275475061
44.7674870547
39.4569646058
54.0555256610
62.6809316106
77.0000000000

result:

ok 7 numbers

Test #37:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

0.78 0.69 4 42 97

output:

42.0000000000
57.2979051140
73.6723659889
97.0000000000

result:

ok 4 numbers

Test #38:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

0.78 0.70 10 54 99

output:

54.0000000000
-13.0128863509
27.6499486463
12.4579394985
29.0721568612
31.3968400007
44.8400450034
56.9530231031
75.8113895228
99.0000000000

result:

ok 10 numbers

Test #39:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

0.78 0.76 10 97 83

output:

97.0000000000
-43.7347369590
39.6069051719
-2.3450140548
28.2721369680
20.2700561534
37.2974678953
44.4972676349
63.0539443557
83.0000000000

result:

ok 10 numbers

Test #40:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

0.78 0.95 10 100 32

output:

100.0000000000
-63.2695788174
45.6497285225
-24.4993116290
24.2577790257
-4.3532784075
19.6493329166
11.1908651879
27.3957411173
32.0000000000

result:

ok 10 numbers

Test #41:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

0.79 0.90 10 98 42

output:

98.0000000000
-58.2469146280
42.1849374438
-19.0961225846
22.8805068576
0.8890900914
21.2948373441
17.6231025841
33.0876046511
42.0000000000

result:

ok 10 numbers

Test #42:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

0.81 0.48 10 97 1

output:

97.0000000000
-38.2575016816
15.5714236379
-5.7507476605
2.8161777412
-0.4792549066
0.9635688414
0.5504484064
0.9083762530
1.0000000000

result:

ok 10 numbers

Test #43:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

0.81 0.86 10 20 100

output:

20.0000000000
-3.3328428697
14.5003972756
8.8790769253
19.6623939665
23.5625452687
35.9953204788
49.4199985189
70.9861744121
100.0000000000

result:

ok 10 numbers

Test #44:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

0.84 0.85 10 74 95

output:

74.0000000000
-36.2908048771
32.4157239032
-3.6179760668
24.5142654216
17.5167032974
35.5511563782
44.7521691604
67.8103050162
95.0000000000

result:

ok 10 numbers

Test #45:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

0.88 0.37 10 3 96

output:

3.0000000000
29.0218284904
26.6492090715
34.1893805244
39.9468622179
47.8033095458
56.8472514209
67.7128057824
80.6207521142
96.0000000000

result:

ok 10 numbers

Test #46:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

0.91 0.50 10 100 98

output:

100.0000000000
-22.5868578545
29.4459593524
15.5023940835
28.8301582922
33.9866410876
45.3429225358
58.2553800514
75.6838571146
98.0000000000

result:

ok 10 numbers

Test #47:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

0.94 0.48 10 44 97

output:

44.0000000000
-1.5827434387
19.6322211676
17.6945710470
26.0563629446
32.9863752705
43.5142469676
56.7368522794
74.2194796871
97.0000000000

result:

ok 10 numbers

Test #48:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

0.94 0.54 10 28 95

output:

28.0000000000
0.4525463071
15.5453935287
14.8570449229
22.3601347330
29.0413309074
39.3733238087
52.6932430702
70.7932433427
95.0000000000

result:

ok 10 numbers

Test #49:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

0.95 0.57 10 2 94

output:

2.0000000000
9.2272841742
9.9059199655
14.6701759465
19.5830415294
26.9658897424
36.7799289271
50.3114896339
68.7604746407
94.0000000000

result:

ok 10 numbers

Test #50:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

0.98 0.90 10 21 99

output:

21.0000000000
-8.2131934850
10.8510703847
3.2421748406
12.9432946900
15.6023861527
26.9393036507
40.4426651151
63.8791850984
99.0000000000

result:

ok 10 numbers

Extra Test:

score: 0
Extra Test Passed