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

Added SRM/604-U/1A.cpp version [b81d85fd8b288dc7]

            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 PowerOfThree { public:
           23  + string ableToGet(int x_, int y_)
           24  + {
           25  +  LL x=x_, y=y_;
           26  +  for(LL tk=1;; tk*=3)
           27  +  {
           28  +   if(x==0 && y==0)
           29  +    break;
           30  +   LL xr = ((x/tk)%3+3)%3;
           31  +   LL yr = ((y/tk)%3+3)%3;
           32  +   if(xr==1 && yr==0) x-=tk;
           33  +   else if(xr==2 && yr==0) x+=tk;
           34  +   else if(xr==0 && yr==1) y-=tk;
           35  +   else if(xr==0 && yr==2) y+=tk;
           36  +   else return "Impossible";
           37  +  }
           38  +  return "Possible";
           39  + }
           40  +};
           41  +
           42  +// BEGIN CUT HERE
           43  +#include <ctime>
           44  +double start_time; string timer()
           45  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           46  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           47  + { os << "{ ";
           48  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           49  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           50  +void verify_case(const string& Expected, const string& Received) {
           51  + bool ok = (Expected == Received);
           52  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           53  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           54  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           55  +#define END  verify_case(_, PowerOfThree().ableToGet(x, y));}
           56  +int main(){
           57  +
           58  +CASE(0)
           59  + int x = 1;
           60  + int y = 3;
           61  + string _ = "Possible";
           62  +END
           63  +CASE(1)
           64  + int x = 0;
           65  + int y = 2;
           66  + string _ = "Possible";
           67  +END
           68  +CASE(2)
           69  + int x = 1;
           70  + int y = 9;
           71  + string _ = "Impossible";
           72  +END
           73  +CASE(3)
           74  + int x = 3;
           75  + int y = 0;
           76  + string _ = "Impossible";
           77  +END
           78  +CASE(4)
           79  + int x = 1;
           80  + int y = 1;
           81  + string _ = "Impossible";
           82  +END
           83  +CASE(5)
           84  + int x = -6890;
           85  + int y = 18252;
           86  + string _ = "Possible";
           87  +END
           88  +CASE(6)
           89  + int x = 1000000000;
           90  + int y = -1000000000;
           91  + string _ = "Impossible";
           92  +END
           93  +CASE(7)
           94  + int x = 0;
           95  + int y = 0;
           96  + string _ = "Possible";
           97  +END
           98  +CASE(8)
           99  + int x = 8;
          100  + int y = 3;
          101  + string _ = "P";
          102  +END
          103  +CASE(9)
          104  + // -3^0 - 3^1 - ... - 3^18 + 3^19
          105  + // NOTE: 3^19 = 1162261467 > 10^9
          106  + int x = 581130734;
          107  + int y = 0;
          108  + string _ = "P";
          109  +END
          110  +}
          111  +// END CUT HERE

Added SRM/604-U/1B-U.cpp version [72fa1058f372c23c]

            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  +template<typename T>
           23  +struct DP2
           24  +{
           25  + const int N1, N2;
           26  + vector<T> data;
           27  + DP2(int N1, int N2, const T& t = T())
           28  +  : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<28)); }
           29  + T& operator()(int i1, int i2)
           30  +  { return data[ (i1*N2)+i2 ]; }
           31  + void swap(DP2& rhs)
           32  +  { data.swap(rhs.data); }
           33  +};
           34  +
           35  +static const int INF = 0x3fffffff;
           36  +class FoxConnection { public:
           37  + int minimalDistance(vector <int> A, vector <int> B, string haveFox)
           38  + {
           39  +  int N = haveFox.size();
           40  +  vector<vector<int>> G(N);
           41  +  for(int i=0; i<A.size(); ++i) {
           42  +   int a = A[i] - 1;
           43  +   int b = B[i] - 1;
           44  +   G[a].push_back(b);
           45  +   G[b].push_back(a);
           46  +  }
           47  +
           48  +  int best = INF;
           49  +  memo.resize(N+1, vector<vector<int>>(N));
           50  +  ts_memo.resize(N+1, vector<int>(N, INF));
           51  +  for(int root=0; root<N; ++root) {
           52  +   const vector<int>& L = rec(-1, root, G, haveFox);
           53  +   best = min(best, L[0]);
           54  +  }
           55  +  return best==INF ? 0 : best;
           56  + }
           57  +
           58  + vector<vector<int>> ts_memo;
           59  + int treeSize(int prev, int v, const vector<vector<int>>& G, const string& haveFox)
           60  + {
           61  +  if(ts_memo[prev+1][v] != INF)
           62  +   return ts_memo[prev+1][v];
           63  +
           64  +  int ts = (haveFox[v]=='Y');
           65  +  for(int u : G[v]) if(u != prev)
           66  +   ts += treeSize(v, u, G, haveFox);
           67  +  return ts_memo[prev+1][v] = ts;
           68  + }
           69  +
           70  + vector<vector<vector<int>>> memo;
           71  + const vector<int>& rec(int prev, int v, const vector<vector<int>>& G, const string& haveFox)
           72  + {
           73  +  if(!memo[prev+1][v].empty())
           74  +   return memo[prev+1][v];
           75  +  int N = G.size();
           76  +
           77  +  vector<const vector<int>*> children;
           78  +  for(int u : G[v]) if(u != prev)
           79  +   children.push_back(&rec(v,u,G,haveFox));
           80  +  int Z = children.size();
           81  +
           82  +  DP2<int> dp(Z+1, N, INF);
           83  +  dp(0,0) = 0;
           84  +  for(int i=0; i<Z; ++i)
           85  +  {
           86  +   const vector<int>& ch = *children[i];
           87  +   for(int t=0; t<N; ++t)
           88  +   for(int w=0; w<N; ++w)
           89  +    if(t+w<N)
           90  +     dp(i+1, t+w) = min(dp(i+1, t+w), dp(i,t)+ch[w]);
           91  +  }
           92  +
           93  +  const bool Y = (haveFox[v]=='Y');
           94  +  vector<int>& L = memo[prev+1][v];
           95  +  L.resize(N, INF);
           96  +
           97  +  const int TS = treeSize(prev, v, G, haveFox);
           98  +  for(int i=0; i<N; ++i)
           99  +  {
          100  +   if(i == TS)
          101  +    L[i] = min(INF, TS + (Y ? dp(Z,TS-1) : dp(Z,TS)));
          102  +   else
          103  +    L[i] = min(INF, i + (Y ? dp(Z,i) : i+1<N ? dp(Z,i+1) : INF));
          104  +  }
          105  +  return L;
          106  + }
          107  +};
          108  +
          109  +// BEGIN CUT HERE
          110  +#include <ctime>
          111  +double start_time; string timer()
          112  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          113  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          114  + { os << "{ ";
          115  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          116  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          117  +void verify_case(const int& Expected, const int& Received) {
          118  + bool ok = (Expected == Received);
          119  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          120  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          121  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          122  +#define END  verify_case(_, FoxConnection().minimalDistance(A, B, haveFox));}
          123  +int main(){
          124  +
          125  +CASE(0)
          126  + int A_[] = {1,2,3};
          127  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          128  + int B_[] = {2,3,4};
          129  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          130  + string haveFox = "YNNY";
          131  + int _ = 2;
          132  +END
          133  +CASE(1)
          134  + int A_[] = {1,1,1,1};
          135  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          136  + int B_[] = {2,3,4,5};
          137  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          138  + string haveFox = "NYYYY";
          139  + int _ = 1;
          140  +END
          141  +CASE(2)
          142  + int A_[] = {1,3,4,5,4};
          143  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          144  + int B_[] = {2,2,2,4,6};
          145  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          146  + string haveFox = "YNYNYY";
          147  + int _ = 2;
          148  +END
          149  +CASE(3)
          150  + int A_[] = {1,2,3,4,5,6,7,8,9};
          151  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          152  + int B_[] = {2,3,4,5,6,7,8,9,10};
          153  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          154  + string haveFox = "YNNNYNYNNY";
          155  + int _ = 7;
          156  +END
          157  +CASE(4)
          158  + int A_[] = {1,2,3,4,3,6,8,7};
          159  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          160  + int B_[] = {2,3,4,5,6,8,9,6};
          161  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          162  + string haveFox = "YNNYYNYYY";
          163  + int _ = 3;
          164  +END
          165  +CASE(5)
          166  + int A_[] = {1};
          167  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          168  + int B_[] = {2};
          169  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          170  + string haveFox = "NY";
          171  + int _ = 0;
          172  +END
          173  +CASE(6)
          174  + int A_[] = {1};
          175  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          176  + int B_[] = {2};
          177  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          178  + string haveFox = "NN";
          179  + int _ = 0;
          180  +END
          181  +/*
          182  +CASE(7)
          183  + int A_[] = ;
          184  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          185  + int B_[] = ;
          186  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          187  + string haveFox = ;
          188  + int _ = ;
          189  +END
          190  +CASE(8)
          191  + int A_[] = ;
          192  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          193  + int B_[] = ;
          194  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          195  + string haveFox = ;
          196  + int _ = ;
          197  +END
          198  +*/
          199  +}
          200  +// END CUT HERE