QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #858550 | #4754. Balls | jianhe | AC ✓ | 230ms | 4608kb | C++14 | 606b | 2025-01-16 18:57:37 | 2025-01-16 18:57:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define db double
const ll N=2e5+10,M=sqrt(N)+10;
ll T,n,ans[N];
db dp[3][M];
void init(){
for(ll i=0;i<N-9;i++){
db ct=1;ll now=i%3,lst=(i+1)%3;
dp[now][0]=1;
for(ll j=1;j<=min(i-1,M-10);j++){
dp[now][j]=(db)(i-j)/i*dp[lst][j]+(db)j/i*dp[lst][j-1];
if(abs(ct)>abs(dp[now][j]-0.5)) ct=dp[now][j]-0.5,ans[i]=j;
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>T;init();
while(T--) cin>>n,cout<<ans[n]<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 222ms
memory: 4352kb
input:
5 2 3 6 7 8
output:
1 1 2 1 2
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 230ms
memory: 4480kb
input:
100000 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
1 1 1 1 2 1 2 1 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 4 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3 5 3 5 3 5 3 5 3 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 5 6 5 6 5 6 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 8 5 8 5 8 5 8 6 8 6 8 6 8 6 8 6 8 6 8 6 8 6 ...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 230ms
memory: 4608kb
input:
100000 100001 100002 100003 100004 100005 100006 100007 100008 100009 100010 100011 100012 100013 100014 100015 100016 100017 100018 100019 100020 100021 100022 100023 100024 100025 100026 100027 100028 100029 100030 100031 100032 100033 100034 100035 100036 100037 100038 100039 100040 100041 100042...
output:
156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 213 156 ...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed