SHARE
TWEET

CarrotBoxes

a guest Feb 5th, 2011 152 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <math.h>
  12.  
  13. using namespace std;
  14.  
  15. class CarrotBoxes
  16. {
  17.     int n;
  18.     vector< vector<int> > adj;
  19.  
  20. public:
  21.     double theProbability(vector <string> info)
  22.     {
  23.         n = info.size();
  24.         adj.resize(n);
  25.         for(int i=0; i<n; i++){
  26.             adj[i].resize(n);
  27.             for(int j=0; j<info[i].length(); j++)
  28.                 adj[i][j] = (info[i][j] == 'Y') ? 1 : 0;
  29.         }
  30.         FloydWarshall( );
  31.         vector<int> comp(n);
  32.         StronglyConnectedComponents(comp);
  33.  
  34.         /* Encontra as fontes (grau de entrada = 0) */
  35.         vector<int> indeg(n);
  36.         for(int i=0; i<n; i++){
  37.             if(comp[i] != i) continue;
  38.             for(int j=0; j<n; j++)
  39.                 indeg[j] += (adj[i][j] && j != i);
  40.         }
  41.         /* Conta qtas fontes alcancam cada vertice */
  42.         vector<int> reach(n);
  43.         for(int i=0; i<n; i++){
  44.             if(comp[i] != i || indeg[i] != 0) continue;
  45.             for(int j=0; j<n; j++)
  46.                 if (i != j && adj[i][j]) reach[j]++;
  47.         }
  48.         /* Se houver uma fonte que so alcanca folha que
  49.            alguma outra folha alcanca, podemos ignora-la */
  50.         int open = 0;
  51.         int last = 0;
  52.         for(int i=0; i<n; i++){
  53.             if(comp[i] != i || indeg[i] != 0) continue;
  54.             int min_reach = n+1;
  55.             for(int j=0; j<n; j++)
  56.                 if (i != j && adj[i][j])
  57.                     min_reach = min(min_reach, reach[j]);
  58.             if (min_reach == 1 || last) // Nao podemos ignorar
  59.                 open++;
  60.              else last = 1;
  61.         }
  62.         return(1.0 - open*(1.0/n));
  63.     }
  64.     void FloydWarshall( ){
  65.         for(int k=0; k<n; k++)
  66.             for(int i=0; i<n; i++)
  67.                 for(int j=0; j<n; j++)
  68.                     adj[i][j] = max(adj[i][j], adj[i][k] * adj[k][j]);
  69.     }
  70.     void StronglyConnectedComponents(vector<int> &comp){
  71.         comp.assign(n, -1);
  72.         for(int i=0; i<n; i++){
  73.             if(comp[i] != -1) continue;
  74.             for(int j=0; j<n; j++){
  75.                 if(adj[i][j] && adj[j][i])
  76.                     comp[j] = i;
  77.             }
  78.         }
  79.     }
  80.    
  81. // BEGIN CUT HERE
  82.         public:
  83.         void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
  84.         private:
  85.         template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
  86.         void verify_case(int Case, const double &Expected, const double &Received) { cerr << "Test Case #" << Case << "..."; if (Expected <= Received + 1e-8 && Expected >= Received - 1e-8) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
  87.         void test_case_0() { string Arr0[] = {"YYYYY",
  88.  "NYNNN",
  89.  "NNYNN",
  90.  "NNNYN",
  91.  "NNNNY"}
  92. ; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.8; verify_case(0, Arg1, theProbability(Arg0)); }
  93.         void test_case_1() { string Arr0[] = {"YNNNN",
  94.  "NYNNN",
  95.  "NNYNN",
  96.  "NNNYN",
  97.  "NNNNY"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.2; verify_case(1, Arg1, theProbability(Arg0)); }
  98.         void test_case_2() { string Arr0[] = {"Y"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 1.0; verify_case(2, Arg1, theProbability(Arg0)); }
  99.         void test_case_3() { string Arr0[] = {"YNNNN",
  100.  "YYNNN",
  101.  "YNYNN",
  102.  "NNNYY",
  103.  "NNNYY"}
  104. ; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.6; verify_case(3, Arg1, theProbability(Arg0)); }
  105.         void test_case_4() { string Arr0[] = {"YYYNNNYN",
  106.  "NYNNNNYN",
  107.  "NNYNNNNN",
  108.  "NYNYNNNN",
  109.  "YNNNYNNY",
  110.  "NNYNNYNN",
  111.  "NNNNYNYN",
  112.  "NNYNNNNY"}
  113. ; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.875; verify_case(4, Arg1, theProbability(Arg0)); }
  114.         void test_case_5() { string Arr0[] = {"YNNNNNNNNYNNNNNNNNNN",
  115.  "NYNNNNNNNNNNNNNNNNNN",
  116.  "NNYNNNNNNNYNNNNNYNNN",
  117.  "NNNYNYNNNNNNNNYNNNNN",
  118.  "NNNNYNNNNNNNNNYNNNNY",
  119.  "NNNNNYNNNNNNNNNNNNNY",
  120.  "NNNNYNYNYNNNNNNNNNNN",
  121.  "NNNNNNNYNNNYYNNNNNNN",
  122.  "NNNNNNNNYNNNNNNNNNNN",
  123.  "YNNNNNNNNYNNNNNYNNNN",
  124.  "NNNNNNNNNNYNNNNNNNNN",
  125.  "NYNNNNNNNNNYNNNNNNNN",
  126.  "NNNNNNNYNNNNYNNNNNNN",
  127.  "NNNNNNNNNNNNNYNNNYNN",
  128.  "NNNNNNNNNNNYNNYNNNYN",
  129.  "NYNNNNNNNNNNNNNYNNNN",
  130.  "NNYNNNNNNNNNNNNNYNNN",
  131.  "NNNNNNNNNNNNNYNYNYNN",
  132.  "NNNNNNNNYNYNNNNNNNYY",
  133.  "NNNYNNNNNNNNNNNNNNNY"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.75; verify_case(5, Arg1, theProbability(Arg0)); }
  134.  
  135. // END CUT HERE
  136.  
  137. };
  138.  
  139. // BEGIN CUT HERE
  140. int main()
  141. {
  142.     CarrotBoxes ___test;
  143.     ___test.run_test(-1);
  144. }
  145. // END CUT HERE
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top