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

Added SRM/TCO14-1B/1A.cpp version [d72e60e00215d96c]

            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 SpamChecker { public:
           23  + string spamCheck(string judgeLog, int good, int bad)
           24  + {
           25  +  return isBad(judgeLog, good, bad) ? "SPAM" : "NOT SPAM";
           26  + }
           27  +
           28  + bool isBad(string judgeLog, int good, int bad)
           29  + {
           30  +  int score = 0;
           31  +  for(char c: judgeLog)
           32  +   if((score += c=='o' ? good : -bad) < 0)
           33  +    return true;
           34  +  return false;
           35  + }
           36  +};
           37  +
           38  +// BEGIN CUT HERE
           39  +#include <ctime>
           40  +double start_time; string timer()
           41  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           42  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           43  + { os << "{ ";
           44  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           45  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           46  +void verify_case(const string& Expected, const string& Received) {
           47  + bool ok = (Expected == Received);
           48  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           49  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           50  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           51  +#define END  verify_case(_, SpamChecker().spamCheck(judgeLog, good, bad));}
           52  +int main(){
           53  +
           54  +CASE(0)
           55  + string judgeLog = "ooooxxxo";
           56  + int good = 2;
           57  + int bad = 3;
           58  + string _ = "SPAM";
           59  +END
           60  +CASE(1)
           61  + string judgeLog = "ooooxxxo";
           62  + int good = 3;
           63  + int bad = 4;
           64  + string _ = "NOT SPAM";
           65  +END
           66  +CASE(2)
           67  + string judgeLog = "xooooooooooooooooooooooooooo";
           68  + int good = 1000;
           69  + int bad = 1;
           70  + string _ = "SPAM";
           71  +END
           72  +CASE(3)
           73  + string judgeLog = "oxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
           74  + int good = 1000;
           75  + int bad = 1;
           76  + string _ = "NOT SPAM";
           77  +END
           78  +CASE(4)
           79  + string judgeLog = "ooxoxoxooxoxxoxoxooxoxoxoxxoxx";
           80  + int good = 15;
           81  + int bad = 17;
           82  + string _ = "SPAM";
           83  +END
           84  +CASE(5)
           85  + string judgeLog = "oooxoxoxoxoxoxooxooxoxooxo";
           86  + int good = 16;
           87  + int bad = 18;
           88  + string _ = "NOT SPAM";
           89  +END
           90  +/*
           91  +CASE(6)
           92  + string judgeLog = ;
           93  + int good = ;
           94  + int bad = ;
           95  + string _ = ;
           96  +END
           97  +CASE(7)
           98  + string judgeLog = ;
           99  + int good = ;
          100  + int bad = ;
          101  + string _ = ;
          102  +END
          103  +*/
          104  +}
          105  +// END CUT HERE

Added SRM/TCO14-1B/1B.cpp version [27ee55f46dcdfc29]

            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  +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 WolvesAndSheep { public:
           31  + int getmin(vector <string> field)
           32  + {
           33  +  int H = field.size();
           34  +  int W = field[0].size();
           35  +  int best = W*H;
           36  +  for(int mask=0; mask<(1<<(W-1)); ++mask)
           37  +  {
           38  +   vector<vector<pair<int,int>>> sw(H);
           39  +   for(int y=0; y<field.size(); ++y)
           40  +    for(int s=0,w=0,x=0; x<W; ++x)
           41  +    {
           42  +     if(field[y][x]=='S') s++;
           43  +     if(field[y][x]=='W') w++;
           44  +     if(s&&w)
           45  +      goto next;
           46  +     if((mask & (1<<x)) || x==W-1) {
           47  +      sw[y].emplace_back(s,w);
           48  +      s=w=0;
           49  +     }
           50  +    }
           51  +   {
           52  +    int score = bitcnt(mask);
           53  +    int WW = sw[0].size();
           54  +    vector<pair<int,int>> cur(WW);
           55  +    for(int y=0; y<sw.size(); ++y)
           56  +    {
           57  +     bool dame = false;
           58  +     for(int x=0; x<WW; ++x) {
           59  +      cur[x].first += sw[y][x].first;
           60  +      cur[x].second += sw[y][x].second;
           61  +      if(cur[x].first && cur[x].second)
           62  +       dame = true;
           63  +     }
           64  +     if(dame) {
           65  +      score ++;
           66  +      cur = sw[y];
           67  +     }
           68  +    }
           69  +
           70  +    best = min(best, score);
           71  +   }
           72  +  next:;
           73  +  }
           74  +  return best;
           75  + }
           76  +};
           77  +
           78  +// BEGIN CUT HERE
           79  +#include <ctime>
           80  +double start_time; string timer()
           81  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           82  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           83  + { os << "{ ";
           84  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           85  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           86  +void verify_case(const int& Expected, const int& Received) {
           87  + bool ok = (Expected == Received);
           88  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           89  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           90  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           91  +#define END  verify_case(_, WolvesAndSheep().getmin(field));}
           92  +int main(){
           93  +
           94  +CASE(0)
           95  + string field_[] = {"W.WSS",
           96  + "WW.S.",
           97  + ".SSS.",
           98  + "SSS.S",
           99  + ".SS.S"};
          100  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          101  + int _ = 2;
          102  +END
          103  +CASE(1)
          104  + string field_[] = {".....",
          105  + ".....",
          106  + "....."};
          107  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          108  + int _ = 0;
          109  +END
          110  +CASE(2)
          111  + string field_[] = {".SS",
          112  + "...",
          113  + "S..",
          114  + "W.W"};
          115  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          116  + int _ = 1;
          117  +END
          118  +CASE(3)
          119  + string field_[] = {"WWWSWWSSWWW",
          120  + "WWSWW.SSWWW",
          121  + "WS.WSWWWWS."};
          122  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          123  + int _ = 10;
          124  +END
          125  +CASE(4)
          126  + string field_[] = {".W.S.W.W",
          127  + "W.W.S.W.",
          128  + ".S.S.W.W",
          129  + "S.S.S.W.",
          130  + ".S.W.W.S",
          131  + "S.S.W.W.",
          132  + ".W.W.W.S",
          133  + "W.W.S.S."};
          134  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          135  + int _ = 7;
          136  +END
          137  +CASE(5)
          138  + string field_[] = {"W.SSWWSSSW.SS",
          139  + ".SSSSW.SSWWWW",
          140  + ".WWWWS.WSSWWS",
          141  + "SS.WSS..W.WWS",
          142  + "WSSS.SSWS.W.S",
          143  + "WSS.WS...WWWS",
          144  + "S.WW.S.SWWWSW",
          145  + "WSSSS.SSW...S",
          146  + "S.WWSW.WWSWSW",
          147  + ".WSSS.WWSWWWS",
          148  + "..SSSS.WWWSSS",
          149  + "SSWSWWS.W.SSW",
          150  + "S.WSWS..WSSS.",
          151  + "WS....W..WSS."};
          152  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          153  + int _ = 24;
          154  +END
          155  +CASE(6)
          156  + string field_[] = {"WW..SS",
          157  + "WW..SS",
          158  + "......",
          159  + "......",
          160  + "SS..WW",
          161  + "SS..WW"};
          162  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          163  + int _ = 2;
          164  +END
          165  +/*
          166  +CASE(7)
          167  + string field_[] = ;
          168  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          169  + int _ = ;
          170  +END
          171  +CASE(8)
          172  + string field_[] = ;
          173  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          174  + int _ = ;
          175  +END
          176  +*/
          177  +}
          178  +// END CUT HERE

Added SRM/TCO14-1B/1C.cpp version [7c1aa38966342ddc]

            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  +double C(int n, int k)
           23  +{
           24  + k = min(n-k, k);
           25  + double t = 1;
           26  + for(int i=1; i<=k; ++i)
           27  +  t = t * (n-i+1) / i;
           28  + return t;
           29  +}
           30  +
           31  +class EagleInZoo { public:
           32  + double calc(vector <int> parent, int K)
           33  + {
           34  +  int N = parent.size() + 1;
           35  +  vector<vector<int>> child(N);
           36  +  for(int i=1; i<N; ++i)
           37  +   child[parent[i-1]].push_back(i);
           38  +  return rec(child, 0, K);
           39  + }
           40  +
           41  + map<pair<int,int>,double> memo;
           42  + double rec(const vector<vector<int>>& child, int v, int K)
           43  + {
           44  +  if(K == 1)
           45  +   return 1.0;
           46  +  if(child[v].empty())
           47  +   return 0.0;
           48  +  pair<int,int> key(v, K);
           49  +  if(memo.count(key)) return memo[key];
           50  +
           51  +  double ans = 0.0;
           52  +  for(int u: child[v]) // When K-the eagle goes to |u|.
           53  +   for(int uN=0; uN<=K-2; ++uN) // When uN out of K-2 previous eagles went to |u|.
           54  +   {
           55  +    ans += C(K-2, uN)
           56  +     * pow(1.0/child[v].size(), uN)
           57  +     * pow(1.0-1.0/child[v].size(), K-2-uN)
           58  +     * rec(child, u, uN+1);
           59  +   }
           60  +  return memo[key] = ans / child[v].size();
           61  + }
           62  +};
           63  +
           64  +// BEGIN CUT HERE
           65  +#include <ctime>
           66  +double start_time; string timer()
           67  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           68  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           69  + { os << "{ ";
           70  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           71  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           72  +void verify_case(const double& Expected, const double& Received) {
           73  + bool ok = (abs(Expected - Received) < 1e-9);
           74  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           75  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           76  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           77  +#define END  verify_case(_, EagleInZoo().calc(parent, K));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + int parent_[] = {0,0};
           82  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
           83  + int K = 2;
           84  + double _ = 1.0;
           85  +END
           86  +CASE(1)
           87  + int parent_[] = {0,0};
           88  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
           89  + int K = 3;
           90  + double _ = 0.5;
           91  +END
           92  +CASE(2)
           93  + int parent_[] = {0,1,0,3};
           94  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
           95  + int K = 4;
           96  + double _ = 0.75;
           97  +END
           98  +CASE(3)
           99  + int parent_[] = {0,0,1,1,2,4,4,4,5,5,6,6};
          100  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
          101  + int K = 20;
          102  + double _ = 0.14595168754091617;
          103  +END
          104  +CASE(4)
          105  + int parent_[] = {0,1,2,3,2,1,1,7,0,9,10,11,12,13,14,15,16,17,18,14,9};
          106  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
          107  + int K = 24;
          108  + double _ = 0.3272154791654077;
          109  +END
          110  +CASE(5)
          111  + int parent_[] = {0,1,2,3,4,5,6,7,8,9,10};
          112  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
          113  + int K = 50;
          114  + double _ = 0.0;
          115  +END
          116  +/*
          117  +CASE(6)
          118  + int parent_[] = ;
          119  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
          120  + int K = ;
          121  + double _ = ;
          122  +END
          123  +CASE(7)
          124  + int parent_[] = ;
          125  +   vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
          126  + int K = ;
          127  + double _ = ;
          128  +END
          129  +*/
          130  +}
          131  +// END CUT HERE