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

Added SRM/TCO20-2B-U/1A.cpp version [07e1c3e6145a787c]

            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 FixedNumberOfDigits { public:
           23  + long long sum(int start, int step, long long numberOfDigits)
           24  + {
           25  +  return solve(start, step, numberOfDigits);
           26  + }
           27  +
           28  + LL solve(LL s, LL inc, LL nd) {
           29  +  LL next = 10;
           30  +  int w = 1;
           31  +  while (next <= s) {
           32  +   next *= 10;
           33  +   w += 1;
           34  +  }
           35  +  next = (next - s + inc - 1) / inc * inc + s;
           36  +  LL k = (next - s) / inc;
           37  +  if (k * w >= nd) {
           38  +   LL q = nd / w;
           39  +   LL r = nd % w;
           40  +   if (r == 0) q -= 1, r += w;
           41  +
           42  +   stringstream ss;
           43  +   ss << (s + inc*q);
           44  +   stringstream ss2;
           45  +   ss2 << ss.str().substr(0, int(r));
           46  +   LL ans;
           47  +   ss2 >> ans;
           48  +   return ans;
           49  +  }
           50  +  return solve(next, inc, nd - k*w);
           51  + }
           52  +};
           53  +
           54  +// BEGIN CUT HERE
           55  +#include <ctime>
           56  +double start_time; string timer()
           57  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           58  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           59  + { os << "{ ";
           60  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           61  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           62  +void verify_case(const long long& Expected, const long long& Received) {
           63  + bool ok = (Expected == Received);
           64  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           65  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           66  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           67  +#define END  verify_case(_, FixedNumberOfDigits().sum(start, step, numberOfDigits));}
           68  +int main(){
           69  +
           70  +CASE(0)
           71  + int start = 47;
           72  + int step = 10;
           73  + long long numberOfDigits = 7LL;
           74  + long long _ = 7LL;
           75  +END
           76  +CASE(1)
           77  + int start = 98;
           78  + int step = 1;
           79  + long long numberOfDigits = 10LL;
           80  + long long _ = 101LL;
           81  +END
           82  +CASE(2)
           83  + int start = 0;
           84  + int step = 1;
           85  + long long numberOfDigits = 7LL;
           86  + long long _ = 6LL;
           87  +END
           88  +CASE(3)
           89  + int start = 123456789;
           90  + int step = 10;
           91  + long long numberOfDigits = 5LL;
           92  + long long _ = 12345LL;
           93  +END
           94  +CASE(4)
           95  + int start = 123456789;
           96  + int step = 10;
           97  + long long numberOfDigits = 17LL;
           98  + long long _ = 12345679LL;
           99  +END
          100  +CASE(5)
          101  + int start = 0;
          102  + int step = 1;
          103  + long long numberOfDigits = 15LL;
          104  + long long _ = 1LL;
          105  +END
          106  +CASE(6)
          107  +int start = 314;
          108  +int step = 11;
          109  +long long numberOfDigits = 9LL;
          110  +long long _ = 336LL;
          111  +END
          112  +CASE(6)
          113  +int start = 314;
          114  +int step = 11;
          115  +long long numberOfDigits = 192LL;
          116  +long long _ = 100LL;
          117  +END
          118  +CASE(6)
          119  +int start = 1;
          120  +int step = 612;
          121  +long long numberOfDigits = 10LL;
          122  +long long _ = 18LL;
          123  +END
          124  +}
          125  +// END CUT HERE

Added SRM/TCO20-2B-U/1B-U.cpp version [b05daf554eb1a2c2]

            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 RoomPairs { public:
           23  + vector <string> fix(vector<string> s) {
           24  +  for (size_t y = 1; y < s.size(); y += 2)
           25  +   s[y][0] = s[y][s[y].size() - 1] = '|';
           26  +  for (size_t x = 1; x < s[0].size(); x += 2)
           27  +   s[0][x] = s[s.size()-1][x] = '-';
           28  +
           29  +  for (size_t y = 0; y<s.size(); y += 2)
           30  +   for (size_t x = 0; x < s[y].size(); x += 2) {
           31  +    int dx[] = { -1, +1, 0, 0 };
           32  +    int dy[] = { 0, 0, -1, +1 };
           33  +    char c = ' ';
           34  +    for (int d = 0; d < 4; ++d) {
           35  +     int yy = y + dy[d];
           36  +     int xx = x + dx[d];
           37  +     if (0 <= yy && yy < s.size() && 0 <= xx && xx < s[0].size() && s[yy][xx] != ' ')
           38  +      c = '+';
           39  +    }
           40  +    s[y][x] = c;
           41  +   }
           42  +  return s;
           43  + }
           44  + vector <string> construct(int R, int C, int N)
           45  + {
           46  +  return fix(solve(R, C, N));
           47  + }
           48  +
           49  + vector<string> solve(int R, int C, int N)
           50  + {
           51  +  vector<string> ans(R * 2 + 1, string(C * 2 + 1, ' '));
           52  +  if (N < C) {
           53  +   for (int r=1; r < ans.size(); r+=2) {
           54  +    for (int c = 0; c < N; ++c)
           55  +     ans[r][c*2+2] = '|';
           56  +   }
           57  +   return ans;
           58  +  }
           59  +
           60  +  for (int r = 2; r <= R; ++r)
           61  +   if((r-1)*C+r*(C-1) >= N)
           62  +   {
           63  +    int cnt = (r - 2)*C + (r - 1)*(C - 1);
           64  +
           65  +    vector<bool> h(C-1, true);
           66  +    vector<bool> v(C, false);
           67  +    for(; cnt<N; ++cnt) {
           68  +     if (h[0] == false)
           69  +      h[0] = true;
           70  +     else {
           71  +      int r = v.size() - 1;
           72  +      for (; r >= 0; --r)
           73  +       if (v[r] == false)
           74  +        break;
           75  +      if (r > 1) {
           76  +       v[r] = true;
           77  +       h[0] = false;
           78  +      }
           79  +      else {
           80  +       //..
           81  +      }
           82  +     }
           83  +    }
           84  +
           85  +    for (int x = 0; x < h.size(); ++x) {
           86  +     for (int y = 0; y < R; ++y)
           87  +      if(y<r-1)
           88  +       ans[1 + y * 2][2 + x * 2] = '|';
           89  +      else
           90  +       ans[1 + y * 2][2 + x * 2] = (h[x] ? '|' : ' ');
           91  +    }
           92  +    for (int x = 0; x < v.size(); ++x)
           93  +     for (int y=0; y < R; ++y)
           94  +      if(y < r)
           95  +       ans[2 + y * 2][1 + x * 2] = '-';
           96  +      else if(y==r)
           97  +       ans[2 + y * 2][1 + x * 2] = (v[x] ? '-' : ' ');
           98  +
           99  +    return ans;
          100  +   }
          101  + }
          102  +};
          103  +
          104  +// BEGIN CUT HERE
          105  +#include <ctime>
          106  +double start_time; string timer()
          107  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          108  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          109  + { os << "{ \n";
          110  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          111  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : "\n"); os << " }"; return os; }
          112  +void verify_case(const vector <string>& Expected, const vector <string>& Received) {
          113  + bool ok = (Expected == Received);
          114  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          115  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          116  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          117  +#define END  verify_case(_, RoomPairs().construct(R, C, N));}
          118  +int main(){
          119  +
          120  +CASE(0)
          121  + int R = 2;
          122  + int C = 4;
          123  + int N = 1;
          124  + string __[] = {"+-+-+-+-+", "| |   | |", "+ + +-+ +", "|   |   |", "+-+-+-+-+" };
          125  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          126  +END
          127  +CASE(1)
          128  + int R = 3;
          129  + int C = 3;
          130  + int N = 4;
          131  + string __[] = {"+-+-+-+", "| | | |", "+-+ +-+", "|     |", "+-+ +-+", "| | | |", "+-+-+-+" };
          132  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          133  +END
          134  +CASE(2)
          135  + int R = 3;
          136  + int C = 4;
          137  + int N = 3;
          138  + string __[] = {"+-+-+-+-+", "|       |", "+ +-+-+ +", "| | | | |", "+ +-+-+ +", "|       |", "+-+-+-+-+" };
          139  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          140  +END
          141  +CASE(3)
          142  + int R = 4;
          143  + int C = 5;
          144  + int N = 31;
          145  + string __[] = {"+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+" };
          146  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          147  +END
          148  +CASE(4)
          149  + int R = 1;
          150  + int C = 10;
          151  + int N = 4;
          152  + string __[] = { "!!" };
          153  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          154  +END
          155  +/*
          156  +CASE(5)
          157  + int R = ;
          158  + int C = ;
          159  + int N = ;
          160  + string __[] = { "!!" };
          161  + vector <string> _(__, __+sizeof(__)/sizeof(*__));
          162  +END
          163  +*/
          164  +}
          165  +// END CUT HERE