ea99443fa2 2014-06-07 kinaba: #include <iostream> ea99443fa2 2014-06-07 kinaba: #include <sstream> ea99443fa2 2014-06-07 kinaba: #include <iomanip> ea99443fa2 2014-06-07 kinaba: #include <vector> ea99443fa2 2014-06-07 kinaba: #include <string> ea99443fa2 2014-06-07 kinaba: #include <map> ea99443fa2 2014-06-07 kinaba: #include <set> ea99443fa2 2014-06-07 kinaba: #include <algorithm> ea99443fa2 2014-06-07 kinaba: #include <numeric> ea99443fa2 2014-06-07 kinaba: #include <iterator> ea99443fa2 2014-06-07 kinaba: #include <functional> ea99443fa2 2014-06-07 kinaba: #include <complex> ea99443fa2 2014-06-07 kinaba: #include <queue> ea99443fa2 2014-06-07 kinaba: #include <stack> ea99443fa2 2014-06-07 kinaba: #include <cmath> ea99443fa2 2014-06-07 kinaba: #include <cassert> ea99443fa2 2014-06-07 kinaba: #include <tuple> ea99443fa2 2014-06-07 kinaba: using namespace std; ea99443fa2 2014-06-07 kinaba: typedef long long LL; ea99443fa2 2014-06-07 kinaba: typedef complex<double> CMP; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: class AliceAndFriends { public: ea99443fa2 2014-06-07 kinaba: double getMoney(vector <int> cards) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: int N = cards.size(); ea99443fa2 2014-06-07 kinaba: double ex = 0.0; ea99443fa2 2014-06-07 kinaba: for(int alice=0; alice<N; ++alice) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: double best = -1e+300; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int R = cards[alice]; ea99443fa2 2014-06-07 kinaba: for(int B=0; B<=R; ++B) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: double total_gain = 0.0; ea99443fa2 2014-06-07 kinaba: for(int i=0; i<N; ++i) if(i!=alice) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: int r = cards[i]; ea99443fa2 2014-06-07 kinaba: double best_you = 1e+300; ea99443fa2 2014-06-07 kinaba: int b; ea99443fa2 2014-06-07 kinaba: if(R==r) ea99443fa2 2014-06-07 kinaba: b = B; ea99443fa2 2014-06-07 kinaba: else if(R < r) ea99443fa2 2014-06-07 kinaba: b = 0; ea99443fa2 2014-06-07 kinaba: else { ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: // r-b > R-B ea99443fa2 2014-06-07 kinaba: // r-b > R+B ea99443fa2 2014-06-07 kinaba: // r+b > R-B ea99443fa2 2014-06-07 kinaba: // r+b > R+B ea99443fa2 2014-06-07 kinaba: // ができるだけ成り立ちたい ea99443fa2 2014-06-07 kinaba: for(int b=0; b<=r; ++b) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: // Alice: [R-B or R+B] ea99443fa2 2014-06-07 kinaba: // You: [r-b or r+b] ea99443fa2 2014-06-07 kinaba: double s = 0.0; ea99443fa2 2014-06-07 kinaba: s += (r-b<R-B ? +0.25 : r-b>R-B ? -0.25 : 0); ea99443fa2 2014-06-07 kinaba: s += (r-b<R+B ? +0.25 : r-b>R+B ? -0.25 : 0); ea99443fa2 2014-06-07 kinaba: s += (r+b<R-B ? +0.25 : r+b>R-B ? -0.25 : 0); ea99443fa2 2014-06-07 kinaba: s += (r+b<R+B ? +0.25 : r+b>R+B ? -0.25 : 0); ea99443fa2 2014-06-07 kinaba: best_you = min(best_you, s); ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: total_gain += best_you; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: best = max(best, total_gain); ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: ex += best; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: return ex / N; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: }; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: // BEGIN CUT HERE ea99443fa2 2014-06-07 kinaba: #include <ctime> ea99443fa2 2014-06-07 kinaba: double start_time; string timer() ea99443fa2 2014-06-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ea99443fa2 2014-06-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ea99443fa2 2014-06-07 kinaba: { os << "{ "; ea99443fa2 2014-06-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ea99443fa2 2014-06-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ea99443fa2 2014-06-07 kinaba: void verify_case(const double& Expected, const double& Received) { ea99443fa2 2014-06-07 kinaba: bool ok = (abs(Expected - Received) < 1e-9); ea99443fa2 2014-06-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ea99443fa2 2014-06-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ea99443fa2 2014-06-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ea99443fa2 2014-06-07 kinaba: #define END verify_case(_, AliceAndFriends().getMoney(cards));} ea99443fa2 2014-06-07 kinaba: int main(){ ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: CASE(0) ea99443fa2 2014-06-07 kinaba: int cards_[] = {10, 1}; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = 0.0; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(1) ea99443fa2 2014-06-07 kinaba: int cards_[] = {10, 9}; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = -0.25; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(2) ea99443fa2 2014-06-07 kinaba: int cards_[] = {1, 3}; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = 0.0; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(3) ea99443fa2 2014-06-07 kinaba: int cards_[] = {1000000000, 1000000000}; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = 0.0; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(4) ea99443fa2 2014-06-07 kinaba: int cards_[] = {42, 468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996, ea99443fa2 2014-06-07 kinaba: 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539, ea99443fa2 2014-06-07 kinaba: 870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674, 665, 142, 712, 254, 869}; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = -9.095; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: /* ea99443fa2 2014-06-07 kinaba: CASE(5) ea99443fa2 2014-06-07 kinaba: int cards_[] = ; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(6) ea99443fa2 2014-06-07 kinaba: int cards_[] = ; ea99443fa2 2014-06-07 kinaba: vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); ea99443fa2 2014-06-07 kinaba: double _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: */ ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: // END CUT HERE