d02edd33e2 2018-06-03 kinaba: #include <iostream> d02edd33e2 2018-06-03 kinaba: #include <sstream> d02edd33e2 2018-06-03 kinaba: #include <iomanip> d02edd33e2 2018-06-03 kinaba: #include <vector> d02edd33e2 2018-06-03 kinaba: #include <string> d02edd33e2 2018-06-03 kinaba: #include <map> d02edd33e2 2018-06-03 kinaba: #include <set> d02edd33e2 2018-06-03 kinaba: #include <algorithm> d02edd33e2 2018-06-03 kinaba: #include <numeric> d02edd33e2 2018-06-03 kinaba: #include <iterator> d02edd33e2 2018-06-03 kinaba: #include <functional> d02edd33e2 2018-06-03 kinaba: #include <complex> d02edd33e2 2018-06-03 kinaba: #include <queue> d02edd33e2 2018-06-03 kinaba: #include <stack> d02edd33e2 2018-06-03 kinaba: #include <cmath> d02edd33e2 2018-06-03 kinaba: #include <cassert> d02edd33e2 2018-06-03 kinaba: #include <tuple> d02edd33e2 2018-06-03 kinaba: using namespace std; d02edd33e2 2018-06-03 kinaba: typedef long long LL; d02edd33e2 2018-06-03 kinaba: typedef complex<double> CMP; d02edd33e2 2018-06-03 kinaba: d02edd33e2 2018-06-03 kinaba: class ArithmeticSequenceDiv1 { public: d02edd33e2 2018-06-03 kinaba: int findMinCost(vector <int> x) d02edd33e2 2018-06-03 kinaba: { d02edd33e2 2018-06-03 kinaba: int best = 0x7fffffff; d02edd33e2 2018-06-03 kinaba: for (int i = 0; i < x.size(); ++i) { d02edd33e2 2018-06-03 kinaba: // x[i]: fixed d02edd33e2 2018-06-03 kinaba: for (int z = 0; z < 1000; ++z) { d02edd33e2 2018-06-03 kinaba: int ss[] = { -1,+1 }; d02edd33e2 2018-06-03 kinaba: for (int s : ss) { d02edd33e2 2018-06-03 kinaba: int cur_cost = 0; d02edd33e2 2018-06-03 kinaba: for (int k = 0; k < x.size(); ++k) { d02edd33e2 2018-06-03 kinaba: int v = x[i]+s*z*(k-i); d02edd33e2 2018-06-03 kinaba: cur_cost += abs(v - x[k]); d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: best = min(best, cur_cost); d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: return best; d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: }; d02edd33e2 2018-06-03 kinaba: d02edd33e2 2018-06-03 kinaba: // BEGIN CUT HERE d02edd33e2 2018-06-03 kinaba: #include <ctime> d02edd33e2 2018-06-03 kinaba: double start_time; string timer() d02edd33e2 2018-06-03 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d02edd33e2 2018-06-03 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d02edd33e2 2018-06-03 kinaba: { os << "{ "; d02edd33e2 2018-06-03 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d02edd33e2 2018-06-03 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d02edd33e2 2018-06-03 kinaba: void verify_case(const int& Expected, const int& Received) { d02edd33e2 2018-06-03 kinaba: bool ok = (Expected == Received); d02edd33e2 2018-06-03 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d02edd33e2 2018-06-03 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d02edd33e2 2018-06-03 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d02edd33e2 2018-06-03 kinaba: #define END verify_case(_, ArithmeticSequenceDiv1().findMinCost(x));} d02edd33e2 2018-06-03 kinaba: int main(){ d02edd33e2 2018-06-03 kinaba: d02edd33e2 2018-06-03 kinaba: CASE(0) d02edd33e2 2018-06-03 kinaba: int x_[] = {1,3,2}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 2; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(1) d02edd33e2 2018-06-03 kinaba: int x_[] = {1,1,1,2,3,4,5}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 3; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(2) d02edd33e2 2018-06-03 kinaba: int x_[] = {1,2,3,4}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 0; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(3) d02edd33e2 2018-06-03 kinaba: int x_[] = {1,5,2,5}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 5; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(4) d02edd33e2 2018-06-03 kinaba: int x_[] = {11,33,22}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 17; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(5) d02edd33e2 2018-06-03 kinaba: int x_[] = {1, 3, 5, 7, 2, 4, 6}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = 12; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: CASE(6) d02edd33e2 2018-06-03 kinaba: int x_[] = {17,68,99,48,66,66,20,88,91,4,20,7,82,23,76,55,50,7,46,88,73,40,41,48,32,18,71,58,56,68,2,99,7,13,19,11,55,95,23,40,17,89,41,12,5,82,93,93,19,20,41,8,15,24,53,87,54,10,12,41,86,95,92,13,56,6,67,72,95,78,82,34,75,12,11,100,99,46,32,45,59,1,63,60,13,94,33,13,85,35,65,40,37,22,37,87,35,2,92,64}; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = -1; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: /* d02edd33e2 2018-06-03 kinaba: CASE(7) d02edd33e2 2018-06-03 kinaba: int x_[] = ; d02edd33e2 2018-06-03 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d02edd33e2 2018-06-03 kinaba: int _ = ; d02edd33e2 2018-06-03 kinaba: END d02edd33e2 2018-06-03 kinaba: */ d02edd33e2 2018-06-03 kinaba: } d02edd33e2 2018-06-03 kinaba: // END CUT HERE