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

Added SRM/523/1A.cpp version [e904c748ecdc6b47]

            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 CountingSeries { public:
           23  + long long countThem(long long a, long long b, long long c, long long d, long long upperBound)
           24  + {
           25  +  LL cnt = a<=upperBound ? (upperBound-a)/b+1 : 0;
           26  +  for(; c<=upperBound; c*=d) {
           27  +   if( !in_arith(a, b, c) )
           28  +    ++cnt;
           29  +   if( d == 1 )
           30  +    break;
           31  +  }
           32  +  return cnt;
           33  + }
           34  +
           35  + bool in_arith(LL a, LL b, LL v) const
           36  + {
           37  +  return v-a>=0 && (v-a)%b==0;
           38  + }
           39  +};
           40  +
           41  +// BEGIN CUT HERE
           42  +#include <ctime>
           43  +double start_time; string timer()
           44  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           45  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           46  + { os << "{ ";
           47  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           48  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           49  +void verify_case(const long long& Expected, const long long& Received) {
           50  + bool ok = (Expected == Received);
           51  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           52  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           53  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           54  +#define END  verify_case(_, CountingSeries().countThem(a, b, c, d, upperBound));}
           55  +int main(){
           56  +
           57  +CASE(0)
           58  + long long a = 1LL;
           59  + long long b = 1LL;
           60  + long long c = 1LL;
           61  + long long d = 2LL;
           62  + long long upperBound = 1000LL;
           63  + long long _ = 1000LL;
           64  +END
           65  +CASE(1)
           66  + long long a = 3LL;
           67  + long long b = 3LL;
           68  + long long c = 1LL;
           69  + long long d = 2LL;
           70  + long long upperBound = 1000LL;
           71  + long long _ = 343LL;
           72  +END
           73  +CASE(2)
           74  + long long a = 40LL;
           75  + long long b = 77LL;
           76  + long long c = 40LL;
           77  + long long d = 100000LL;
           78  + long long upperBound = 40LL;
           79  + long long _ = 1LL;
           80  +END
           81  +CASE(3)
           82  + long long a = 452LL;
           83  + long long b = 24LL;
           84  + long long c = 4LL;
           85  + long long d = 5LL;
           86  + long long upperBound = 600LL;
           87  + long long _ = 10LL;
           88  +END
           89  +CASE(4)
           90  + long long a = 234LL;
           91  + long long b = 24LL;
           92  + long long c = 377LL;
           93  + long long d = 1LL;
           94  + long long upperBound = 10000LL;
           95  + long long _ = 408LL;
           96  +END
           97  +CASE(5)
           98  + long long a = 8LL;
           99  + long long b = 8LL;
          100  + long long c = 2LL;
          101  + long long d = 2LL;
          102  + long long upperBound = 80LL;
          103  + long long _ = 12LL;
          104  +END
          105  +CASE(6)
          106  + long long a = 1LL;
          107  + long long b = 12345LL;
          108  + long long c = 1LL;
          109  + long long d = 100000LL;
          110  + long long upperBound = 1000000000000LL;
          111  + long long _ = -1LL;
          112  +END
          113  +}
          114  +// END CUT HERE

Added SRM/523/1B.cpp version [2ad7ecc836973d8a]

            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  +static const int MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {} // x>=0
           28  + mint(size_t x):val(x%MODVAL) {} // x>=0
           29  + mint(LL     x):val(x%MODVAL) {} // x>=0
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           33  +mint operator+(mint x, mint y) { return x+=y; }
           34  +mint operator*(mint x, mint y) { return x*=y; }
           35  +
           36  +class BricksN { public:
           37  + int countStructures(int w, int h, int k)
           38  + {
           39  +  memo1.clear();
           40  +  memo2.clear();
           41  +  return rec(w, h, k).val;
           42  + }
           43  +
           44  + map<int,mint> memo1;
           45  + mint rec(int w, int h, int k)
           46  + {
           47  +  if( h == 0 ) return 1;
           48  +  if( w <= 0 ) return 1;
           49  +
           50  +  const int key = w*51+h;
           51  +  if( memo1.count(key) )
           52  +   return memo1[key];
           53  +
           54  +  mint sum = 1;
           55  +  for(int s=0; s<w; ++s)
           56  +   for(int ww=1; s+ww<=w; ++ww)
           57  +    sum += full(ww, k) * rec(ww, h-1, k) * rec(w-(s+ww+1), h, k);
           58  +  return memo1[key] = sum;
           59  + }
           60  +
           61  + map<int,mint> memo2;
           62  + mint full(int w, int k)
           63  + {
           64  +  if( w <= 0 ) return 1;
           65  +
           66  +  const int key = w;
           67  +  if( memo2.count(key) )
           68  +   return memo2[key];
           69  +
           70  +  mint sum = 0;
           71  +  for(int ww=1; ww<=min(w,k); ++ww)
           72  +   sum += full(w-ww, k);
           73  +  return memo2[key] = sum;
           74  + }
           75  +};
           76  +
           77  +// BEGIN CUT HERE
           78  +#include <ctime>
           79  +double start_time; string timer()
           80  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           81  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           82  + { os << "{ ";
           83  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           84  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           85  +void verify_case(const int& Expected, const int& Received) {
           86  + bool ok = (Expected == Received);
           87  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           88  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           89  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           90  +#define END  verify_case(_, BricksN().countStructures(w, h, k));}
           91  +int main(){
           92  +
           93  +CASE(0)
           94  + int w = 3;
           95  + int h = 1;
           96  + int k = 3;
           97  + int _ = 13;
           98  +END
           99  +CASE(1)
          100  + int w = 3;
          101  + int h = 2;
          102  + int k = 3;
          103  + int _ = 83;
          104  +END
          105  +CASE(2)
          106  + int w = 1;
          107  + int h = 5;
          108  + int k = 1;
          109  + int _ = 6;
          110  +END
          111  +CASE(3)
          112  + int w = 10;
          113  + int h = 10;
          114  + int k = 3;
          115  + int _ = 288535435;
          116  +END
          117  +CASE(4)
          118  + int w = 50;
          119  + int h = 50;
          120  + int k = 50;
          121  + int _ = -1;
          122  +END
          123  +CASE(5)
          124  + int w = 1;
          125  + int h = 1;
          126  + int k = 1;
          127  + int _ = 1;
          128  +END
          129  +
          130  +}
          131  +// END CUT HERE

Added SRM/523/1C.cpp version [ac1374745693c058]

            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  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class AlphabetPaths { public:
           29  + int H, W;
           30  + long long count(vector <string> maze)
           31  + {
           32  +  H = maze.size();
           33  +  W = maze[0].size();
           34  +  for(int y=0; y<H; ++y)
           35  +  for(int x=0; x<W; ++x)
           36  +   if( maze[y][x] != '.' )
           37  +    maze[y][x] = char(string("ABCDEFZHIKLMNOPQRSTVX").find(maze[y][x]));
           38  +
           39  +  LL total = 0;
           40  +  for(int y=0; y<H; ++y)
           41  +  for(int x=0; x<W; ++x)
           42  +   if( maze[y][x] != '.' ) {
           43  +    int mid = maze[y][x];
           44  +
           45  +    unordered_map<int, int> reachable;
           46  +    travel(1, 1<<mid, y, x, maze, reachable);
           47  +
           48  +    for(unordered_map<int,int>::iterator it=reachable.begin(); it!=reachable.end(); ++it)
           49  +    {
           50  +     unordered_map<int,int>::iterator kt = reachable.find((((1<<21)-1)^it->first) | (1<<mid));
           51  +     if( kt != reachable.end() )
           52  +      total += LL(it->second) * kt->second;
           53  +    }
           54  +   }
           55  +  return total;
           56  + }
           57  +
           58  + void travel(int n, int mask, int y, int x, const vector<string>& maze,
           59  +             unordered_map<int,int>& reachable)
           60  + {
           61  +  if( n == 11 ) {
           62  +   reachable[mask]++;
           63  +   return;
           64  +  }
           65  +
           66  +  static const int dy[] = {-1,+1,0,0};
           67  +  static const int dx[] = {0,0,-1,+1};
           68  +  for(int i=0; i<4; ++i) {
           69  +   int yy = y+dy[i];
           70  +   int xx = x+dx[i];
           71  +   if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='.' ) {
           72  +    int v = maze[yy][xx];
           73  +    if( !(mask & (1<<v)) )
           74  +     travel(n+1, mask|(1<<v), yy, xx, maze, reachable);
           75  +   }
           76  +  }
           77  + }
           78  +};
           79  +
           80  +// BEGIN CUT HERE
           81  +#include <ctime>
           82  +double start_time; string timer()
           83  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           84  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           85  + { os << "{ ";
           86  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           87  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           88  +void verify_case(const long long& Expected, const long long& Received) {
           89  + bool ok = (Expected == Received);
           90  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           91  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           92  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           93  +#define END  verify_case(_, AlphabetPaths().count(maze));}
           94  +int main(){
           95  +
           96  +CASE(0)
           97  + string maze_[] = {"ABCDEFZHIXKLMNOPQRST",
           98  + "...................V"};
           99  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          100  + long long _ = 2LL;
          101  +END
          102  +CASE(1)
          103  + string maze_[] = {".................VT.",
          104  + "....................",
          105  + "ABCDEFZHIXKLMNOPQRS.",
          106  + "..................S.",
          107  + ".................VT."};
          108  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          109  + long long _ = 0LL;
          110  +END
          111  +CASE(2)
          112  + string maze_[] = {"TBCDE.PQRSA",
          113  + "FZHIXKLMNOV"};
          114  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          115  + long long _ = 50LL;
          116  +END
          117  +CASE(3)
          118  + string maze_[] = {"ABCDEF.",
          119  + "V....Z.",
          120  + "T....H.",
          121  + "S....I.",
          122  + "R....X.",
          123  + "KLMNOPQ"};
          124  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          125  + long long _ = 4LL;
          126  +END
          127  +CASE(4)
          128  + string maze_[] = {
          129  +  "ABCDEFZHIXKLMNOPQRSTV",
          130  +  "HIXKLMNOPQRSTVABCDEFZ",
          131  +  "OPQRSTVABCDEFZHIXKLMN",
          132  +  "ABCDEFZHIXKLMNOPQRSTV",
          133  +  "HIXKLMNOPQRSTVABCDEFZ",
          134  +  "OPQRSTVABCDEFZHIXKLMN",
          135  +  "ABCDEFZHIXKLMNOPQRSTV",
          136  +  "HIXKLMNOPQRSTVABCDEFZ",
          137  +  "OPQRSTVABCDEFZHIXKLMN",
          138  +  "ABCDEFZHIXKLMNOPQRSTV",
          139  +  "HIXKLMNOPQRSTVABCDEFZ",
          140  +  "OPQRSTVABCDEFZHIXKLMN",
          141  +  "ABCDEFZHIXKLMNOPQRSTV",
          142  +  "HIXKLMNOPQRSTVABCDEFZ",
          143  +  "OPQRSTVABCDEFZHIXKLMN",
          144  +  "ABCDEFZHIXKLMNOPQRSTV",
          145  +  "HIXKLMNOPQRSTVABCDEFZ",
          146  +  "OPQRSTVABCDEFZHIXKLMN",
          147  +  "ABCDEFZHIXKLMNOPQRSTV",
          148  +  "HIXKLMNOPQRSTVABCDEFZ",
          149  +  "OPQRSTVABCDEFZHIXKLMN",
          150  + };
          151  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          152  + long long _ = 6119782LL;
          153  +END
          154  +CASE(5)
          155  + string maze_[] = {"ABCDEFZHIKLMNOPQRSTVX", "FZHIKLMNOPQRSTVXABCDE", "LMNOPQRSTVXABCDEFZHIK", "QRSTVXABCDEFZHIKLMNOP", "XABCDEFZHIKLMNOPQRSTV", "EFZHIKLMNOPQRSTVXABCD", "KLMNOPQRSTVXABCDEFZHI", "PQRSTVXABCDEFZHIKLMNO", "VXABCDEFZHIKLMNOPQRST", "DEFZHIKLMNOPQRSTVXABC", "IKLMNOPQRSTVXABCDEFZH", "OPQRSTVXABCDEFZHIKLMN", "TVXABCDEFZHIKLMNOPQRS", "CDEFZHIKLMNOPQRSTVXAB", "HIKLMNOPQRSTVXABCDEFZ", "NOPQRSTVXABCDEFZHIKLM", "STVXABCDEFZHIKLMNOPQR", "BCDEFZHIKLMNOPQRSTVXA", "ZHIKLMNOPQRSTVXABCDEF", "MNOPQRSTVXABCDEFZHIKL", "RSTVXABCDEFZHIKLMNOPQ"};
          156  +   vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
          157  + long long _ = 10530238LL;
          158  +END
          159  +}
          160  +// END CUT HERE

Modified TZTesterSp/template.cpp from [0155d37d08046666] to [56e8b77f261a915b].

    11     11   #include <functional>
    12     12   #include <complex>
    13     13   #include <queue>
    14     14   #include <stack>
    15     15   #include <cmath>
    16     16   #include <cassert>
    17     17   #include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
    18     24   using namespace std;
    19     25   typedef long long LL;
    20     26   typedef complex<double> CMP;
    21     27   
    22     28   class $CLASSNAME$ { public:
    23     29    $RC$ $METHODNAME$($METHODPARMS$)
    24     30    {
    25     31    }
    26     32   };
    27     33   
    28     34   $TESTCODE$