QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#437978#8785. Fake Coin and Lying Scalesucup-team1198WA 3872ms4212kbC++201.6kb2024-06-09 21:14:492024-06-09 21:14:49

Judging History

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

  • [2024-06-09 21:14:49]
  • 评测
  • 测评结果:WA
  • 用时:3872ms
  • 内存:4212kb
  • [2024-06-09 21:14:49]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#pragma GCC optimize("fast-math")

using namespace std;


using ld = double;

const ld PI = atan2l(0, -1);

ld fact(int x) {
    if (x == 0) return 0;
    return log(2 * PI * x) / 2 + x * log(x) - x;
}

ld C(int n, int k) {
    return fact(n) - fact(k) - fact(n - k);
}

ld add(ld p, ld q) {
    if (p > q) swap(p, q);
    return q + log(1 + exp(p - q));
}

const int D = 1000;

ld get_start(int n, int k) {
    int len = (n + D - 1) / D;
    ld cur = 0;
    for (int i = 0; i <= k; i += len) {
        int L = i, R = min(k + 1, i + len);

        double C1 = 1.0002;
        int P = (C1*L + R) / (1 + C1);
        // int P = (1.0001*L + R) / 2.0001;

        ld res = C(n, P) - (P - L) * log(2);
        // cerr << res << ' ' << C(n, L) << '\n';
        if (R - L < 60) {
            res += L * log(2) + log((1ll << (R - L)) - 1);
        } else {
            res += R * log(2);
        }
        cur = add(cur, res);
    }
    return n * log(3) - cur;
}

void solve() {
    int n, k;
    cin >> n >> k;
    k = min(k, n);
    ld ans = log(3ll * k + 1);
    cerr << "p : " << ans << '\n';
    ans += get_start(n, k);
    cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cout << fixed << setprecision(20);

  int tst;
  cin >> tst;
  while (tst--) {
    solve();
  }


  return 0;
}

详细

Test #1:

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

input:

2
100 0
100 1

output:

109.16808168625102837268
105.85895694123772159401

result:

ok q=0 (2 test cases)

Test #2:

score: 0
Accepted
time: 35ms
memory: 4100kb

input:

10000
32 6
45 98
67 57
35 70
29 3
22 81
59 12
48 16
63 69
99 36
60 36
32 47
73 91
81 30
7 7
71 57
38 60
35 19
92 40
3 17
21 71
54 62
95 67
60 50
10 20
19 80
64 73
10 21
70 97
84 3
26 22
38 47
37 38
31 91
11 37
73 17
75 98
8 74
73 60
87 10
94 48
35 73
18 14
88 25
61 54
39 59
100 90
70 98
73 21
92 11
...

output:

20.09444326417136750251
4.90586136619895452071
5.14319466133247615858
4.65456831821048222508
23.79448628853394964722
4.18990134020424509487
32.22847109632190409911
16.81541044029399856186
5.24224099071624127788
25.76859798203559392960
6.46762734691642116047
4.56494130693933897192
5.38951916577060696...

result:

ok q=0 (10000 test cases)

Test #3:

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

input:

1
10000 0

output:

10985.42973950053783482872

result:

ok q=0 (1 test case)

Test #4:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

1
10000 10

output:

10905.62258178719093848485

result:

ok q=0 (1 test case)

Test #5:

score: 0
Accepted
time: 1ms
memory: 4148kb

input:

1
10000 100

output:

10365.71643379963279585354

result:

ok q=0 (1 test case)

Test #6:

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

input:

1
100000 0

output:

109860.53571963042486459017

result:

ok q=0 (1 test case)

Test #7:

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

input:

1000
867 38
906 28
876 34
182 38
692 59
986 55
675 20
699 12
741 82
154 11
264 6
682 4
176 19
728 69
37 95
501 56
998 96
495 52
359 86
750 19
726 39
794 6
268 16
609 70
414 45
182 19
123 68
909 56
880 71
419 8
679 14
363 16
751 35
299 73
852 35
901 36
903 63
425 85
416 33
80 89
863 91
491 32
603 84
...

output:

777.59636158647606407612
858.01638484537534168339
802.29638886592954349908
87.58586265253866542935
525.72035376248857119208
840.90012916297564515844
644.11729715042497446120
704.69378670289586352737
507.95193376245225636012
127.50297460108043878790
261.97443022107961496658
726.10892995713663822244
1...

result:

ok q=0 (1000 test cases)

Test #8:

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

input:

1000
71 766
31 464
8 194
12 296
69 506
55 518
31 237
73 576
50 685
1 137
29 661
58 508
46 870
33 172
66 94
41 634
38 725
94 163
94 45
34 685
71 486
95 511
37 108
54 643
64 94
1 624
48 283
1 64
23 122
3 866
52 798
68 669
43 460
68 187
50 403
31 877
100 191
44 512
33 50
91 732
37 584
22 501
46 93
81 7...

output:

5.36174838650823293307
4.53318308195820751649
3.17555624210413744990
3.58151820232653017584
5.33318406314127457790
5.10648079326694670499
4.53318308195820751649
5.38951916577060696767
5.01119709345944652767
1.09861228866810978211
4.46646278855775591410
5.15957480286337499820
4.92783561017860627373
4...

result:

ok q=0 (1000 test cases)

Test #9:

score: -100
Wrong Answer
time: 3872ms
memory: 4212kb

input:

100000
448906 73251
858780 829062
380117 529011
219451 974416
390411 446812
457769 678634
440286 29979
663948 267273
623318 824172
557346 329036
2366 757990
279231 95725
394222 75586
671713 417299
997686 156089
462641 704003
267172 15563
115033 76151
271539 36507
909436 341831
97232 987703
780566 75...

output:

242774.08081042283447459340
20.77722903579823210407
19.19651337585594319535
17.40482992022075947602
19.24911446473441145599
18.87323636706656060369
354170.42382832575822249055
96846.80854288223781622946
19.49294432783705488532
7147.34738846599429962225
9.40658233393251919097
61084.437951136525953188...

result:

wrong answer WA (test case 1)