SRM540 DIV1 easy
easy : ImportantSequence
普通に難しい、intだと通らなかったりするので…
元の数列 {1,2,3,4}と、符号 {+-+} があり、それを計算した結果{3,-1,7}となったが、
元の数列がほしくなった為、{3,-1,7}と{+-+}から元の数列を求めたい。
この場合{1,2,3,4}と{2,1,2,5}の2通りがあるため
答えは2通りとなる。
a[0]が決まれば、自動的にa[3]が決まるので、a[3]の範囲が求まればいい。
1 <= a[0]なので、1 <= a[1] <= 2, 2 <= a[2] <= 3, 4 <= a[3] <= 5
となること利用して、答えを出す。
#ifdef TEST_CODE #define typeof(X) std::identity<decltype(X)>::type //C++0x #else #define typeof(X) __typeof__(X) // for gcc #endif #define sz(a) int((a).size()) #define FOREACH(it, c) for (typeof((c).begin()) it=(c).begin(); it != (c).end(); ++it) #define FOR(i,n) for(int i = 0; i < (n); i++) using namespace std; static const double EPS = 1e-5; typedef long long ll; class ImportantSequence { public: int getCount(vector <int> B, string operators) { ll mn = 1,mx = LLONG_MAX; FOR(i,sz(B)){ ll nmn,nmx; if(operators[i] == '+'){ if(mn > B[i]) return 0; nmn = max<ll>(B[i] - mx,1); nmx = B[i] - mn; } else { if(mx <= B[i]) return 0; nmn = max<ll>(1, mn- B[i]); nmx = (mx == LLONG_MAX) ? LLONG_MAX : mx - B[i]; } mn = nmn; mx = nmx; } if(mx == LLONG_MAX) return -1; return (int)(mx - mn) + 1; } };