SRM502やってきました。
また一回書いたこと消えたし。
まじなえる。。。
というわけでまた適当な記事です。
コードのゴミ箱。今回はよかったからゴミ箱ではないか。
250
// BEGIN CUT HERE // PROBLEM STATEMENT // Farmer John and Fox Brus are participating in a // programming contest as a team. // // // The duration of the contest is T minutes and they are // given N tasks. Solutions can be submitted at any time // during the contest, including exactly T minutes after the // start of the contest. It takes them requiredTime[i] // minutes to solve the i-th task. // // // The score in this contest is represented by two numbers, // solved and penalty. Initially both numbers are 0. If they // solve a task t minutes after the start of the contest, // solved increases by 1 and penalty increases by t. Two // scores are compared by solved first. If two scores have // different solved, the score with bigger solved is better. // If two scores have the same solved, the score with smaller // penalty is better. // // // Return a vector <int> containing exactly two integers that // describes the best score they can get. The first integer // of the return value must represent solved and the second // integer must represent penalty. // // DEFINITION // Class:TheProgrammingContestDivTwo // Method:find // Parameters:int, vector <int> // Returns:vector <int> // Method signature:vector <int> find(int T, vector <int> // requiredTime) // // // CONSTRAINTS // -T will be between 1 and 100,000, inclusive. // -requiredTime will contain between 1 and 50 elements, // inclusive. // -Each element of requiredTime will be between 1 and // 100,000, inclusive. // // // EXAMPLES // // 0) // 74 // {47} // // Returns: {1, 47 } // // They can solve the task. solved will be 1 and penalty will // be 47. // // 1) // 74 // {4747} // // Returns: {0, 0 } // // They don't have time enough to solve the task. // // 2) // 47 // {8, 5} // // Returns: {2, 18 } // // The order is important. If they solve task 0 first and // task 1 second, solved will be 2 and penalty will be 21. If // they solve task 1 first and task 0 second, solved will be // 2 and penalty will be 18. // // 3) // 47 // {12, 3, 21, 6, 4, 13} // // Returns: {5, 86 } // // // // 4) // 58 // {4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8} // // Returns: {10, 249 } // // // // 5) // 100000 // {100000} // // Returns: {1, 100000 } // // END CUT HERE #line 100 "TheProgrammingContestDivTwo.cpp" #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std; class TheProgrammingContestDivTwo { public: vector <int> find(int T, vector <int> requiredTime) { int s = 0, p = 0, time = 0; sort(requiredTime.begin(), requiredTime.end()); for (int i = 0; i < requiredTime.size(); i++) { time += requiredTime[i]; if (time <= T) { p+=time; s++; } } vector<int> ans; ans.push_back(s); ans.push_back(p); return ans; } // BEGIN CUT HERE public: 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(); } private: 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(); } void verify_case(int Case, const vector <int> &Expected, const vector <int> &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; } } void test_case_0() { int Arg0 = 74; int Arr1[] = {47}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1, 47 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(0, Arg2, find(Arg0, Arg1)); } void test_case_1() { int Arg0 = 74; int Arr1[] = {4747}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {0, 0 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(1, Arg2, find(Arg0, Arg1)); } void test_case_2() { int Arg0 = 47; int Arr1[] = {8, 5}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {2, 18 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(2, Arg2, find(Arg0, Arg1)); } void test_case_3() { int Arg0 = 47; int Arr1[] = {12, 3, 21, 6, 4, 13}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {5, 86 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(3, Arg2, find(Arg0, Arg1)); } void test_case_4() { int Arg0 = 58; int Arr1[] = {4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {10, 249 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(4, Arg2, find(Arg0, Arg1)); } void test_case_5() { int Arg0 = 100000; int Arr1[] = {100000}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1, 100000 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(5, Arg2, find(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE int main() { TheProgrammingContestDivTwo __test; __test.run_test(-1); } // END CUT HERE
500
// BEGIN CUT HERE // PROBLEM STATEMENT // Farmer John wants to buy a lottery ticket. Before he buys // a ticket, Fox Brus decided to calculate the probability // that John will get a prize. // // // There are 1,000,000,000 types of lottery tickets. They are // numbered "000000000" to "999999999" (they may have leading // zeroes). Each type of ticket has an equal probability of // being bought by John. You are given a vector <string> // goodSuffixes. If the number written on John's ticket has // at least one element of goodSuffixes as a suffix, he will // get a prize. // // // Return the probability that John will get a prize. // // DEFINITION // Class:TheLotteryBothDivs // Method:find // Parameters:vector <string> // Returns:double // Method signature:double find(vector <string> goodSuffixes) // // // NOTES // -The returned value must have an absolute or relative // error less than 1e-9. // -A suffix of a string is obtained by removing zero or more // contiguous characters from the beginning of the string. // // // CONSTRAINTS // -goodSuffixes will contain between 1 and 50 elements, // inclusive. // -Each element of goodSuffixes will contain between 1 and 9 // characters, inclusive. // -Each character in goodSuffixes will be a digit ('0'-'9'). // // // EXAMPLES // // 0) // {"4"} // // Returns: 0.1 // // John will get a prize if the last digit is '4'. It happens // with probability 0.1. // // 1) // {"4", "7"} // // Returns: 0.2 // // // // 2) // {"47", "47"} // // Returns: 0.01 // // goodSuffixes may contain duplicate elements. // // 3) // {"47", "58", "4747", "502"} // // Returns: 0.021 // // // // 4) // {"8542861", "1954", "6", "523", "000000000", "5426", "8"} // // Returns: 0.201100101 // // // // END CUT HERE #line 82 "TheLotteryBothDivs.cpp" #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std; class TheLotteryBothDivs { public: vector<string> sorts(vector<string> str) { string temp; for (int i=0; i<str.size(); i++) { for (int j=i; j<str.size(); j++) { if (str[i].size() > str[j].size()) { temp = str[i]; str[i] = str[j]; str[j] = temp; } } } return str; } double find(vector <string> goodSuffixes) { goodSuffixes = sorts(goodSuffixes); double p=0; int size=0; bool ok = true; int ten = 1; vector<int> sizes; vector<string> old; string temp; for (int i=0; i<goodSuffixes.size(); i++) { size = goodSuffixes[i].size(); cout << size << ":" << goodSuffixes[i] << endl; if (i != 0) { for (int j=0; j<sizes.size(); j++) { temp = ""; for (int k=size-sizes[j]; k<size; k++) temp+= goodSuffixes[i][k]; if (temp == old[j]) { ok = false; break; } } } if(ok) { for (int j=0; j<size; j++) ten *= 10; p += (double)1/ten; cout << p << endl; } old.push_back(goodSuffixes[i]); sizes.push_back(size); ok = true; ten = 1; } return p; } // BEGIN CUT HERE public: 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(); } private: 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(); } void verify_case(int Case, const double &Expected, const double &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { string Arr0[] = {"4"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.1; verify_case(0, Arg1, find(Arg0)); } void test_case_1() { string Arr0[] = {"4", "7"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.2; verify_case(1, Arg1, find(Arg0)); } void test_case_2() { string Arr0[] = {"47", "47"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.01; verify_case(2, Arg1, find(Arg0)); } void test_case_3() { string Arr0[] = {"47", "58", "4747", "502"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.021; verify_case(3, Arg1, find(Arg0)); } void test_case_4() { string Arr0[] = {"8542861", "1954", "6", "523", "000000000", "5426", "8"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); double Arg1 = 0.201100101; verify_case(4, Arg1, find(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE int main() { TheLotteryBothDivs __test; __test.run_test(-1); } // END CUT HERE