98c5c562ca 2015-02-02 kinaba: #include <iostream> 98c5c562ca 2015-02-02 kinaba: #include <sstream> 98c5c562ca 2015-02-02 kinaba: #include <iomanip> 98c5c562ca 2015-02-02 kinaba: #include <vector> 98c5c562ca 2015-02-02 kinaba: #include <string> 98c5c562ca 2015-02-02 kinaba: #include <map> 98c5c562ca 2015-02-02 kinaba: #include <set> 98c5c562ca 2015-02-02 kinaba: #include <algorithm> 98c5c562ca 2015-02-02 kinaba: #include <numeric> 98c5c562ca 2015-02-02 kinaba: #include <iterator> 98c5c562ca 2015-02-02 kinaba: #include <functional> 98c5c562ca 2015-02-02 kinaba: #include <complex> 98c5c562ca 2015-02-02 kinaba: #include <queue> 98c5c562ca 2015-02-02 kinaba: #include <stack> 98c5c562ca 2015-02-02 kinaba: #include <cmath> 98c5c562ca 2015-02-02 kinaba: #include <cassert> 98c5c562ca 2015-02-02 kinaba: #include <tuple> 98c5c562ca 2015-02-02 kinaba: using namespace std; 98c5c562ca 2015-02-02 kinaba: typedef long long LL; 98c5c562ca 2015-02-02 kinaba: typedef complex<double> CMP; 98c5c562ca 2015-02-02 kinaba: 98c5c562ca 2015-02-02 kinaba: class TheConsecutiveIntegersDivOne { public: 98c5c562ca 2015-02-02 kinaba: int find(vector <int> numbers, int k) 98c5c562ca 2015-02-02 kinaba: { 98c5c562ca 2015-02-02 kinaba: sort(numbers.begin(), numbers.end()); 98c5c562ca 2015-02-02 kinaba: int best = 0x7fffffff; 98c5c562ca 2015-02-02 kinaba: for(int fixed=0; fixed<numbers.size(); ++fixed) { 98c5c562ca 2015-02-02 kinaba: for(int s=0; s+k<=numbers.size(); ++s) { 98c5c562ca 2015-02-02 kinaba: if(s<=fixed && fixed<=s+k) { 98c5c562ca 2015-02-02 kinaba: int cost = 0; 98c5c562ca 2015-02-02 kinaba: for(int i=0; i<k; ++i) 98c5c562ca 2015-02-02 kinaba: cost += abs(numbers[s+i] - (numbers[fixed]-(fixed-s-i))); 98c5c562ca 2015-02-02 kinaba: best = min(best, cost); 98c5c562ca 2015-02-02 kinaba: } 98c5c562ca 2015-02-02 kinaba: } 98c5c562ca 2015-02-02 kinaba: } 98c5c562ca 2015-02-02 kinaba: return best; 98c5c562ca 2015-02-02 kinaba: } 98c5c562ca 2015-02-02 kinaba: }; 98c5c562ca 2015-02-02 kinaba: 98c5c562ca 2015-02-02 kinaba: // BEGIN CUT HERE 98c5c562ca 2015-02-02 kinaba: #include <ctime> 98c5c562ca 2015-02-02 kinaba: double start_time; string timer() 98c5c562ca 2015-02-02 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 98c5c562ca 2015-02-02 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 98c5c562ca 2015-02-02 kinaba: { os << "{ "; 98c5c562ca 2015-02-02 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 98c5c562ca 2015-02-02 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 98c5c562ca 2015-02-02 kinaba: void verify_case(const int& Expected, const int& Received) { 98c5c562ca 2015-02-02 kinaba: bool ok = (Expected == Received); 98c5c562ca 2015-02-02 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 98c5c562ca 2015-02-02 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 98c5c562ca 2015-02-02 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 98c5c562ca 2015-02-02 kinaba: #define END verify_case(_, TheConsecutiveIntegersDivOne().find(numbers, k));} 98c5c562ca 2015-02-02 kinaba: int main(){ 98c5c562ca 2015-02-02 kinaba: 98c5c562ca 2015-02-02 kinaba: CASE(0) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = {4, 7, 47}; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = 2; 98c5c562ca 2015-02-02 kinaba: int _ = 2; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: CASE(1) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = {1, 100}; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = 1; 98c5c562ca 2015-02-02 kinaba: int _ = 0; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: CASE(2) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = {-96, -53, 82, -24, 6, -75}; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = 2; 98c5c562ca 2015-02-02 kinaba: int _ = 20; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: CASE(3) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = {64, -31, -56}; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = 2; 98c5c562ca 2015-02-02 kinaba: int _ = 24; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: CASE(4) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = {-96, -53, 82, -24, 6, -75}; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = 4; 98c5c562ca 2015-02-02 kinaba: int _ = 90; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: /* 98c5c562ca 2015-02-02 kinaba: CASE(5) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = ; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = ; 98c5c562ca 2015-02-02 kinaba: int _ = ; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: CASE(6) 98c5c562ca 2015-02-02 kinaba: int numbers_[] = ; 98c5c562ca 2015-02-02 kinaba: vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); 98c5c562ca 2015-02-02 kinaba: int k = ; 98c5c562ca 2015-02-02 kinaba: int _ = ; 98c5c562ca 2015-02-02 kinaba: END 98c5c562ca 2015-02-02 kinaba: */ 98c5c562ca 2015-02-02 kinaba: } 98c5c562ca 2015-02-02 kinaba: // END CUT HERE