QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#668150#9307. Clock Master4eyebird#WA 257ms4680kbC++171.2kb2024-10-23 11:57:092024-10-23 11:57:09

Judging History

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

  • [2024-10-23 11:57:09]
  • 评测
  • 测评结果:WA
  • 用时:257ms
  • 内存:4680kb
  • [2024-10-23 11:57:09]
  • 提交

answer

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

const int N = 30005;
#define Buff ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define int long long

int primes[N], cnt;
bool st[N];
double ans[N];
void pr()
{
    st[0] = st[1] = 1;
    for (int i = 2; i <= N - 2; i++)
    {
        if (!st[i])
        {
            primes[++cnt] = i;
            for (int j = 1; j <= cnt && i * primes[j] <= N - 2; j++)
            {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }
}

double ln[N];

void init()
{
    for (int i = 1; i < N; i++)
        ln[i] = log(i);
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = 30000; j >= primes[i]; j--)
        {
            for (int k = primes[i]; k <= j; k *= primes[i])
            {
                ans[j] = max(ans[j], ans[j - k] + ln[k]);
            }
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    cout << fixed << setprecision(10) << ans[n] << "\n";
}

signed main()
{
    Buff;
    int _T_ = 1;
    cin >> _T_;
    pr();
    init();
    while (_T_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 257ms
memory: 4680kb

input:

3
2
7
10

output:

0.6931471806
2.4849066498
3.4011973817

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 221ms
memory: 4564kb

input:

5000
580
4555
4654
1420
53
1076
1226
2733
2285
348
2104
2293
3447
4208
710
307
1763
1142
3027
2151
3182
1546
3398
867
2380
830
4211
3117
3058
2251
1890
3961
4003
3991
4167
4976
1765
3235
2644
4070
4644
3645
875
3005
4769
4934
3846
2941
255
946
4164
1372
1193
3056
4472
508
3949
2473
4490
88
4014
2953...

output:

72.8540240844
273.9182741492
277.9512887126
131.2816079570
13.1695522602
109.7511126632
118.8001409243
198.7514301942
177.7799446494
52.4547152679
168.7822247395
177.8787242950
229.3969776350
260.6311908377
83.5065664495
47.2662127674
150.5091145055
113.9407674052
211.5853485415
171.3599131227
218.6...

result:

wrong answer 1st numbers differ - expected: '59.8085219', found: '72.8540241', error = '0.2181211'