QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74206 | #5444. Tavern Chess | zhangboju# | WA | 2ms | 3740kb | C++14 | 1.7kb | 2023-01-31 08:59:19 | 2023-01-31 08:59:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
const int N=15;
int n,m;
int ha[N],hb[N];
int aa[N],ab[N];
int cnta[N],cntb[N];
double ansa,ansb,ansp;
void dfsa(double p,int numa,int numb);
void dfsb(double p,int numa,int numb);
void dfsa(double p,int numa,int numb)
{
if(!numa||!numb)
{
if(!numa&&!numb) ansp+=p;
else if(!numa) ansb+=p;
else ansa+=p;
return;
}
int pos=0;
for(int i=1;i<=n;++i)
if(ha[i]>0&&(pos==0||cnta[i]<cnta[pos]))
pos=i;
if(!pos) return;
for(int i=1;i<=m;++i)
{
if(hb[i]<=0) continue;
ha[pos]-=ab[i];
hb[i]-=aa[pos];
++cnta[pos];
dfsb(p/numb,numa-(ha[pos]<=0),numb-(hb[i]<=0));
ha[pos]+=ab[i];
hb[i]+=aa[pos];
--cnta[pos];
}
}
void dfsb(double p,int numa,int numb)
{
if(!numa||!numb)
{
if(!numa&&!numb) ansp+=p;
else if(!numa) ansb+=p;
else ansa+=p;
return;
}
int pos=0;
for(int i=1;i<=m;++i)
if(hb[i]>0&&(pos==0||cntb[i]<cntb[pos]))
pos=i;
if(!pos) return;
for(int i=1;i<=m;++i)
{
if(ha[i]<=0) continue;
hb[pos]-=aa[i];
ha[i]-=ab[pos];
++cntb[pos];
dfsa(p/numa,numa-(ha[i]<=0),numb-(hb[pos]<=0));
hb[pos]+=aa[i];
ha[i]+=ab[pos];
--cntb[pos];
}
}
int main()
{
read(n),read(m);
for(int i=1;i<=n;++i) read(ha[i]),aa[i]=ha[i];
for(int i=1;i<=m;++i) read(hb[i]),ab[i]=hb[i];
if(n>m) dfsa(1,n,m);
else if(n<m) dfsb(1,n,m);
else dfsa(0.5,n,m),dfsb(0.5,n,m);
printf("%.10lf\n%.10lf\n%.10lf",ansa,ansb,ansp);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3740kb
input:
2 3 2 5 3 4 1
output:
0.1250000000 0.7500000000 0.1250000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
6 6 1 1 4 5 1 4 1 1 4 5 1 4
output:
0.2418672840 0.2418672840 0.5162654321
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0.0000000000 0.0000000000 1.0000000000
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
1 7 7 1 1 1 1 1 1 1
output:
0.0000000000 0.0000000000 1.0000000000
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
2 3 736618938 652769331 328875880 97571721 44608905
output:
1.0000000000 0.0000000000 0.0000000000
result:
ok 3 numbers
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3548kb
input:
5 4 53585130 731696211 668322278 611205195 158818781 569587984 776042583 745745433 330119007
output:
0.0243055556 0.0124421296 0.0743634259
result:
wrong answer 1st numbers differ - expected: '0.0668403', found: '0.0243056', error = '0.0425347'