Overview
| SHA1 Hash: | 148e3f363b59b6a1c66c3b75ecc7e03c9e9e8d74 |
|---|---|
| Date: | 2011-09-10 13:56:26 |
| User: | kinaba |
| Comment: | 516 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/516-U/2A.cpp version [2e6ce5bbe0d9efd7]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class NetworkXZeroOne { public: > 23 string reconstruct(string message) > 24 { > 25 if( message[0]=='?' ) { > 26 string msg = message; > 27 msg[0] = 'o'; > 28 if( check(msg) ) > 29 return msg; > 30 message[0] = 'x'; > 31 } > 32 check(message); > 33 return message; > 34 } > 35 > 36 bool check(string& msg) > 37 { > 38 for(int i=1; i<msg.size(); ++i) > 39 if( msg[i]=='?' ) { > 40 if( msg[i-1]=='x' ) > 41 msg[i]='o'; > 42 else > 43 msg[i]='x'; > 44 } > 45 for(int i=0; i<msg.size(); ++i) > 46 for(int k=2; i+k<=msg.size(); k+=2) > 47 if( count(msg.begin()+i, msg.begin()+i+k, 'o')*2 > 48 return false; > 49 return true; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const string& Expected, const string& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, NetworkXZeroOne().reconstruct(message));} > 67 int main(){ > 68 > 69 CASE(0) > 70 string message = "x?x?"; > 71 string _ = "xoxo"; > 72 END > 73 CASE(1) > 74 string message = "?xo?"; > 75 string _ = "oxox"; > 76 END > 77 CASE(2) > 78 string message = "xo"; > 79 string _ = "xo"; > 80 END > 81 CASE(3) > 82 string message = "o??x??o"; > 83 string _ = "oxoxoxo"; > 84 END > 85 CASE(4) > 86 string message = "???????x"; > 87 string _ = "oxoxoxox"; > 88 END > 89 /* > 90 CASE(5) > 91 string message = ; > 92 string _ = ; > 93 END > 94 CASE(6) > 95 string message = ; > 96 string _ = ; > 97 END > 98 */ > 99 } > 100 // END CUT HERE
Added SRM/516-U/2B.cpp version [8e15fec270ef292a]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class NetworkXOneTimePad { public: > 23 int crack(vector <string> plaintexts, vector <string> ciphertexts) > 24 { > 25 set<string> possible_keys; > 26 for(int i=0; i<plaintexts.size(); ++i) > 27 for(int j=0; j<ciphertexts.size(); ++j) > 28 possible_keys.insert(key(plaintexts[i], cipherte > 29 > 30 int cnt = 0; > 31 for(set<string>::iterator it=possible_keys.begin(); it!=possible > 32 { > 33 const string& key = *it; > 34 set<string> target(plaintexts.begin(), plaintexts.end()) > 35 for(int i=0; i<ciphertexts.size(); ++i) { > 36 string ci = cipher(ciphertexts[i], key); > 37 if( !target.count(ci) ) > 38 goto next; > 39 target.erase(ci); > 40 } > 41 ++cnt; > 42 next:; > 43 } > 44 return cnt; > 45 } > 46 > 47 string cipher(const string& a, const string& b) > 48 { > 49 string c; > 50 for(int i=0; i<a.size(); ++i) > 51 c += char(a[i]^(b[i]=='1')); > 52 return c; > 53 } > 54 > 55 string key(const string& a, const string& b) > 56 { > 57 string c; > 58 for(int i=0; i<a.size(); ++i) > 59 c += (a[i]==b[i] ? '0' : '1'); > 60 return c; > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const int& Expected, const int& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, NetworkXOneTimePad().crack(plaintexts, ciphertex > 78 int main(){ > 79 > 80 CASE(0) > 81 string plaintexts_[] = {"110", "001"}; > 82 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 83 string ciphertexts_[] = {"101", "010"}; > 84 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 85 int _ = 2; > 86 END > 87 CASE(1) > 88 string plaintexts_[] = {"00", "01", "10", "11"}; > 89 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 90 string ciphertexts_[] = {"00", "01", "10", "11"}; > 91 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 92 int _ = 4; > 93 END > 94 CASE(2) > 95 string plaintexts_[] = {"01", "10"}; > 96 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 97 string ciphertexts_[] = {"00"}; > 98 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 99 int _ = 2; > 100 END > 101 CASE(3) > 102 string plaintexts_[] = {"000", "111", "010", "101", "110", "001"}; > 103 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 104 string ciphertexts_[] = {"011", "100"}; > 105 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 106 int _ = 6; > 107 END > 108 /* > 109 CASE(4) > 110 string plaintexts_[] = ; > 111 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 112 string ciphertexts_[] = ; > 113 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 114 int _ = ; > 115 END > 116 CASE(5) > 117 string plaintexts_[] = ; > 118 vector <string> plaintexts(plaintexts_, plaintexts_+sizeof(plaintexts_ > 119 string ciphertexts_[] = ; > 120 vector <string> ciphertexts(ciphertexts_, ciphertexts_+sizeof(cipherte > 121 int _ = ; > 122 END > 123 */ > 124 } > 125 // END CUT HERE
Added SRM/516-U/2C.cpp version [9236182d87218311]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class NetworkXMessageRecovery { public: > 23 string recover(vector <string> messages) > 24 { > 25 map< char, set<char> > prev; > 26 for(int i=0; i<messages.size(); ++i) { > 27 prev[messages[i][0]]; > 28 for(int j=0; j+1<messages[i].size(); ++j) > 29 prev[messages[i][j+1]].insert(messages[i][j]); > 30 } > 31 > 32 string result; > 33 while( !prev.empty() ) > 34 { > 35 set<char> cand; > 36 for(map< char,set<char> >::iterator it=prev.begin(); it! > 37 if( it->second.empty() ) > 38 cand.insert(it->first); > 39 char c = *cand.begin(); > 40 result += c; > 41 for(map< char,set<char> >::iterator it=prev.begin(); it! > 42 it->second.erase(c); > 43 prev.erase(c); > 44 } > 45 return result; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const string& Expected, const string& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, NetworkXMessageRecovery().recover(messages));} > 63 int main(){ > 64 > 65 CASE(0) > 66 string messages_[] = {"acd", "bce"}; > 67 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 68 string _ = "abcde"; > 69 END > 70 CASE(1) > 71 string messages_[] = {"ed", "dc", "cb", "ba"}; > 72 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 73 string _ = "edcba"; > 74 END > 75 CASE(2) > 76 string messages_[] = {"Fox", "Ciel", "FoxCiel"}; > 77 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 78 string _ = "FoxCiel"; > 79 END > 80 CASE(3) > 81 string messages_[] = {"a", "A"}; > 82 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 83 string _ = "Aa"; > 84 END > 85 /* > 86 CASE(4) > 87 string messages_[] = ; > 88 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 89 string _ = ; > 90 END > 91 CASE(5) > 92 string messages_[] = ; > 93 vector <string> messages(messages_, messages_+sizeof(messages_)/sizeof > 94 string _ = ; > 95 END > 96 */ > 97 } > 98 // END CUT HERE