QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790603#9307. Clock MasterIllusionaryDominance#AC ✓58ms4636kbC++20926b2024-11-28 13:55:302024-11-28 13:55:31

Judging History

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

  • [2024-11-28 13:55:31]
  • 评测
  • 测评结果:AC
  • 用时:58ms
  • 内存:4636kb
  • [2024-11-28 13:55:30]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 30000 + 5;

int pri[MAX_N], pcnt;
char np[MAX_N];
double f[MAX_N];

void init() {
    for (int i = 2; i < MAX_N; i ++) {
        if (!np[i]) {
            pri[++ pcnt] = i;
            static double g[MAX_N];
            for (int j = i; j < MAX_N; j *= i) {
                const double w = log((double)j);
                for (int k = MAX_N - 1; k >= j; k --) {
                    g[k] = max(g[k], f[k - j] + w);
                }
            }
            memcpy(f, g, sizeof f);
        }
        for (int j = 1; j <= pcnt && i * pri[j] < MAX_N; j ++) {
            np[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T --) {
        int x;
        scanf("%d", &x);
        printf("%.10lf\n", f[x]);
    }
    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 44ms
memory: 4592kb

input:

3
2
7
10

output:

0.6931471806
2.4849066498
3.4011973817

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 46ms
memory: 4620kb

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:

59.8085219222
202.4405257660
204.2875988733
102.5147878468
12.7948588108
87.1121777482
94.2896329571
150.9394241979
135.9314246226
44.1382732617
130.2343311361
135.9907012325
171.9425161563
192.9350064932
67.6519847578
40.4247011950
116.7014832688
90.4617922909
159.8342658434
131.0247772276
164.2250...

result:

ok 5000 numbers

Test #3:

score: 0
Accepted
time: 58ms
memory: 4592kb

input:

30000
14727
26896
6571
17234
3891
15888
13803
8818
11068
5541
24029
24764
15463
20613
8526
102
23759
10980
24923
19706
25043
2014
15199
19085
5761
24243
2075
16490
695
29219
2397
17193
25700
12082
13253
4167
5329
23855
6274
13900
26056
2910
28712
13016
9531
3368
17801
24668
23566
28589
1630
29223
24...

output:

391.3137529464
546.9251078965
248.6141707416
426.7012673221
183.8731017495
407.6267076649
377.4640530615
293.7069704831
333.3052599961
225.3412923152
514.1094321272
522.8216211783
401.5757086549
472.1779295309
288.0294695591
19.9162458807
510.9588351430
332.0720453422
524.4400375544
460.5810628136
5...

result:

ok 30000 numbers

Test #4:

score: 0
Accepted
time: 57ms
memory: 4596kb

input:

30000
7303
9397
29807
14117
26079
521
24880
13348
3507
2730
12948
24124
11931
20353
2972
8842
2822
6482
28198
11160
20228
9360
22739
10345
6523
10943
1290
7656
25686
25672
5920
8709
21244
28654
14891
6931
13149
6285
25615
5220
26475
3569
4878
19879
17324
26596
20869
29746
22377
27326
10043
3099
1425...

output:

263.7071924088
303.9239550386
578.3318607106
381.7893977717
538.1656638854
56.2969764833
523.9402414542
369.8987857509
173.3581381325
150.4442899039
363.8982106459
515.4957264883
347.8439993240
468.0862982845
157.8189637009
294.3680636373
153.3941170691
246.3031119677
561.4910484169
334.9735571304
4...

result:

ok 30000 numbers

Test #5:

score: 0
Accepted
time: 52ms
memory: 4596kb

input:

30000
20346
25684
25448
20568
28450
22513
24535
22174
27365
29390
29947
26968
24429
29299
22646
24327
20884
28665
28165
26338
24932
24668
26276
26758
20761
20643
22023
21015
25086
24814
29117
20105
23995
25805
24808
26211
23715
20272
24108
21876
25946
20128
26304
27341
21729
28712
28003
29471
24643
...

output:

468.0609269448
533.0405798366
530.3961796625
471.3197583846
564.2890749929
496.0666576318
520.0112068535
492.1447787826
551.8060122882
574.2733841349
580.5930775031
548.0635805344
518.6007821443
573.5318019502
497.7392328805
517.5106295088
475.0111428749
566.4380336839
561.4356248705
540.9725829889
...

result:

ok 30000 numbers

Test #6:

score: 0
Accepted
time: 52ms
memory: 4636kb

input:

30000
29955
29983
29952
29905
29951
29929
29972
29954
29925
29932
29973
29965
29965
29963
29978
29914
29942
29906
29975
29901
29911
29952
29957
29903
29982
29982
29960
29917
29937
29915
29936
29976
29989
29900
29926
29923
29922
29976
29905
29995
29901
29952
29968
29954
29932
29971
29975
29936
29906
...

output:

580.6068101934
580.6576162094
580.6042227453
579.9383045901
580.6003073849
580.5634700773
580.6394997719
580.6068101934
579.9754985524
580.5668034137
580.6394997719
580.6246096587
580.6246096587
580.6202107289
580.6494336284
579.9562864478
580.5870401920
579.9412986230
580.6420525766
579.9314624781
...

result:

ok 30000 numbers

Extra Test:

score: 0
Extra Test Passed