Submission #7423020
Source Code Expand
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace::std; struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> #include <boost/numeric/interval.hpp> #include <boost/numeric/interval/io.hpp> // #include <boost/intrusive/rbtree.hpp> // #include <boost/geometry.hpp> // #include <boost/geometry/geometries/linestring.hpp> // #include <boost/geometry/geometries/polygon.hpp> // #include <boost/geometry/geometries/point_xy.hpp> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/tag_and_trait.hpp> using namespace __gnu_pbds; using namespace::std; namespace mp = boost::multiprecision; typedef mp::number<mp::cpp_dec_float<256,int64_t>> cdouble; typedef mp::cpp_int cint; typedef long long lint; typedef long long ll; typedef long double ldouble; typedef vector<lint> vec; typedef vector<vector<lint>> mat; typedef vector<vector<vector<lint>>> mat3; typedef vector<double> dvec; typedef vector<vector<double>> dmat; typedef vector<vector<vector<double>>> dmat3; typedef vector<string> svec; typedef vector<vector<string>> smat; typedef vector<vector<vector<string>>> smat3; typedef vector<pair<lint,lint>> pvec; typedef vector<vector<pair<lint,lint>>> pmat; typedef vector<vector<vector<pair<lint,lint>>>> pmat3; #define rep(i, n) for(lint i = 0; i < (lint)(n); i++) #define irep(i) for(lint i = 0;; i++) #define irep1(i) for(lint i = 1;; i++) #define irep2(i) for(lint i = 2;; i++) #define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--) #define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--) #define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++) #define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c) #define all(x) (x).begin(),(x).end() #define PI 3.141592653589793 #define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5)) #define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"");if(i>INF/2)cout<<"INF";else cout<<i;f=1;}cout<<"\n";}while(0) #define output2(v) for(auto j:v)output(j); #define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i]; #define SUM(v) accumulate(all(v),0LL) #define INF (1LL<<60) #define IINF (1<<30) #define EPS (1e-10) #define LINF 9223372036854775807 #define MOD 1000000007 #define endl "\n" struct any{ string s; any(string s):s(s){} operator lint()const{return stoll(s);} operator double()const{return stod(s);} operator string()const{return s;} }; any in(void){ return any(*istream_iterator<string>(cin)); } inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;} inline lint lcm(lint a,lint b){return a*b/gcd(a,b);} inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;} inline lint mex(vector<lint> s){ lint res=0; sort(all(s)); while(binary_search(all(s),res))res++; return res; } vector<lint> dx={-1,1,0,0,1,1,-1,-1}; vector<lint> dy={0,0,-1,1,1,-1,1,-1}; struct BIT{ private: vector<lint> bit,bit2; lint n; public: BIT(lint n):n(n){ bit.resize(n+1,0); bit2.resize(n+1,0); } //0-indexed [0,x)-sum lint sum(lint x){ lint res=0; for(lint i=x;i>0;i-=i&-i)res+=bit[i]; for(lint i=x;i>0;i-=i&-i)res+=x*bit2[i]; return res; } //0-indexed [x,y)-sum lint sum(lint x,lint y){ return sum(y)-sum(x); } //0-indexed [l,r)add void add(lint l,lint r,lint x){ l++;r++; if(0>r||l>n)return; for(lint i=l;i<=n;i+=i&-i)bit[i]+=-x*(l-1); for(lint i=r;i<=n;i+=i&-i)bit[i]+=x*r; for(lint i=l;i<=n;i+=i&-i)bit2[i]+=x; for(lint i=r;i<=n;i+=i&-i)bit2[i]+=-x; } }; // struct tree{ // private: // lint n; // vector<> // public: // tree(lint n):n(n){} // tree addEdge(lint from,lint to,lint cost=1){ // } // } lint comb(lint a,lint b){ cint ans=1; repi(i,a-b+1,a+1){ ans*=i; } repi(i,1,b+1){ ans/=i; } return (lint)ans; } int main(){ lint n; cin>>n; vector<cdouble> dp(n+1,0); repi(i,2,n+1){ //j:グー,k:チョキ,l:パー cdouble aiko=0; cdouble kitai=0; cdouble waight=1; rep(j,i+1){ waight=comb(i,j); rep(k,i-j+1){ if(k!=0){ waight*=i-j-k+1; waight/=k; } lint l=i-j-k; vec v={j,k,l}; set<lint> s{j,k,l}; s.erase(0); sort(all(v)); if((v[0]==0&&v[1]==0)||(v[0]==v[1]&&v[1]==v[2])){ aiko+=waight; }else{ kitai+=(dp[*min_element(all(s))]+1)*waight; } } } dp[i]=(aiko+kitai)/(pow(cdouble(3),cdouble(i))-aiko); } cout<<dp[n]; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | hotman78 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5162 Byte |
Status | WA |
Exec Time | 291 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
input-002.txt | AC | 2 ms | 256 KB |
input-003.txt | AC | 2 ms | 256 KB |
input-004.txt | AC | 2 ms | 256 KB |
input-005.txt | AC | 2 ms | 256 KB |
input-006.txt | AC | 2 ms | 256 KB |
input-007.txt | AC | 2 ms | 256 KB |
input-008.txt | AC | 2 ms | 256 KB |
input-009.txt | AC | 2 ms | 256 KB |
input-010.txt | AC | 2 ms | 256 KB |
input-011.txt | AC | 2 ms | 256 KB |
input-012.txt | AC | 2 ms | 256 KB |
input-013.txt | AC | 2 ms | 256 KB |
input-014.txt | AC | 3 ms | 256 KB |
input-015.txt | AC | 3 ms | 256 KB |
input-016.txt | AC | 3 ms | 256 KB |
input-017.txt | AC | 3 ms | 256 KB |
input-018.txt | AC | 4 ms | 256 KB |
input-019.txt | AC | 4 ms | 256 KB |
input-020.txt | AC | 4 ms | 256 KB |
input-021.txt | AC | 6 ms | 384 KB |
input-022.txt | AC | 5 ms | 256 KB |
input-023.txt | AC | 5 ms | 256 KB |
input-024.txt | AC | 6 ms | 256 KB |
input-025.txt | AC | 6 ms | 256 KB |
input-026.txt | AC | 7 ms | 256 KB |
input-027.txt | AC | 7 ms | 256 KB |
input-028.txt | AC | 8 ms | 256 KB |
input-029.txt | AC | 9 ms | 256 KB |
input-030.txt | AC | 9 ms | 256 KB |
input-031.txt | AC | 10 ms | 256 KB |
input-032.txt | AC | 11 ms | 256 KB |
input-033.txt | AC | 12 ms | 256 KB |
input-034.txt | AC | 12 ms | 256 KB |
input-035.txt | AC | 13 ms | 256 KB |
input-036.txt | AC | 14 ms | 256 KB |
input-037.txt | AC | 16 ms | 256 KB |
input-038.txt | AC | 17 ms | 256 KB |
input-039.txt | AC | 20 ms | 256 KB |
input-040.txt | AC | 19 ms | 256 KB |
input-041.txt | AC | 20 ms | 256 KB |
input-042.txt | AC | 22 ms | 256 KB |
input-043.txt | AC | 23 ms | 256 KB |
input-044.txt | AC | 29 ms | 256 KB |
input-045.txt | AC | 26 ms | 256 KB |
input-046.txt | AC | 28 ms | 256 KB |
input-047.txt | AC | 30 ms | 384 KB |
input-048.txt | AC | 32 ms | 256 KB |
input-049.txt | AC | 39 ms | 256 KB |
input-050.txt | AC | 35 ms | 256 KB |
input-051.txt | AC | 38 ms | 384 KB |
input-052.txt | AC | 40 ms | 256 KB |
input-053.txt | AC | 42 ms | 256 KB |
input-054.txt | AC | 44 ms | 256 KB |
input-055.txt | AC | 47 ms | 256 KB |
input-056.txt | AC | 49 ms | 256 KB |
input-057.txt | AC | 52 ms | 256 KB |
input-058.txt | AC | 55 ms | 256 KB |
input-059.txt | AC | 58 ms | 256 KB |
input-060.txt | AC | 61 ms | 256 KB |
input-061.txt | AC | 64 ms | 256 KB |
input-062.txt | AC | 67 ms | 256 KB |
input-063.txt | AC | 71 ms | 256 KB |
input-064.txt | AC | 75 ms | 256 KB |
input-065.txt | AC | 79 ms | 256 KB |
input-066.txt | AC | 80 ms | 256 KB |
input-067.txt | WA | 84 ms | 256 KB |
input-068.txt | WA | 88 ms | 256 KB |
input-069.txt | WA | 92 ms | 256 KB |
input-070.txt | WA | 96 ms | 256 KB |
input-071.txt | WA | 100 ms | 256 KB |
input-072.txt | WA | 104 ms | 256 KB |
input-073.txt | WA | 109 ms | 384 KB |
input-074.txt | WA | 114 ms | 384 KB |
input-075.txt | WA | 124 ms | 384 KB |
input-076.txt | WA | 123 ms | 384 KB |
input-077.txt | WA | 128 ms | 256 KB |
input-078.txt | WA | 135 ms | 256 KB |
input-079.txt | WA | 139 ms | 384 KB |
input-080.txt | WA | 144 ms | 384 KB |
input-081.txt | WA | 161 ms | 384 KB |
input-082.txt | WA | 156 ms | 384 KB |
input-083.txt | WA | 162 ms | 384 KB |
input-084.txt | WA | 168 ms | 384 KB |
input-085.txt | WA | 174 ms | 384 KB |
input-086.txt | WA | 181 ms | 256 KB |
input-087.txt | WA | 187 ms | 256 KB |
input-088.txt | WA | 196 ms | 384 KB |
input-089.txt | WA | 200 ms | 256 KB |
input-090.txt | WA | 210 ms | 256 KB |
input-091.txt | WA | 215 ms | 384 KB |
input-092.txt | WA | 258 ms | 384 KB |
input-093.txt | WA | 230 ms | 256 KB |
input-094.txt | WA | 239 ms | 256 KB |
input-095.txt | WA | 249 ms | 256 KB |
input-096.txt | WA | 254 ms | 384 KB |
input-097.txt | WA | 263 ms | 384 KB |
input-098.txt | WA | 271 ms | 384 KB |
input-099.txt | WA | 283 ms | 384 KB |
input-100.txt | WA | 291 ms | 384 KB |