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

Added SRM/TCO13-2C-U/1A.cpp version [8ec0b22b8f67ffe8]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class DancingFoxes { public:
           23  + int minimalDays(vector <string> friendship)
           24  + {
           25  +  static const int INF = 0x1fffffff;
           26  +  int N = friendship.size();
           27  +  vector< vector<int> > M(N, vector<int>(N));
           28  +  for(int i=0; i<N; ++i)
           29  +  for(int k=0; k<N; ++k)
           30  +   M[i][k] = (friendship[i][k]=='Y' ? 1 : INF);
           31  +
           32  +  for(int k=0; k<N; ++k)
           33  +  for(int i=0; i<N; ++i)
           34  +  for(int j=0; j<N; ++j)
           35  +   M[i][j] = min(M[i][j], M[i][k]+M[k][j]);
           36  +
           37  +  if(M[0][1] == INF)
           38  +   return -1;
           39  +
           40  +  int s = 0;
           41  +  for(int d = M[0][1]; d>1; ++s)
           42  +   d -= (d+1)/3;
           43  +  return s;
           44  + }
           45  +};
           46  +
           47  +// BEGIN CUT HERE
           48  +#include <ctime>
           49  +double start_time; string timer()
           50  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           51  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           52  + { os << "{ ";
           53  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           54  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           55  +void verify_case(const int& Expected, const int& Received) {
           56  + bool ok = (Expected == Received);
           57  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           58  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           59  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           60  +#define END  verify_case(_, DancingFoxes().minimalDays(friendship));}
           61  +int main(){
           62  +
           63  +CASE(0)
           64  + string friendship_[] = {"NNY",
           65  + "NNY",
           66  + "YYN"};
           67  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
           68  + int _ = 1;
           69  +END
           70  +CASE(1)
           71  + string friendship_[] = {"NNNNN",
           72  + "NNYYY",
           73  + "NYNYY",
           74  + "NYYNY",
           75  + "NYYYN"};
           76  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
           77  + int _ = -1;
           78  +END
           79  +CASE(2)
           80  + string friendship_[] = {"NNYYNN",
           81  + "NNNNYY",
           82  + "YNNNYN",
           83  + "YNNNNY",
           84  + "NYYNNN",
           85  + "NYNYNN"};
           86  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
           87  + int _ = 2;
           88  +END
           89  +CASE(3)
           90  + string friendship_[] = {"NNYNNNNYN",
           91  + "NNNNYNYNN",
           92  + "YNNYNYNNN",
           93  + "NNYNYNYYN",
           94  + "NYNYNNNNY",
           95  + "NNYNNNYNN",
           96  + "NYNYNYNNN",
           97  + "YNNYNNNNY",
           98  + "NNNNYNNYN"};
           99  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
          100  + int _ = 3;
          101  +END
          102  +CASE(4)
          103  + string friendship_[] = {"NY",
          104  + "YN"};
          105  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
          106  + int _ = 0;
          107  +END
          108  +CASE(5)
          109  + string friendship_[] = {
          110  +"NNYNNNNNN",
          111  +"NNNNNNNNY",
          112  +"YNNYNNNNN",
          113  +"NNYNYNNNN",
          114  +"NNNYNYNNN",
          115  +"NNNNYNYNN",
          116  +"NNNNNYNYN",
          117  +"NNNNNNYNY",
          118  +"NYNNNNNYN"
          119  +};
          120  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
          121  +   int N = friendship.size();
          122  +   int idx[] = {0,8,1,2,3,4,5,6,7};
          123  +   for(int y=0; y<N; ++y, cout<<endl)
          124  +   for(int x=0; x<N; ++x) {
          125  +    cout << friendship[idx[y]][idx[x]];
          126  +   }
          127  + int _ = -1;
          128  +END
          129  +/*
          130  +CASE(6)
          131  + string friendship_[] = ;
          132  +   vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_));
          133  + int _ = ;
          134  +END
          135  +*/
          136  +}
          137  +// END CUT HERE

Added SRM/TCO13-2C-U/1B.cpp version [c50d0a704a3e9f57]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class TheMountain { public:
           23  + int minSum(int H, int W, vector <int> Y, vector <int> X, vector <int> V)
           24  + {
           25  +  const int N = Y.size();
           26  +  static const int INF = 0x3fffffff;
           27  +  int best = INF;
           28  +
           29  +  vector< vector<int> > fixed(H, vector<int>(W, 0));
           30  +  for(int i=0; i<N; ++i)
           31  +   fixed[Y[i]][X[i]] = V[i];
           32  +
           33  +  for(int x=0; x<W; ++x)
           34  +  {
           35  +   vector< vector<int> > td(H, vector<int>(W));
           36  +   vector<int> td_sum(H);
           37  +   int td_end = 0;
           38  +   for(int y=0; y<H; ++y)
           39  +   {
           40  +    for(int a=0; a<x; ++a) {
           41  +     int req = 1;
           42  +     if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
           43  +     if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
           44  +     if(fixed[y][a]) {
           45  +      if(fixed[y][a] < req)
           46  +       goto label_td_end;
           47  +      td[y][a] = fixed[y][a];
           48  +     } else {
           49  +      td[y][a] = req;
           50  +     }
           51  +    }
           52  +    for(int a=W-1; a>x; --a) {
           53  +     int req = 1;
           54  +     if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
           55  +     if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
           56  +     if(fixed[y][a]) {
           57  +      if(fixed[y][a] < req)
           58  +       goto label_td_end;
           59  +      td[y][a] = fixed[y][a];
           60  +     } else {
           61  +      td[y][a] = req;
           62  +     }
           63  +    }
           64  +    int a = x;
           65  +    {
           66  +     int req = 1;
           67  +     if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
           68  +     if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
           69  +     if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
           70  +     if(fixed[y][a]) {
           71  +      if(fixed[y][a] < req)
           72  +       goto label_td_end;
           73  +      td[y][a] = fixed[y][a];
           74  +     } else {
           75  +      td[y][a] = req;
           76  +     }
           77  +    }
           78  +    td_sum[y] = accumulate(td[y].begin(), td[y].end(), 0);
           79  +    td_end ++;
           80  +   }
           81  +  label_td_end:;
           82  +
           83  +   vector< vector<int> > bu(H, vector<int>(W));
           84  +   vector<int> bu_sum(H);
           85  +   int bu_begin = H;
           86  +   for(int y=H-1; y>=0; --y)
           87  +   {
           88  +    for(int a=0; a<x; ++a) {
           89  +     int req = 1;
           90  +     if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
           91  +     if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
           92  +     if(fixed[y][a]) {
           93  +      if(fixed[y][a] < req)
           94  +       goto label_bu_end;
           95  +      bu[y][a] = fixed[y][a];
           96  +     } else {
           97  +      bu[y][a] = req;
           98  +     }
           99  +    }
          100  +    for(int a=W-1; a>x; --a) {
          101  +     int req = 1;
          102  +     if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
          103  +     if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
          104  +     if(fixed[y][a]) {
          105  +      if(fixed[y][a] < req)
          106  +       goto label_bu_end;
          107  +      bu[y][a] = fixed[y][a];
          108  +     } else {
          109  +      bu[y][a] = req;
          110  +     }
          111  +    }
          112  +    int a = x;
          113  +    {
          114  +     int req = 1;
          115  +     if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
          116  +     if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
          117  +     if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
          118  +     if(fixed[y][a]) {
          119  +      if(fixed[y][a] < req)
          120  +       goto label_bu_end;
          121  +      bu[y][a] = fixed[y][a];
          122  +     } else {
          123  +      bu[y][a] = req;
          124  +     }
          125  +    }
          126  +    bu_sum[y] = accumulate(bu[y].begin(), bu[y].end(), 0);
          127  +    bu_begin --;
          128  +   }
          129  +  label_bu_end:;
          130  +
          131  +   if(td_end <= bu_begin)
          132  +    continue;
          133  +
          134  +   int baseline = 0;
          135  +   for(int Y=0; Y<H; ++Y)
          136  +    baseline += (Y<bu_begin ? td_sum[Y] : Y==bu_begin ? 0 : bu_sum[Y]);
          137  +
          138  +   for(int y=bu_begin; y<td_end; ++y)
          139  +   {
          140  +    int score = baseline;
          141  +    for(int x=0; x<W; ++x)
          142  +     score += max(td[y][x], bu[y][x]);
          143  +    best = min(best, score);
          144  +    if(y<H)
          145  +     baseline += td_sum[y] - bu_sum[y+1];
          146  +   }
          147  +  }
          148  +  return (best==INF ? -1 : best);
          149  + }
          150  +};
          151  +
          152  +// BEGIN CUT HERE
          153  +#include <ctime>
          154  +double start_time; string timer()
          155  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          156  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          157  + { os << "{ ";
          158  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          159  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          160  +void verify_case(const int& Expected, const int& Received) {
          161  + bool ok = (Expected == Received);
          162  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          163  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          164  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          165  +#define END  verify_case(_, TheMountain().minSum(n, m, rowIndex, columnIndex, element));}
          166  +int main(){
          167  +
          168  +CASE(0)
          169  + int n = 2;
          170  + int m = 3;
          171  + int rowIndex_[] = {0, 0, 0, 1, 1, 1};
          172  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          173  + int columnIndex_[] = {0, 1, 2, 0, 1, 2};
          174  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          175  + int element_[] = {4, 6, 9, 1, 3, 6};
          176  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          177  + int _ = 29;
          178  +END
          179  +CASE(1)
          180  + int n = 2;
          181  + int m = 3;
          182  + int rowIndex_[] = {1, 0, 1};
          183  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          184  + int columnIndex_[] = {2, 2, 0};
          185  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          186  + int element_[] = {5, 7, 6};
          187  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          188  + int _ = 40;
          189  +END
          190  +CASE(2)
          191  + int n = 3;
          192  + int m = 3;
          193  + int rowIndex_[] = {0, 0, 2, 2};
          194  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          195  + int columnIndex_[] = {0, 2, 2, 0};
          196  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          197  + int element_[] = {1, 1, 1, 1};
          198  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          199  + int _ = 15;
          200  +END
          201  +CASE(3)
          202  + int n = 2;
          203  + int m = 2;
          204  + int rowIndex_[] = {0, 0, 1, 1};
          205  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          206  + int columnIndex_[] = {0, 1, 1, 0};
          207  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          208  + int element_[] = {5, 8, 5, 8};
          209  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          210  + int _ = -1;
          211  +END
          212  +CASE(4)
          213  + int n = 1;
          214  + int m = 3;
          215  + int rowIndex_[] = {0};
          216  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          217  + int columnIndex_[] = {1};
          218  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          219  + int element_[] = {1};
          220  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          221  + int _ = -1;
          222  +END
          223  +CASE(5)
          224  + int n = 123;
          225  + int m = 45;
          226  + int rowIndex_[] = {2, 3, 5, 7, 11};
          227  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          228  + int columnIndex_[] = {13, 17, 19, 23, 29};
          229  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          230  + int element_[] = {100, 200, 300, 400, 500};
          231  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          232  + int _ = 367047;
          233  +END
          234  +CASE(6)
          235  + int n = 200;
          236  + int m = 200;
          237  + int rowIndex_[] = {5};
          238  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          239  + int columnIndex_[] = {8};
          240  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          241  + int element_[] = {666};
          242  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          243  + int _ = 5737554;
          244  +END
          245  +CASE(7)
          246  + int n = 10;
          247  + int m = 10;
          248  + int rowIndex_[] = {0, 8, 7};
          249  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          250  + int columnIndex_[] = {3, 1, 9};
          251  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          252  + int element_[] = {5, 4, 7};
          253  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          254  + int _ = 593;
          255  +END
          256  +CASE(8)
          257  + int n = 200;
          258  + int m = 200;
          259  + int rowIndex_[] = {129,99,142,33,111,174,169,176,83,143,70,116,193,139,7,35,111,4,189,111,170,29,16,87,115,4,60,71,37,138,128,38,61,176,187,66,64,84,120,104,124,129,91,137,114,187,97,115,151,140};
          260  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          261  + int columnIndex_[] = {191,148,194,13,90,17,185,163,17,170,193,165,140,158,85,15,56,91,9,68,153,83,9,97,74,40,160,165,49,151,173,98,123,44,139,164,66,112,141,172,91,147,71,167,123,53,189,86,71,171};
          262  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          263  + int element_[] = {953,216,307,197,970,590,659,153,79,262,628,153,106,904,888,249,224,839,29,327,664,619,387,325,865,849,516,313,649,135,713,585,347,279,702,837,682,817,844,981,401,410,982,891,167,102,646,73,784,455};
          264  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          265  + int _ = -1;
          266  +END
          267  +/*
          268  +CASE(9)
          269  + int n = ;
          270  + int m = ;
          271  + int rowIndex_[] = ;
          272  +   vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
          273  + int columnIndex_[] = ;
          274  +   vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
          275  + int element_[] = ;
          276  +   vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
          277  + int _ = ;
          278  +END
          279  +*/
          280  +}
          281  +// END CUT HERE

Added YNGraph.rb version [7857b17ad5edb6a7]

            1  +STDERR.print "Number of nodes? "
            2  +V = gets.to_i
            3  +
            4  +STDERR.print "Directed (u/d)? "
            5  +D = (gets.chomp.downcase=="d");
            6  +
            7  +ES = []
            8  +loop do
            9  + STDERR.print "Edge (u v)? "
           10  + edge = gets.split.map(&:to_i)
           11  + break if edge.size==0
           12  + ES << edge
           13  +end
           14  +
           15  +V.times do |y|
           16  + puts (0...V).map{|x|
           17  +  (D ? ES.index([y,x]) : ES.index([y,x]) || ES.index([x,y])) ? "Y" : "N"
           18  + }*""
           19  +end