• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/667-U/1A-U.cpp version [8f81dce206d33d35]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +inline int bitcnt(int x)
           23  +{
           24  + int c = 0;
           25  + for(; x; x>>=1)
           26  +  c += x&1;
           27  + return c;
           28  +}
           29  +
           30  +class OrderOfOperations { public:
           31  + int minTime(vector <string> s)
           32  + {
           33  +  const int M = s[0].size();
           34  +
           35  +  vector<int> edge;
           36  +  int all = 0;
           37  +  for(auto& si: s) {
           38  +   int x = 0;
           39  +   for(int i=0; i<M; ++i)
           40  +    x |= (si[i]=='1')<<i;
           41  +   edge.emplace_back(x);
           42  +   all |= x;
           43  +  }
           44  +  vector<int> nbits;
           45  +  for(int m=0; m<(1<<M); ++m)
           46  +   nbits.emplace_back(bitcnt(m));
           47  +
           48  +  typedef int Vert, Cost;
           49  +  typedef pair<Cost,Vert> Edge;
           50  +  priority_queue<Edge, vector<Edge>, greater<Edge>> Q;
           51  +  Q.emplace(0, 0);
           52  +  vector<bool> V(1<<M);
           53  +  while(!Q.empty())
           54  +  {
           55  +   Vert v = Q.top().second;
           56  +   Cost c = Q.top().first;
           57  +   Q.pop();
           58  +   if( V[v] )
           59  +    continue;
           60  +   V[v] = true;
           61  +
           62  +   if( v == all )
           63  +    return c;
           64  +
           65  +   for(auto e: edge)
           66  +    if( !V[v|e] )
           67  +     Q.emplace(c+nbits[(v|e)&~v]*nbits[(v|e)&~v], v|e);
           68  +  }
           69  +  return -1;
           70  + }
           71  +};
           72  +
           73  +// BEGIN CUT HERE
           74  +#include <ctime>
           75  +double start_time; string timer()
           76  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           77  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           78  + { os << "{ ";
           79  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           80  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           81  +void verify_case(const int& Expected, const int& Received) {
           82  + bool ok = (Expected == Received);
           83  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           84  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           85  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           86  +#define END  verify_case(_, OrderOfOperations().minTime(s));}
           87  +int main(){
           88  +
           89  +CASE(0)
           90  + string s_[] = {
           91  + "111",
           92  + "001",
           93  + "010"
           94  +};
           95  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
           96  + int _ = 3;
           97  +END
           98  +CASE(1)
           99  + string s_[] = {
          100  + "11101",
          101  + "00111",
          102  + "10101",
          103  + "00000",
          104  + "11000"
          105  +};
          106  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          107  + int _ = 9;
          108  +END
          109  +CASE(2)
          110  + string s_[] = {
          111  +  "11111111111111111111"
          112  +};
          113  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          114  + int _ = 400;
          115  +END
          116  +CASE(3)
          117  + string s_[] = {
          118  +  "1000",
          119  +  "1100",
          120  +  "1110"
          121  +};
          122  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          123  + int _ = 3;
          124  +END
          125  +CASE(4)
          126  + string s_[] = {
          127  +  "111",
          128  +  "111",
          129  +  "110",
          130  +  "100"
          131  +};
          132  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          133  + int _ = 3;
          134  +END
          135  +CASE(5)
          136  + string s_[] = {"00100001010101000101","11011001110001000111","01011001010101111001","01011100110111000111","11000100001100001000","11110000101111111111","10010110010000000111","10001100001101110001","00010001100000010010","10001111001101101011","01010111000111100110","00111100010101100010","00110111000100111111","01100000110001000010","11011001011011101100","11111101100111101100","10011101010111101010","11001100000100011100","10111010000011100101","11001000000000011110","10110010101111110000","10101001011011100010","00101001111000110100","10011000010100011000","00011000001011110111","00111000101010001111","01011110110001111100","01010001100001010100","11001010000011000101","00000100010101101000","11100110101101011101","01110100101010100011","10100000100100010100","00111101010111101100","10101011110111111011","01001101010110000000","00111110001011010101","01011011010100011111","11011110011011111111","11111100000011110111","00110001010001100010","00100101011011100001","10101111001101011011","01011101100100010010","01000001010011101100","11001010100110001110","00010110001001110001","01000001111111110100","01001100101111101011","00010101001100110110"};
          137  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          138  + int _ = -2;
          139  +END
          140  +CASE(6)
          141  + string s_[] = {
          142  +  "1100",
          143  +  "0011",
          144  +  "0110",
          145  + };
          146  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          147  + int _ = 6;
          148  +END
          149  +}
          150  +// END CUT HERE

Added SRM/667-U/1B-U.cpp version [e7836058c4211ebe]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class CatsOnTheCircle { public:
           23  + int N;
           24  + double p;
           25  +
           26  + double getProb(int N_, int K, int p_)
           27  + {
           28  +  N = N_;
           29  +  p = p_ / pow(10.0,9);
           30  +  return rec(false, 1, K-1);
           31  + }
           32  +/*
           33  + void rec2(int V,
           34  +  vector<double>* p_t2e,
           35  +  vector<double>* q_t2e) {
           36  +  if(V == N-1) {
           37  +   p_t2e->assign(1, 1.0);
           38  +   q_t2e->assign(1, 1.0);
           39  +   return;
           40  +  }
           41  +
           42  +  vector<double> pp, qq;
           43  +  rec2(V+1, &pp, &qq);
           44  +
           45  +  vector<double> pp2;
           46  +  pp2 += (pp<<1) * rightOut(p,V);
           47  +  pp2 += rev(qq<<1) * (1-rightOut(p,V));
           48  + }
           49  +*/
           50  + double rec(bool inv, int V, int T) {
           51  +  if(V == N-1)
           52  +   return 1.0;
           53  +  double pp = 0.0;
           54  +  if(T!=0) pp += rightOut(inv?1-p:p,V) * rec(inv, V+1,T-1);
           55  +  if(T!=N-V-1) pp += (1-rightOut(inv?1-p:p,V)) * rec(!inv, V+1,N-V-2-T);
           56  +  return pp;
           57  + }
           58  +
           59  + double rightOut(const double p, int V) {
           60  +  if(V==1)
           61  +   return p;
           62  +  //x = p + (1-p)y
           63  +  //y = rightOut(V-1)x
           64  +  return p / (1 - (1-p)*rightOut(p, V-1));
           65  + }
           66  +};
           67  +
           68  +// BEGIN CUT HERE
           69  +#include <ctime>
           70  +double start_time; string timer()
           71  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           72  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           73  + { os << "{ ";
           74  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           75  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           76  +void verify_case(const double& Expected, const double& Received) {
           77  + bool ok = (abs(Expected - Received) < 1e-9);
           78  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           79  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           80  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           81  +#define END  verify_case(_, CatsOnTheCircle().getProb(N, K, p));}
           82  +int main(){
           83  +
           84  +CASE(0)
           85  + int N = 3;
           86  + int K = 1;
           87  + int p = 300000000;
           88  + double _ = 0.6999999999999985;
           89  +END
           90  +CASE(1)
           91  + int N = 6;
           92  + int K = 2;
           93  + int p = 500000000;
           94  + double _ = 0.2;
           95  +END
           96  +CASE(2)
           97  + int N = 6;
           98  + int K = 5;
           99  + int p = 500000000;
          100  + double _ = 0.2;
          101  +END
          102  +CASE(3)
          103  + int N = 10;
          104  + int K = 2;
          105  + int p = 666666666;
          106  + double _ = 0.00391389439551009;
          107  +END
          108  +CASE(4)
          109  + int N = 999999999;
          110  + int K = 999999996;
          111  + int p = 777777777;
          112  + double _ = 0.05830903870125612;
          113  +END
          114  +CASE(5)
          115  + int N = 1000000000;
          116  + int K = 4;
          117  + int p = 300000000;
          118  + double _ = 0.044981259448371;
          119  +END
          120  +CASE(6)
          121  + int N = 534428790;
          122  + int K = 459947197;
          123  + int p = 500000000;
          124  + double _ = 1.871156682766205E-9;
          125  +END
          126  +/*
          127  +CASE(7)
          128  + int N = ;
          129  + int K = ;
          130  + int p = ;
          131  + double _ = ;
          132  +END
          133  +CASE(8)
          134  + int N = ;
          135  + int K = ;
          136  + int p = ;
          137  + double _ = ;
          138  +END
          139  +*/
          140  +}
          141  +// END CUT HERE