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

Added SRM/TCO15-2D-U/1A.cpp version [fd2a8960b68fd451]

            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 BalancedSubstrings { public:
           23  + int countSubstrings(string s)
           24  + {
           25  +  const int N = s.size();
           26  +
           27  +  int numAllZeroRange = 0;
           28  +  for(int i=0; i<N; ++i)
           29  +   for(int k=i; k<N && s[k]=='0'; ++k)
           30  +    ++numAllZeroRange;
           31  +
           32  +  vector<int> leftZero(N), rightZero(N);
           33  +  for(int i=1; i<N; ++i)
           34  +   leftZero[i] = (s[i-1]=='0' ? leftZero[i-1]+1 : 0);
           35  +  for(int i=N-2; i>=0; --i)
           36  +   rightZero[i] = (s[i+1]=='0' ? rightZero[i+1]+1 : 0);
           37  +
           38  +  set<pair<int,int>> OneOneRange;
           39  +  for(int c=0; c<N; ++c) {
           40  +   // take c as the center.
           41  +   // enumerate all balanced [L, R].
           42  +   int L=c, R=c, Lw=0, Rw=0;
           43  +   if(s[L]=='1')
           44  +    OneOneRange.emplace(L,R);
           45  +   while(0<=L && R<N) {
           46  +    const bool moveL = (Lw<Rw || Lw==Rw);
           47  +    const bool moveR = (Lw>Rw || Lw==Rw);
           48  +
           49  +    if(moveL)
           50  +     while(--L>=0)
           51  +      if(s[L]=='1') {
           52  +       Lw += (c-L);
           53  +       break;
           54  +      }
           55  +    if(moveR)
           56  +     while(++R<N)
           57  +      if(s[R]=='1') {
           58  +       Rw += (R-c);
           59  +       break;
           60  +      }
           61  +    if(0<=L && R<N && Lw==Rw)
           62  +     OneOneRange.emplace(L, R);
           63  +   }
           64  +  }
           65  +  int numOtherRange = 0;
           66  +  for(auto lr: OneOneRange) {
           67  +   int L = lr.first, R = lr.second;
           68  +   numOtherRange += (leftZero[L]+1) * (rightZero[R]+1);
           69  +  }
           70  +  return numAllZeroRange + numOtherRange;
           71  + }
           72  +};
           73  +
           74  +// BEGIN CUT HERE
           75  +#include <ctime>
           76  +double start_time; string timer()
           77  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           78  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           79  + { os << "{ ";
           80  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           81  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           82  +void verify_case(const int& Expected, const int& Received) {
           83  + bool ok = (Expected == Received);
           84  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           85  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           86  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           87  +#define END  verify_case(_, BalancedSubstrings().countSubstrings(s));}
           88  +int main(){
           89  +
           90  +CASE(0)
           91  + string s = "011";
           92  + int _ = 4;
           93  +END
           94  +CASE(1)
           95  + string s = "10111";
           96  + int _ = 10;
           97  +END
           98  +CASE(2)
           99  + string s = "00000";
          100  + int _ = 15;
          101  +END
          102  +CASE(3)
          103  + string s = "0000001000000";
          104  + int _ = 91;
          105  +END
          106  +CASE(4)
          107  + string s = "100110001001";
          108  + int _ = 49;
          109  +END
          110  +CASE(5)
          111  + string s = "0";
          112  + int _ = 1;
          113  +END
          114  +CASE(5)
          115  + string s = "1";
          116  + int _ = 1;
          117  +END
          118  +CASE(5)
          119  + string s = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
          120  + int _ = 1563750;
          121  +END
          122  +CASE(5)
          123  + string s = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
          124  + int _ = 3126250;
          125  +END
          126  +CASE(5)
          127  + string s = "1000111010010001011011011010000101101001011001001010101001010100101011011101011111101011011111110001001110010101111010101000001011100011100110101011010001010010110001000111000010110101111101100001000010100010000000101101010011100000000010100010011000101010100100111101001000000000001111011001011101010000011000000110011111011110100101011011111101001111000101011000101110101001001000001101100101000110100111000110100000000011001110110110011011110101101010111010011011101101111110010110101100001101111111101010000010001001001001110111001101110000111001110101111000110011010101010111100001001111110010101010100000010011111010100001101100111111010110010110011010101110110100001100000111000011100100000110111101110010101011101101101100001100111111110011100101101111000011010001000111011001100010100110001010101011101110100100101001000000010000001000001111001110111101110011000111010010101110000111101011010000011000101111011000101110101000011000110010011011001000001001111100110001011110010101000000001110010111100101101111100000001110000011100101001000100011101100011010010100011101111100001010111101000110010111000110101000101100001101111111011000111001110010011010011111100101000000010101110100100101100010001000101001110100001111010100011110000010001011100000100110010111000111110010101110000000110010000111001000010010111011111110110100000101011110000100110101111000111010001001101100000111010101000000011110001101011001010010101001111111010101001011010010011110111110100011000100111010010101111101011010001110001111011000101110101001110111000010100101110001110011110111101111000011100111010100011010100110110010100001100000000000110100001101110001001100011001111001001101011000110011101100010110011001100100111110010011001101111110000011010111111100101000110001111101101011111001011000010101111000110100000000111100100100001010011001100001101010100001101010101100110001100110110111111101000101000000101111010010010101000011101100100010100000111111101001010100000110110110110011110111010010100001100001010001000001000001111001001111110001100010001001101101110110111010011010100101101010111000010100001000000010010010110110110000010100010010101111101101001111101001010000011000010000011000011111010001101101101011100001101010001001011001011000010100101010000111010101111100101010111111111100010111101101110110101110101110100010010010011101010001010011110111010111011010011110111000100111000111100001111011001010010111010101001000110010000010110001011111111000001100001000100001000111000111111011110101";
          128  + int _ = 36497;
          129  +END
          130  +}
          131  +// END CUT HERE

Added SRM/TCO15-2D-U/1B.cpp version [2d1a81027397e941]

            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 BallsInBoxes { public:
           23  + long long maxTurns(long long N, long long K)
           24  + {
           25  +  if(N < 2*K)
           26  +   return shortCase(N, K);
           27  +  if(N < 3*K)
           28  +   return 1 + shortCase((N+K)/2, K);
           29  +  if(N < 10*K)
           30  +   return 1 + maxTurns(N-K, K);
           31  +  return (N/K-4) + maxTurns(N - (N/K-4)*K, K);
           32  + }
           33  +
           34  + LL shortCase(LL N, LL K) {
           35  +  // The case where N is small enough and all positions are possoible.
           36  +  return solve(N-K);
           37  + }
           38  +
           39  + LL solve(LL N) {
           40  +  // Determine what number in [0,N] out of N boxes are filled.
           41  +  return N ? solve(N/2)+1 : 0;
           42  + }
           43  +};
           44  +
           45  +// BEGIN CUT HERE
           46  +#include <ctime>
           47  +double start_time; string timer()
           48  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           49  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           50  + { os << "{ ";
           51  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           52  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           53  +void verify_case(const long long& Expected, const long long& Received) {
           54  + bool ok = (Expected == Received);
           55  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           56  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           57  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           58  +#define END  verify_case(_, BallsInBoxes().maxTurns(N, K));}
           59  +int main(){
           60  +
           61  +CASE(0)
           62  + long long N = 10LL;
           63  + long long K = 10LL;
           64  + long long _ = 0LL;
           65  +END
           66  +CASE(1)
           67  + long long N = 100LL;
           68  + long long K = 1LL;
           69  + long long _ = 99LL;
           70  +END
           71  +CASE(2)
           72  + long long N = 1000LL;
           73  + long long K = 999LL;
           74  + long long _ = 1LL;
           75  +END
           76  +CASE(3)
           77  + long long N = 10LL;
           78  + long long K = 5LL;
           79  + long long _ = 3LL;
           80  +END
           81  +CASE(4)
           82  + long long N = 1234567898765LL;
           83  + long long K = 658167578LL;
           84  + long long _ = -1LL;
           85  +END
           86  +/*
           87  +CASE(5)
           88  + long long N = LL;
           89  + long long K = LL;
           90  + long long _ = LL;
           91  +END
           92  +*/
           93  +}
           94  +// END CUT HERE