QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55166#1760. Jammed GymBeevo#AC ✓4ms4136kbC++231.5kb2022-10-12 16:08:302022-10-12 16:08:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 16:08:33]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:4136kb
  • [2022-10-12 16:08:30]
  • 提交

answer

#include <bits/stdc++.h>

#define el '\n'
#define ll long long
#define ld long double

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const ld pi = acos(-1);
const int N = 100 + 5, INF = 2e9;

int n, m;
ld d[N][N];
ld dp[N][N];
int a[N], s[N];
bool vis[N][N];

ld dist(int i, int j) {
    ld div = 360.0 / m;

    int diff = min(j - i, m - j + i);

    ld angle = div * diff;

    ld len = angle * pi / 180;

    return 2 * sin(len / 2);
}

ld solve(int idx, int st) {
    if (idx >= n)
        return 0;

    ld &ret = dp[idx][st];

    if (vis[idx][st])
        return ret;

    vis[idx][st] = 1;

    ret = INF;

    for (int i = 0; i < m; i++) {
        if (s[i] != a[idx])
            continue;

        ret = min(ret, d[st][i] + solve(idx + 1, i));
    }

    return ret;
}

void testCase() {
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    cin >> m;

    for (int i = 0; i < m; i++)
        cin >> s[i];

    s[m] = m;

    for (int i = 0; i < m; i++) {
        d[i][i] = 0;

        for (int j = i + 1; j < m; j++)
            d[i][j] = d[j][i] = dist(i, j);
    }

    for (int i = 0; i < m; i++)
        d[i][m] = d[m][i] = 1;

    memset(dp, -1, sizeof dp);

    cout << fixed << setprecision(6) << solve(0, m);
}

signed main() {
    Beevo

    int T = 1;
//    cin >> T;

    while (T--)
        testCase();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 4084kb

input:

10
1 3 2 2 3 1 3 3 3 3
10
1 2 3 1 1 2 1 2 2 2

output:

4.090170

result:

ok found '4.0901700', expected '4.0901699', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 4080kb

input:

20
3 2 3 4 4 4 1 4 2 4 3 2 3 2 3 3 4 1 4 4
10
4 1 2 3 4 1 1 3 2 4

output:

11.385583

result:

ok found '11.3855830', expected '11.3855829', error '0.0000000'

Test #3:

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

input:

30
5 4 2 2 3 2 2 4 3 5 2 1 2 1 2 3 5 1 4 4 1 1 2 4 5 3 1 4 2 3
10
4 5 3 3 2 3 2 1 5 1

output:

26.526668

result:

ok found '26.5266680', expected '26.5266684', error '0.0000000'

Test #4:

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

input:

100
4 5 8 5 10 1 9 3 3 3 1 2 4 7 9 9 4 5 7 7 1 6 8 2 1 4 5 9 5 8 8 2 5 3 8 10 8 6 4 9 8 9 1 4 1 5 2 6 10 6 6 3 4 3 4 5 10 6 10 4 1 3 10 4 7 1 8 1 5 10 7 9 8 9 2 7 8 10 5 10 5 1 9 3 2 3 4 1 5 6 4 9 1 7 10 9 3 8 10 10
50
9 8 7 1 7 7 9 4 8 10 4 3 3 10 4 3 1 3 9 2 7 5 6 8 7 2 3 1 8 9 4 5 9 7 4 2 7 1 4 9...

output:

43.842914

result:

ok found '43.8429140', expected '43.8429139', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

100
5 2 6 9 5 2 9 7 6 1 7 6 4 9 6 10 5 6 6 4 6 10 2 1 3 4 9 6 1 9 1 9 6 2 2 10 4 6 6 2 6 8 6 8 2 1 9 8 4 4 2 7 5 5 9 10 8 5 6 9 8 8 7 7 8 3 6 2 4 2 9 5 10 4 8 7 10 9 7 10 3 10 9 1 6 1 4 8 5 1 2 3 1 7 4 7 9 6 10 4
100
4 9 2 9 3 8 10 8 1 3 9 4 1 9 4 5 2 9 9 9 5 3 5 3 8 10 7 1 8 9 8 10 2 4 2 4 5 10 8 8...

output:

24.556588

result:

ok found '24.5565880', expected '24.5565882', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

100
3 19 13 12 13 1 12 10 3 10 17 6 18 8 7 20 12 14 4 2 9 10 13 5 3 12 17 17 13 5 13 2 15 10 18 19 17 6 16 4 4 12 6 3 7 7 8 16 16 14 4 2 12 1 14 8 20 5 3 7 5 5 19 14 7 11 17 4 2 6 13 16 5 17 2 19 7 15 19 6 13 19 8 11 1 5 2 19 8 11 11 20 8 2 10 15 13 11 20 6
100
2 9 8 15 18 7 11 14 19 10 14 20 3 10 1...

output:

47.902692

result:

ok found '47.9026920', expected '47.9026915', error '0.0000000'

Test #7:

score: 0
Accepted
time: 4ms
memory: 4136kb

input:

100
16 24 16 6 28 6 11 17 13 26 5 10 21 7 20 26 3 18 16 15 16 19 24 2 21 7 9 15 6 8 8 7 17 25 29 13 29 6 14 9 29 14 30 2 2 17 20 9 9 14 11 22 3 1 9 4 9 16 9 13 12 9 15 1 2 7 3 28 12 7 28 2 25 28 1 25 19 15 11 8 10 27 7 2 16 29 7 13 18 7 30 11 12 20 9 29 26 29 15 17
100
7 10 23 17 22 23 13 5 9 6 18 2...

output:

68.581986

result:

ok found '68.5819860', expected '68.5819859', error '0.0000000'

Test #8:

score: 0
Accepted
time: 4ms
memory: 4112kb

input:

100
18 7 17 6 31 2 26 8 1 21 40 37 23 22 26 13 28 17 19 28 15 10 1 22 8 34 31 16 4 16 25 36 9 25 31 17 22 38 33 13 40 37 15 32 4 22 15 2 5 16 7 28 13 8 20 10 1 17 21 18 18 34 19 12 11 24 28 14 5 9 35 25 4 9 38 21 7 8 39 12 12 29 6 16 40 22 38 28 9 29 17 13 28 27 19 40 1 9 20 9
100
27 7 30 18 14 39 3...

output:

73.819350

result:

ok found '73.8193500', expected '73.8193498', error '0.0000000'