4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class BusTrip 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: int returnTime(int, vector <string> buses) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int t=-1, v=0; 4fd800b3a8 2011-02-23 kinaba: do 4fd800b3a8 2011-02-23 kinaba: onestep( t, v, buses ); 4fd800b3a8 2011-02-23 kinaba: while( v ); 4fd800b3a8 2011-02-23 kinaba: return t; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: void onestep(int& t, int& v, vector<string>& buses) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int mt=1001, mv=0; 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<buses.size(); ++j) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stringstream sin(buses[j]); 4fd800b3a8 2011-02-23 kinaba: vector<int> vs; 4fd800b3a8 2011-02-23 kinaba: for(int x; sin>>x;) 4fd800b3a8 2011-02-23 kinaba: vs.push_back(x); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int loop_time = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<vs.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: loop_time += abs(vs[(i+1)%vs.size()] - vs[i]); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int rem = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<vs.size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: if( v==vs[i] ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int nt = rem; 4fd800b3a8 2011-02-23 kinaba: while( t >= nt ) 4fd800b3a8 2011-02-23 kinaba: nt += loop_time; 4fd800b3a8 2011-02-23 kinaba: if( nt < mt ) { 4fd800b3a8 2011-02-23 kinaba: mt = nt; 4fd800b3a8 2011-02-23 kinaba: mv = vs[(i+1)%vs.size()]; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: rem += abs(vs[(i+1)%vs.size()] - vs[i]); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: t = mt + abs(mv-v); 4fd800b3a8 2011-02-23 kinaba: v = mv; 4fd800b3a8 2011-02-23 kinaba: if( t > 1000 ) 4fd800b3a8 2011-02-23 kinaba: t=-1, v=0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } 4fd800b3a8 2011-02-23 kinaba: private: 4fd800b3a8 2011-02-23 kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: void test_case_0() { int Arg0 = 3; string Arr1[] = {"0 1 2"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 12; verify_case(0, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_1() { int Arg0 = 51; string Arr1[] = {"0 5 10 15 20 25 30 35 40 50"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 1000; verify_case(1, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_2() { int Arg0 = 3; string Arr1[] = {"0 1 2", "2 1 0"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = -1; verify_case(2, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_3() { int Arg0 = 5; string Arr1[] = {"0 1 2 3 4", "3 1 2 0", "4 1 2 3 0", "1 2 0 3 4", "4 0"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 12; verify_case(3, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_4() { int Arg0 = 25; string Arr1[] = {"24 14 9 7 2", "21 4 18 24 7 1 2 11 8 9 14 16 5 17 13 23 19 15 22", "12 22 24 9 1 5 10 8 7 18 16 19 4 13 17", 4fd800b3a8 2011-02-23 kinaba: "14 5 17 9 23 7 16 22 10 4 6", "19 8 1 9 24 3 5 22 16 7 6 4 10 23 17 0 13 15", 4fd800b3a8 2011-02-23 kinaba: "2 16 10 13 14 1 11 20 0 24 22 23 19 4 18", "19 15 18 0", "15 9 22 5 20 8 23 14 24 18 21 6 13 19", 4fd800b3a8 2011-02-23 kinaba: "2 6 19 3 21 10 20 22 24 13 16 15 8 18 17 14 5", "19 10 1 7 5 11 21 8 14 0 17 23 12 2 3 16"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 157; verify_case(4, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_5() { int Arg0 = 100; string Arr1[] = {"0 10 30 45 60 46 39 31 20", "9 20 0 86"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = -1; verify_case(5, Arg2, returnTime(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: int main() { BusTrip().run_test(-1); } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE