QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178078 | #5377. $N$ 门问题 | zhoukangyang# | 5 | 1ms | 8132kb | C++11 | 1.7kb | 2023-09-13 17:50:17 | 2024-07-04 01:56:23 |
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 21, L = 5e5, mod = 998244353;
double f[N];
ll n;
int k;
ll a[N], b[N];
ll rd() {
cin >> k;
L(i, 1, k) {
cin >> a[i] >> b[i];
}
n = 0;
while(true) {
int win = 1;
L(i, 1, k) {
if(n % b[i] != a[i]) {
win = 0;
break;
}
}
if(win) break;
++n;
if(n > 200) {
break;
}
}
return n;
}
double slv(vector < double > a, int cur) {
if(sz(a) == 2) {
return cur == 0;
}
double win = 1;
L(p, 1, sz(a) - 1) if(p != cur) {
double sum1 = 0, sum2 = 0;
L(i, 0, sz(a) - 1) if(i != cur) {
sum1 += a[i];
if(i != p) sum2 += a[i];
}
sum1 /= sum2;
vector < double > b;
L(i, 0, sz(a) - 1) {
if(i == cur) b.emplace_back(a[i]);
else if(i != p) b.emplace_back(a[i] * sum1);
}
double mx = 0;
L(i, 0, sz(b) - 1) {
mx = max(mx, b[i]);
}
int total = 0;
double sum = 0;
L(i, 0, sz(b) - 1) {
if(fabs(b[i] - mx) <= 1e-9) {
total += 1;
sum += slv(b, i);
}
}
sum /= total;
win = min(win, sum);
}
return win;
}
int main () {
ios :: sync_with_stdio(false);
cin.tie (0); cout.tie (0);
n = rd();
if(n < 2) {
cout << "error\n";
return 0;
}
vector < double > f(n);
L(i, 0, n - 1) {
f[i] = 1;
}
double ans = (slv(f, 0) + slv(f, 1) * (n - 1)) / n;
cout.precision(6); cout << fixed;
cout << ans << '\n';
return 0;
}
/*
(n-1)/(n-2) 1 [(n-1)/(n-2)] (n-1)/(n-2) (n-1)/(n-2) x
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 8128kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7912kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7936kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7884kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7644kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 10
Accepted
time: 0ms
memory: 7588kb
input:
8 1 160005726539569 1 233 0 1 1 2947295521 1 686719856393 1 54289 1 12649337 1 37281334283719577
output:
error
result:
ok single line: 'error'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7848kb
input:
10 2 64 0 2 2 512 2 4 2 32 2 16 2 256 0 1 2 8 2 128
output:
0.500000
result:
ok single line: '0.500000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7996kb
input:
10 3 256 3 16 0 1 3 8 3 512 3 32 3 4 3 128 3 64 1 2
output:
0.666667
result:
ok single line: '0.666667'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8132kb
input:
10 0 2 4 8 0 4 4 256 0 1 4 512 4 32 4 128 4 64 4 16
output:
0.625000
result:
ok single line: '0.625000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7916kb
input:
10 5 128 5 32 5 16 1 4 0 1 5 64 5 256 5 512 1 2 5 8
output:
0.466667
result:
ok single line: '0.466667'
Test #11:
score: 0
Accepted
time: 1ms
memory: 8064kb
input:
10 6 32 6 16 6 256 6 64 0 1 6 128 0 2 6 512 6 8 2 4
output:
0.416667
result:
ok single line: '0.416667'
Test #12:
score: -10
Time Limit Exceeded
input:
2 1000000007 1000000008 2 4
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #57:
score: 0
Time Limit Exceeded
input:
15 15 17 2 3 5 31 4 5 12 29 38 41 3 11 44 47 16 23 11 19 6 13 3 37 1 2 21 43 5 7
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%