Submission #323607
Source Code Expand
#include <iostream> #include <iomanip> #include <sstream> #include <vector> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <functional> #include <iterator> #include <limits> #include <numeric> #include <utility> #include <cmath> #include <cassert> #include <cstdio> using namespace std; using namespace placeholders; using LL = long long; using ULL = unsigned long long; using VI = vector< int >; using VVI = vector< VI >; using VS = vector< string >; using SS = stringstream; using PII = pair< int, int >; using VPII = vector< PII >; template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; } template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i=0; i<v.size(); ++i ){ s << (" "+!i) << v[i]; } return s; } template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }; template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) ( c ).begin(), ( c ).end() #define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + p, ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define PB push_back #define EM emplace #define EB emplace_back #define BI back_inserter #define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() ) #define MP make_pair #define fst first #define snd second #define DUMP( x ) cerr << #x << " = " << ( x ) << endl double dp1[ 128 ][ 128 ][ 128 ]; double dp2[ 128 ][ 128 ]; int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int N; cin >> N; dp1[0][0][0] = 1; REP( i, 0, N + 1 ) { REP( j, 0, N + 1 ) { REP( k, 0, N + 1 ) { const double p = dp1[i][j][k] / 3; dp1[ i + 1 ][j][k] += p; dp1[i][ j + 1 ][k] += p; dp1[i][j][ k + 1 ] += p; } } } VVT< double > prob( N + 1, VT< double >( N + 1 ) ); REP( i, 0, N + 1 ) { REP( j, 0, N + 1 ) { REP( k, 0, N + 1 ) { if ( N < i + j + k || i + j + k <= 1 ) { continue; } const double p = dp1[i][j][k]; const int n = i + j + k; VI as = { i, j, k }; sort( ALL( as ) ); as.erase( remove( ALL( as ), 0 ), as.end() ); if ( as.back() == n || i == j && j == k ) { prob[n][n] += p; } else if ( as[0] < as[1] ) { prob[n][ as[0] ] += p; } // else if ( as[0] == as[1] && as[1] < as[2] ) else { prob[n][ as[0] ] += p; } } } } dp2[0][N] = 1; double res = 0; REP( i, 0, 127 ) { res += dp2[i][1] * i; REP( j, 2, N + 1 ) { REP( k, 1, N + 1 ) { dp2[ i + 1 ][k] += dp2[i][j] * prob[j][k]; } } } cout << setprecision( 8 ) << fixed << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | torus711 |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 3354 Byte |
Status | AC |
Exec Time | 84 ms |
Memory | 11560 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 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 | 24 ms | 1056 KB |
input-003.txt | AC | 25 ms | 1052 KB |
input-004.txt | AC | 23 ms | 1060 KB |
input-005.txt | AC | 23 ms | 1052 KB |
input-006.txt | AC | 23 ms | 1048 KB |
input-007.txt | AC | 23 ms | 1056 KB |
input-008.txt | AC | 25 ms | 1180 KB |
input-009.txt | AC | 22 ms | 1056 KB |
input-010.txt | AC | 23 ms | 1180 KB |
input-011.txt | AC | 23 ms | 1180 KB |
input-012.txt | AC | 24 ms | 1056 KB |
input-013.txt | AC | 24 ms | 1308 KB |
input-014.txt | AC | 23 ms | 1308 KB |
input-015.txt | AC | 25 ms | 1312 KB |
input-016.txt | AC | 25 ms | 1308 KB |
input-017.txt | AC | 25 ms | 1312 KB |
input-018.txt | AC | 25 ms | 1248 KB |
input-019.txt | AC | 26 ms | 1564 KB |
input-020.txt | AC | 24 ms | 1568 KB |
input-021.txt | AC | 24 ms | 1564 KB |
input-022.txt | AC | 25 ms | 1440 KB |
input-023.txt | AC | 27 ms | 1692 KB |
input-024.txt | AC | 26 ms | 1692 KB |
input-025.txt | AC | 26 ms | 1700 KB |
input-026.txt | AC | 27 ms | 1824 KB |
input-027.txt | AC | 27 ms | 1832 KB |
input-028.txt | AC | 26 ms | 1828 KB |
input-029.txt | AC | 26 ms | 1836 KB |
input-030.txt | AC | 28 ms | 2076 KB |
input-031.txt | AC | 28 ms | 2208 KB |
input-032.txt | AC | 29 ms | 2140 KB |
input-033.txt | AC | 29 ms | 2332 KB |
input-034.txt | AC | 29 ms | 2144 KB |
input-035.txt | AC | 28 ms | 2456 KB |
input-036.txt | AC | 28 ms | 2456 KB |
input-037.txt | AC | 31 ms | 2476 KB |
input-038.txt | AC | 29 ms | 2592 KB |
input-039.txt | AC | 30 ms | 2732 KB |
input-040.txt | AC | 30 ms | 2728 KB |
input-041.txt | AC | 31 ms | 2856 KB |
input-042.txt | AC | 32 ms | 2968 KB |
input-043.txt | AC | 33 ms | 3096 KB |
input-044.txt | AC | 33 ms | 3104 KB |
input-045.txt | AC | 33 ms | 3224 KB |
input-046.txt | AC | 35 ms | 3360 KB |
input-047.txt | AC | 35 ms | 3484 KB |
input-048.txt | AC | 37 ms | 3496 KB |
input-049.txt | AC | 36 ms | 3496 KB |
input-050.txt | AC | 36 ms | 3748 KB |
input-051.txt | AC | 37 ms | 3876 KB |
input-052.txt | AC | 38 ms | 3880 KB |
input-053.txt | AC | 39 ms | 4008 KB |
input-054.txt | AC | 38 ms | 4268 KB |
input-055.txt | AC | 39 ms | 4368 KB |
input-056.txt | AC | 39 ms | 4384 KB |
input-057.txt | AC | 40 ms | 4380 KB |
input-058.txt | AC | 43 ms | 4764 KB |
input-059.txt | AC | 40 ms | 4752 KB |
input-060.txt | AC | 43 ms | 4904 KB |
input-061.txt | AC | 43 ms | 4904 KB |
input-062.txt | AC | 44 ms | 5284 KB |
input-063.txt | AC | 44 ms | 5288 KB |
input-064.txt | AC | 47 ms | 5372 KB |
input-065.txt | AC | 57 ms | 5536 KB |
input-066.txt | AC | 51 ms | 5800 KB |
input-067.txt | AC | 48 ms | 5920 KB |
input-068.txt | AC | 50 ms | 5920 KB |
input-069.txt | AC | 48 ms | 6052 KB |
input-070.txt | AC | 51 ms | 6436 KB |
input-071.txt | AC | 50 ms | 6432 KB |
input-072.txt | AC | 51 ms | 6556 KB |
input-073.txt | AC | 52 ms | 6560 KB |
input-074.txt | AC | 55 ms | 6952 KB |
input-075.txt | AC | 54 ms | 7140 KB |
input-076.txt | AC | 57 ms | 7156 KB |
input-077.txt | AC | 56 ms | 7216 KB |
input-078.txt | AC | 56 ms | 7588 KB |
input-079.txt | AC | 57 ms | 7720 KB |
input-080.txt | AC | 61 ms | 7848 KB |
input-081.txt | AC | 63 ms | 7848 KB |
input-082.txt | AC | 62 ms | 8360 KB |
input-083.txt | AC | 62 ms | 8364 KB |
input-084.txt | AC | 63 ms | 8472 KB |
input-085.txt | AC | 65 ms | 8616 KB |
input-086.txt | AC | 65 ms | 8988 KB |
input-087.txt | AC | 66 ms | 9120 KB |
input-088.txt | AC | 69 ms | 9256 KB |
input-089.txt | AC | 68 ms | 9252 KB |
input-090.txt | AC | 71 ms | 9716 KB |
input-091.txt | AC | 72 ms | 9892 KB |
input-092.txt | AC | 75 ms | 10016 KB |
input-093.txt | AC | 75 ms | 10080 KB |
input-094.txt | AC | 77 ms | 10536 KB |
input-095.txt | AC | 78 ms | 10668 KB |
input-096.txt | AC | 77 ms | 10776 KB |
input-097.txt | AC | 81 ms | 10924 KB |
input-098.txt | AC | 80 ms | 11296 KB |
input-099.txt | AC | 84 ms | 11428 KB |
input-100.txt | AC | 83 ms | 11560 KB |