QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#437978 | #8785. Fake Coin and Lying Scales | ucup-team1198 | WA | 3872ms | 4212kb | C++20 | 1.6kb | 2024-06-09 21:14:49 | 2024-06-09 21:14:49 |
Judging History
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)