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: int gcd(int x, int y) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: while(y) { 4fd800b3a8 2011-02-23 kinaba: int t = x; 4fd800b3a8 2011-02-23 kinaba: x = y; 4fd800b3a8 2011-02-23 kinaba: y = t%y; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return x; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class GradingGridIns 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: vector <string> score(vector <string> answer, vector <int> lower, vector <int> upper) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int lg = gcd(lower[0], lower[1]); 4fd800b3a8 2011-02-23 kinaba: double la=lower[0]/lg, lb=lower[1]/lg; 4fd800b3a8 2011-02-23 kinaba: int ug = gcd(upper[0], upper[1]); 4fd800b3a8 2011-02-23 kinaba: double ua=upper[0]/ug, ub=upper[1]/ug; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> world; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: char c[] = " ./0123456789"; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<sizeof(c)-1; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<sizeof(c)-1; ++j) 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<sizeof(c)-1; ++k) 4fd800b3a8 2011-02-23 kinaba: for(int l=0; l<sizeof(c)-1; ++l) { 4fd800b3a8 2011-02-23 kinaba: try { 4fd800b3a8 2011-02-23 kinaba: double d = eval( string(1,c[i])+c[j]+c[k]+c[l] ); 4fd800b3a8 2011-02-23 kinaba: world.push_back(d); 4fd800b3a8 2011-02-23 kinaba: } catch( const char* ) { 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: sort(world.begin(), world.end()); 4fd800b3a8 2011-02-23 kinaba: world.erase(unique(world.begin(), world.end()), world.end()); 4fd800b3a8 2011-02-23 kinaba: vector<double>::iterator lt = lower_bound( world.begin(), world.end(), la/lb ); 4fd800b3a8 2011-02-23 kinaba: vector<double>::iterator ut = upper_bound( world.begin(), world.end(), ua/ub ); 4fd800b3a8 2011-02-23 kinaba: if( lt!=world.begin() ) --lt; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<string> result(answer.size()); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<answer.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: try { 4fd800b3a8 2011-02-23 kinaba: double d = eval(answer[i]); 4fd800b3a8 2011-02-23 kinaba: result[i] = (*lt<=d && (ut==world.end() || d<=*ut) ? "CORRECT" : "INCORRECT"); 4fd800b3a8 2011-02-23 kinaba: } catch( const char* ) { 4fd800b3a8 2011-02-23 kinaba: result[i] = "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return result; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: static double eval( string ans ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int ii=0; while(ii<ans.size()&&ans[ii]==' ') ++ii; 4fd800b3a8 2011-02-23 kinaba: ans = ans.substr(ii); 4fd800b3a8 2011-02-23 kinaba: ii = ans.size(); while(ii>0 && ans[ii-1]==' ') --ii; 4fd800b3a8 2011-02-23 kinaba: ans = ans.substr(0, ii); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int dot=-1, sla=-1, numdig=0; 4fd800b3a8 2011-02-23 kinaba: int value = 0, value_pre = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<ans.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( ans[i]=='.' ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if(dot>=0 || sla>=0) 4fd800b3a8 2011-02-23 kinaba: throw "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: dot = i; 4fd800b3a8 2011-02-23 kinaba: value_pre = value; 4fd800b3a8 2011-02-23 kinaba: value = 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else if( ans[i]=='/' ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if(dot>=0 || sla>=0 || numdig==0 ) 4fd800b3a8 2011-02-23 kinaba: throw "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: sla = i; 4fd800b3a8 2011-02-23 kinaba: value_pre = value; 4fd800b3a8 2011-02-23 kinaba: value = 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else if( '0'<=ans[i] && ans[i]<='9' ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: ++numdig; 4fd800b3a8 2011-02-23 kinaba: value = value*10 + ans[i]-'0'; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: throw "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: if(numdig==0) 4fd800b3a8 2011-02-23 kinaba: throw "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int L = value_pre, R = value; 4fd800b3a8 2011-02-23 kinaba: if( sla >= 0 ) { 4fd800b3a8 2011-02-23 kinaba: if( R == 0 ) 4fd800b3a8 2011-02-23 kinaba: throw "MALFORMED"; 4fd800b3a8 2011-02-23 kinaba: int g = gcd(L,R); L/=g, R/=g; 4fd800b3a8 2011-02-23 kinaba: return L/double(R); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else if( dot >= 0 ) { 4fd800b3a8 2011-02-23 kinaba: return L + R / pow(10.0, double(ans.size()-dot-1)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else { 4fd800b3a8 2011-02-23 kinaba: return R; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 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(); } 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 vector <string> &Expected, const vector <string> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } } 4fd800b3a8 2011-02-23 kinaba: void test_case_0() { string Arr0[] = {"4/7 "," 4/7","4/07","8/14",".571",".572"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {4,7}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {4,7}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); string Arr3[] = {"CORRECT", "CORRECT", "CORRECT", "CORRECT", "CORRECT", "CORRECT" }; vector <string> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); verify_case(0, Arg3, score(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_1() { string Arr0[] = {" 4/7","1.01","1.02"," 000"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); string Arr3[] = {"CORRECT", "CORRECT", "INCORRECT", "CORRECT" }; vector <string> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); verify_case(1, Arg3, score(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_2() { string Arr0[] = {"1.15","1 14","1.14"," 8/7"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1142,1000}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1142,1000}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); string Arr3[] = {"INCORRECT", "MALFORMED", "CORRECT", "CORRECT" }; vector <string> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); verify_case(2, Arg3, score(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_3() { string Arr0[] = {" ","...."," . ","1 23","8//5","9.4.","85/ ","/123","123/"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); string Arr3[] = {"MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED", "MALFORMED" }; vector <string> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); verify_case(3, Arg3, score(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_4() { string Arr0[] = {"1/0 "}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {9999,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); string Arr3[] = {"MALFORMED" }; vector <string> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); verify_case(4, Arg3, score(Arg0, Arg1, Arg2)); } 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() { GradingGridIns().run_test(-1); } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE