QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178962 | #5377. $N$ 门问题 | Lynkcat# | 35 | 6ms | 4176kb | C++20 | 2.7kb | 2023-09-14 15:54:08 | 2024-07-04 01:59:43 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
// #define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 1000005
using namespace std;
ll x, y, d; int n;
void exgcd(ll &x, ll &y, ll a, ll b) {
if(!b) d = a, x = 1, y = 0;
else exgcd(y, x, b, a % b), y -= a / b * x;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll a, b, A, B;
map<vector<pa>,double>dp;
double dfs(vector<pa> g)
{
if (g.size()==2) return g.back().se;
if (dp.count(g)) return dp[g];
int len=g.size()-1;
double res=inf;
for (int i=0;i+1<g.size();i++)
if (g[i].se!=1)
{
int nw=g[i].fi;
vector<pa> nxt;
for (int j=0;j+1<g.size();j++)
{
if (j!=i)
nxt.push_back(mp(nw/(g.size()-2)+g[j].fi,g[j].se));
}
nxt.push_back(g.back());
sort(nxt.begin(),nxt.end());
int tot=0;
double sm=0;
for (int k=0;k<nxt.size();k++)
{
if (nxt[k].fi==nxt.back().fi) tot++;
}
sm+=dfs(nxt);
if (tot!=1)
{
swap(nxt.back(),nxt[nxt.size()-2]);
sm+=dfs(nxt)*(tot-1);
}
sm/=tot;
res=min(res,sm);
}
return dp[g]=res;
}
void merge()
{
exgcd(x, y, a, A);
ll c = B - b;
if(c % d)
{
cout<<"error"<<endl;
exit(0);
}
x = x * c / d % (A / d);
if(x < 0) x += A / d;
ll mod = lcm(a, A);
b = (a * x + b) % mod; if(b < 0) b += mod;
a = mod;
}
void BellaKira()
{
int t;
cin>>t;
for(int i = 1 ; i <= t ; ++ i)
{
long long _A, _B;
cin>>_B>>_A;
A = _A, B = _B;
if(i > 1) merge();
else a = A, b = B;
}
int n=b%a;
if (n<2)
{
cout<<"error\n";
return;
}
if (n>10)
{
cout<<0.000000<<'\n';
return;
}
// cout<<"!"<<n<<endl;
int x=1;
for (int i=1;i<=n;i++) x=x*i;
vector<pa> g;
for (int i=1;i<n;i++)
g.push_back(mp(x,0));
g.push_back(mp(x,1));
double ans=dfs(g);
swap(g.back(),g[g.size()-2]);
ans+=(n-1)*dfs(g);
cout<<fixed<<setprecision(6)<<ans/n<<endl;
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3752kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 3500kb
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: 3840kb
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: 3760kb
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: 3848kb
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: 3848kb
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: 0ms
memory: 4048kb
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: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 1000000007 1000000008 2 4
output:
error
result:
ok single line: 'error'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 0 1001 0 241221531 0 2
output:
error
result:
ok single line: 'error'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
3 6 1001 6 241221531 0 2
output:
0.416667
result:
ok single line: '0.416667'
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #15:
score: 10
Accepted
time: 0ms
memory: 3564kb
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 #16:
score: 0
Accepted
time: 0ms
memory: 4044kb
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 #17:
score: 0
Accepted
time: 0ms
memory: 3812kb
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 #18:
score: 0
Accepted
time: 0ms
memory: 3944kb
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 #19:
score: 0
Accepted
time: 0ms
memory: 3812kb
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 #20:
score: 0
Accepted
time: 0ms
memory: 4036kb
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 #21:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
10 7 16 7 8 3 4 0 1 7 32 7 256 7 64 1 2 7 512 7 128
output:
0.342857
result:
ok single line: '0.342857'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
10 8 16 8 64 8 32 0 1 0 8 0 2 8 128 0 4 8 256 8 512
output:
0.291667
result:
ok single line: '0.291667'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
10 1 2 113 128 0 8 1 16 49 64 17 32 241 256 1 4 241 512 0 1
output:
error
result:
ok single line: 'error'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
10 5 8 237 512 1 2 13 32 12 16 0 1 109 128 1 4 45 64 237 256
output:
error
result:
ok single line: 'error'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10 11 16 43 64 235 512 11 32 3 4 0 1 235 256 0 2 107 128 3 8
output:
error
result:
ok single line: 'error'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
10 9 32 1 2 41 64 233 512 233 256 1 4 0 1 9 16 1 8 115 128
output:
error
result:
ok single line: 'error'
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 10
Accepted
time: 0ms
memory: 3652kb
input:
8 1 5 1 15 1 2 1 30 1 3 0 1 1 6 1 10
output:
error
result:
ok single line: 'error'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
8 2 30 2 15 0 1 2 6 2 5 2 3 2 10 0 2
output:
0.500000
result:
ok single line: '0.500000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8 0 1 0 3 0 15 0 2 0 30 0 6 0 5 0 10
output:
error
result:
ok single line: 'error'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
8 1 2 5 30 0 1 0 5 2 3 5 6 5 15 5 10
output:
0.466667
result:
ok single line: '0.466667'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
8 3 5 0 3 3 15 3 10 0 1 1 2 3 30 3 6
output:
0.666667
result:
ok single line: '0.666667'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
6 0 3 3 4 1 2 3 6 0 1 3 12
output:
0.666667
result:
ok single line: '0.666667'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
6 0 1 2 6 0 4 2 3 0 2 8 12
output:
0.291667
result:
ok single line: '0.291667'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
6 0 1 1 2 2 3 1 4 5 6 5 12
output:
0.466667
result:
ok single line: '0.466667'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
6 3 12 1 2 0 3 0 1 3 4 3 6
output:
0.666667
result:
ok single line: '0.666667'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 5 6
output:
0.466667
result:
ok single line: '0.466667'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
1 6 7
output:
0.416667
result:
ok single line: '0.416667'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 7 8
output:
0.342857
result:
ok single line: '0.342857'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
4 0 2 0 4 2 3 3 5
output:
0.291667
result:
ok single line: '0.291667'
Test #40:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
4 0 3 0 9 1 2 4 5
output:
0.253968
result:
ok single line: '0.253968'
Test #41:
score: 0
Accepted
time: 2ms
memory: 4176kb
input:
3 0 2 0 5 1 3
output:
0.225000
result:
ok single line: '0.225000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
6 0 1 0 2 0 6 0 12 0 4 0 3
output:
error
result:
ok single line: 'error'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
6 837250 1574381 22682 54289 20 29 81 233 6139 6757 0 1
output:
error
result:
ok single line: 'error'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
6 12521 54289 1478324 1574381 20 29 171 233 0 1 5298 6757
output:
error
result:
ok single line: 'error'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 9430402 12649337 193 233 12831718919798818 37281334283719577 358403095623 686719856393 31260796633308 160005726539569 0 1 38405 54289 1780337582 2947295521
output:
error
result:
ok single line: 'error'
Test #46:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
8 0 2 6 30 0 1 1 5 0 3 0 6 6 15 6 10
output:
0.416667
result:
ok single line: '0.416667'
Subtask #5:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #47:
score: 5
Accepted
time: 0ms
memory: 3504kb
input:
27216 1100249873 1253754216 25197605440 29192187024 1744207706249 2277822821274 12223300097 26875346784 147492353 275539264 320696949581 377638144884 419900489 699380136 453032 1231659 266587329 890393504 7730812097 11914078176 524332817 661404744 2287601 8261694 1156980833 14524544034 967031297 145...
output:
error
result:
ok single line: 'error'
Test #48:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
27216 1887302 8343192 98702 115368 3405075396542 142252321079232 3015286 10958948 59487416 481578669 1045054 3865664 72754046 23575685952 370699174 794635556 163774430 446662944 10742784326 36887818968 2588314 130307788 1814817881150 2290728087648 59263478 81513432 105993323864 106600637682 27086905...
output:
error
result:
ok single line: 'error'
Test #49:
score: 0
Accepted
time: 4ms
memory: 3616kb
input:
50000 13191867 17093160 20006787 28265160 531754947 696215520 49540995 227505696 1073316627 1706292720 58569507 194230400 51790622607 214521407100 141120675 500919552 1207143507 1366149400 1382307 4379200 850756707 11479406400 453052323 1743565824 850756707 2203118400 231422833827 322489324080 15091...
output:
error
result:
ok single line: 'error'
Test #50:
score: 0
Accepted
time: 5ms
memory: 3564kb
input:
50000 9122968989 10897286400 1244648539 11099963875 1895367069 2400239520 35685693 52442208 3724120989 59434502400 6070719789 13899085200 8432349 39225120 131925789 306153000 101446557 226417152 2483743030749 3009900358080 13965142941 24139551744 30294839709 75157175808 317618589 535307520 39789 188...
output:
error
result:
ok single line: 'error'
Test #51:
score: -5
Wrong Answer
time: 6ms
memory: 3972kb
input:
50000 194 83566560 194 11970504 194 3351600 194 56073378816 194 157815216 194 2336202000 194 17749670400 194 2299884678 194 2366622720 194 4135131000 194 26409240 194 13248000 194 83847224260800 194 325909584 194 6051302400 194 1944746496 194 146024424000 194 1574773200 194 2472371200 194 2351661312...
output:
0
result:
wrong answer 1st lines differ - expected: '0.000000', found: '0'
Subtask #6:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 0ms
memory: 4036kb
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:
0
result:
wrong answer 1st lines differ - expected: '0.000000', found: '0'
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%