QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630305#9307. Clock MasterSatonAC ✓109ms6860kbC++201.3kb2024-10-11 17:45:192024-10-11 17:45:20

Judging History

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

  • [2024-10-11 17:45:20]
  • 评测
  • 测评结果:AC
  • 用时:109ms
  • 内存:6860kb
  • [2024-10-11 17:45:19]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 3e4;
double f[N + 5];
int cnt[N + 5], vis[N + 5], num = 0;
int prime[N + 5], val[N + 5][20];
int T, b;

void init()
{
    vis[0] = vis[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        if(!vis[i]) prime[++num] = i;
        for(int j = 1; j <= num && i * prime[j] <= N; j++)
        {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    for(int i = 1; i <= num; i++)
    {
        int len = 1;
        int tempV = pow(prime[i], len);
        while(tempV <= N)
        {
            val[i][len++] = tempV;
            tempV = pow(prime[i], len);
        }
        cnt[i] = len - 1;
    }
}

void solve()
{
    fill(f, f + N + 1, 1);
    for(int i = 1; i <= num; i++)
    {
        for(int j = N; j >= 1; j--)
        {
            for(int k = 1; k <= cnt[i]; k++)
            {
                if(j >= val[i][k])
                    f[j] = max(f[j], f[j - val[i][k]] * (double)val[i][k]);
            }
        }
    }
}


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

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

详细

Test #1:

score: 100
Accepted
time: 95ms
memory: 4836kb

input:

3
2
7
10

output:

0.693147181
2.484906650
3.401197382

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 102ms
memory: 4816kb

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.808521922
202.440525766
204.287598873
102.514787847
12.794858811
87.112177748
94.289632957
150.939424198
135.931424623
44.138273262
130.234331136
135.990701233
171.942516156
192.935006493
67.651984758
40.424701195
116.701483269
90.461792291
159.834265843
131.024777228
164.225018264
108.283079637
...

result:

ok 5000 numbers

Test #3:

score: 0
Accepted
time: 107ms
memory: 4768kb

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.313752946
546.925107896
248.614170742
426.701267322
183.873101749
407.626707665
377.464053061
293.706970483
333.305259996
225.341292315
514.109432127
522.821621178
401.575708655
472.177929531
288.029469559
19.916245881
510.958835143
332.072045342
524.440037554
460.581062814
526.242826547
126.097...

result:

ok 30000 numbers

Test #4:

score: 0
Accepted
time: 109ms
memory: 6860kb

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.707192409
303.923955039
578.331860711
381.789397772
538.165663885
56.296976483
523.940241454
369.898785751
173.358138133
150.444289904
363.898210646
515.495726488
347.843999324
468.086298285
157.818963701
294.368063637
153.394117069
246.303111968
561.491048417
334.973557130
467.401753308
303.475...

result:

ok 30000 numbers

Test #5:

score: 0
Accepted
time: 109ms
memory: 4788kb

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.060926945
533.040579837
530.396179663
471.319758385
564.289074993
496.066657632
520.011206854
492.144778783
551.806012288
574.273384135
580.593077503
548.063580534
518.600782144
573.531801950
497.739232881
517.510629509
475.011142875
566.438033684
561.435624871
540.972582989
524.497195968
521.78...

result:

ok 30000 numbers

Test #6:

score: 0
Accepted
time: 107ms
memory: 4848kb

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.606810193
580.657616209
580.604222745
579.938304590
580.600307385
580.563470077
580.639499772
580.606810193
579.975498552
580.566803414
580.639499772
580.624609659
580.624609659
580.620210729
580.649433628
579.956286448
580.587040192
579.941298623
580.642052577
579.931462478
579.948905396
580.60...

result:

ok 30000 numbers

Extra Test:

score: 0
Extra Test Passed