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

Added SRM/509-U/1A.cpp version [712b40dbdb712dc9]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class LuckyRemainder { public:
           23  + int getLuckyRemainder(string X)
           24  + {
           25  +  int sum = 0;
           26  +  int N = X.size()-1;
           27  +  for(int i=0; i<X.size(); ++i)
           28  +  {
           29  +   int v = X[i]-'0';
           30  +   for(int i=0; i<N; ++i)
           31  +    v = (v*2)%9;
           32  +   sum = (sum+v)%9;
           33  +  }
           34  +  return sum;
           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 int& Expected, const int& 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(_, LuckyRemainder().getLuckyRemainder(X));}
           52  +int main(){
           53  +
           54  +CASE(0)
           55  + string X = "123";
           56  + int _ = 6;
           57  +END
           58  +CASE(1)
           59  + string X = "24816";
           60  + int _ = 3;
           61  +END
           62  +CASE(2)
           63  + string X = "8";
           64  + int _ = 8;
           65  +END
           66  +CASE(3)
           67  + string X = "11235813213455";
           68  + int _ = 7;
           69  +END
           70  +CASE(4)
           71  + string X = "1";
           72  + int _ = 1;
           73  +END
           74  +CASE(4)
           75  + string X = "4";
           76  + int _ = 4;
           77  +END
           78  +CASE(4)
           79  + string X = "9";
           80  + int _ = 0;
           81  +END
           82  +/*
           83  +CASE(5)
           84  + string X = ;
           85  + int _ = ;
           86  +END
           87  + */
           88  +}
           89  +// END CUT HERE

Added SRM/509-U/1B.cpp version [665b46c2c4b5b562]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class PalindromizationDiv1 { public:
           23  + static const int INF = 0x3fffffff;
           24  + static const int NOLETTER = 26;
           25  +
           26  + int getMinimumCost(string word, vector <string> operations)
           27  + {
           28  +  // Cost for changing a character to another
           29  +  int cost[27][27];
           30  +  for(int a=0; a<27; ++a)
           31  +   for(int b=0; b<27; ++b)
           32  +    cost[a][b] = (a==b ? 0 : INF);
           33  +
           34  +  for(size_t i=0; i<operations.size(); ++i)
           35  +  {
           36  +   stringstream cin(operations[i]);
           37  +   string cmd; cin >> cmd;
           38  +
           39  +   char a, b; int c;
           40  +   if( cmd == "add" )   { cin >> a >> c;      cost[NOLETTER][ a - 'a'] = c; }
           41  +   if( cmd == "erase" ) { cin >> a >> c;      cost[ a - 'a'][NOLETTER] = c; }
           42  +   if( cmd == "change" ){ cin >> a >> b >> c; cost[ a - 'a'][ b - 'a'] = c; }
           43  +  }
           44  +
           45  +  // Warshall-Floyd
           46  +  for(int k=0; k<27; ++k)
           47  +   for(int i=0; i<27; ++i)
           48  +    for(int j=0; j<27; ++j)
           49  +     cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
           50  +
           51  +  // Cost for matching two letters
           52  +  int match_cost[27][27];
           53  +  for(int i=0; i<27; ++i)
           54  +   for(int j=0; j<27; ++j)
           55  +   {
           56  +    match_cost[i][j] = INF;
           57  +    for(int k=0; k<27; ++k)
           58  +     match_cost[i][j] = min(match_cost[i][j], cost[i][k]+cost[j][k]);
           59  +   }
           60  +
           61  +  // Solve
           62  +  memo.clear();
           63  +  int r = rec(match_cost, word, 0, word.size()-1);
           64  +  return (r>=INF ? -1 : r);
           65  + }
           66  +
           67  + map<pair<int,int>,int> memo;
           68  + int rec(const int mc[27][27], const string& w, int s, int e)
           69  + {
           70  +  // Base case
           71  +  if( s >= e )
           72  +   return 0;
           73  +
           74  +  // Memoizaion
           75  +  const pair<int,int> key(s, e);
           76  +  if( memo.count(key) )
           77  +   return memo[key];
           78  +
           79  +  // take best
           80  +  int result = INF;
           81  +  result = min(result, rec(mc, w, s+1, e-1)+mc[w[s]-'a'][w[e]-'a']);
           82  +  result = min(result, rec(mc, w, s,   e-1)+mc[NOLETTER][w[e]-'a']);
           83  +  result = min(result, rec(mc, w, s+1, e  )+mc[w[s]-'a'][NOLETTER]);
           84  +  return memo[key] = result;
           85  + }
           86  +};
           87  +
           88  +// BEGIN CUT HERE
           89  +#include <ctime>
           90  +double start_time; string timer()
           91  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           92  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           93  + { os << "{ ";
           94  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           95  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           96  +void verify_case(const int& Expected, const int& Received) {
           97  + bool ok = (Expected == Received);
           98  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           99  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          100  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          101  +#define END  verify_case(_, PalindromizationDiv1().getMinimumCost(word, operations));}
          102  +int main(){
          103  +
          104  +CASE(0)
          105  + string word = "racecar";
          106  + vector <string> operations;
          107  + int _ = 0;
          108  +END
          109  +CASE(1)
          110  + string word = "topcoder";
          111  + string operations_[] = {"erase t 1", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"};
          112  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          113  + int _ = 5;
          114  +END
          115  +CASE(2)
          116  + string word = "topcoder";
          117  + string operations_[] = {"erase t 10", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"};
          118  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          119  + int _ = 7;
          120  +END
          121  +CASE(3)
          122  + string word = "caaaaaab";
          123  + string operations_[] = {"change b a 100000", "change c a 100000", "change c d 50000", "change b e 50000", "erase d 50000", "erase e 49999"};
          124  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          125  + int _ = 199999;
          126  +END
          127  +CASE(4)
          128  + string word = "moon";
          129  + string operations_[] = {"erase o 5", "add u 7", "change d p 3", "change m s 12", "change n d 6", "change s l 1"};
          130  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          131  + int _ = -1;
          132  +END
          133  +CASE(5)
          134  + string word = "a";
          135  +   vector <string> operations;
          136  + int _ = 0;
          137  +END
          138  +CASE(6) // killer!
          139  + string word = "az";
          140  + string operations_[] = {"add u 1", "change u b 100", "change a b 2"};
          141  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          142  + int _ = 103;
          143  +END
          144  +CASE(7) // killer!
          145  + string word = "az";
          146  + string operations_[] = {"add b 1", "change a b 1"};
          147  +   vector <string> operations(operations_, operations_+sizeof(operations_)/sizeof(*operations_));
          148  + int _ = 2;
          149  +END
          150  +}
          151  +// END CUT HERE