Overview
| SHA1 Hash: | 085e72a21bf2c9f70ecda89974e378160f68f0ed |
|---|---|
| Date: | 2011-07-09 15:15:05 |
| User: | kinaba |
| Comment: | 511 |
| 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/511-U/1A-U.cpp version [0939e8f38eb262b6]
> 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 Zoo { public: > 23 long long theCount(vector <int> answers) > 24 { > 25 map<int,int> nc; > 26 for(int i=0; i<answers.size(); ++i) > 27 nc[answers[i]] ++; > 28 > 29 int two = 0; > 30 int one = 0; > 31 for(int k=0 ;; ++k) > 32 if( nc[k] == 2 ) > 33 two++; > 34 else if( nc[k] == 1 ) > 35 { > 36 for(;; ++k) > 37 if( nc[k] == 1 ) > 38 one++; > 39 else if( nc[k] == 0 ) > 40 break; > 41 else > 42 return 0LL; > 43 break; > 44 } > 45 else if( nc[k] == 0 ) > 46 break; > 47 else > 48 return 0LL; > 49 if( two*2 + one != answers.size() ) > 50 return 0LL; > 51 LL r = 2; > 52 for(int i=0; i<two; ++i) > 53 r = r*2; > 54 return r; > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const long long& Expected, const long long& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, Zoo().theCount(answers));} > 72 int main(){ > 73 > 74 CASE(0) > 75 int answers_[] = {0, 1, 2, 3, 4}; > 76 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 77 long long _ = 2LL; > 78 END > 79 CASE(1) > 80 int answers_[] = {5, 8}; > 81 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 82 long long _ = 0LL; > 83 END > 84 CASE(2) > 85 int answers_[] = {0, 0, 0, 0, 0, 0}; > 86 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 87 long long _ = 0LL; > 88 END > 89 CASE(3) > 90 int answers_[] = {1, 0, 2, 0, 1}; > 91 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 92 long long _ = 8LL; > 93 END > 94 CASE(4) > 95 int answers_[] = {1, 0, 1}; > 96 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 97 long long _ = 0LL; > 98 END > 99 /* > 100 CASE(5) > 101 int answers_[] = ; > 102 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 103 long long _ = LL; > 104 END > 105 CASE(6) > 106 int answers_[] = ; > 107 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 108 long long _ = LL; > 109 END > 110 */ > 111 } > 112 // END CUT HERE
Added SRM/511-U/1B-U.cpp version [5cb364fac0d3a48f]
> 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 FiveHundredEleven { public: > 23 string theWinner(vector <int> cards) > 24 { > 25 return rec(cards, 511) ? "Fox Ciel" : "Toastman"; > 26 } > 27 > 28 bool rec(const vector<int>& cards_, int goal) > 29 { > 30 if( goal == 0 ) > 31 return true; > 32 > 33 bool inv = false; > 34 vector<int> cards; > 35 for(int i=0; i<cards_.size(); ++i) > 36 if( cards_[i]&goal ) > 37 cards.push_back( cards_[i]&goal ); > 38 else > 39 inv = !inv; > 40 > 41 for(int i=0; i<cards.size(); ++i) > 42 { > 43 const int c = cards[i]; > 44 cards[i] = cards.back(); > 45 cards.pop_back(); > 46 > 47 if( !rec(cards, goal &~ c) ) > 48 return true ^ inv; > 49 > 50 if( i < cards.size() ) { > 51 cards.push_back(cards[i]); > 52 cards[i] = c; > 53 } > 54 } > 55 return false ^ inv; > 56 } > 57 }; > 58 > 59 // BEGIN CUT HERE > 60 #include <ctime> > 61 double start_time; string timer() > 62 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 63 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 64 { os << "{ "; > 65 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 66 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 67 void verify_case(const string& Expected, const string& Received) { > 68 bool ok = (Expected == Received); > 69 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 70 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 71 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 72 #define END verify_case(_, FiveHundredEleven().theWinner(cards));} > 73 int main(){ > 74 > 75 CASE(0) > 76 int cards_[] = {3, 5, 7, 9, 510}; > 77 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 78 string _ = "Fox Ciel"; > 79 END > 80 CASE(1) > 81 int cards_[] = {0, 0, 0, 0}; > 82 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 83 string _ = "Toastman"; > 84 END > 85 CASE(2) > 86 int cards_[] = {511}; > 87 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 88 string _ = "Toastman"; > 89 END > 90 CASE(3) > 91 int cards_[] = {5, 58, 192, 256}; > 92 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 93 string _ = "Fox Ciel"; > 94 END > 95 CASE(4) > 96 int cards_[] = {1}; > 97 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 98 string _ = "Fox Ciel"; > 99 END > 100 CASE(5) > 101 int cards_[] = {1,2,4,8,16,32,64,128,256}; > 102 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 103 string _ = "Toastman"; > 104 END > 105 /* > 106 CASE(6) > 107 int cards_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 > 108 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 109 string _ = "???"; > 110 END > 111 CASE(7) > 112 int cards_[] = {2, 0, 0, 0, 32, 0, 0, 0, 0, 64, 0, 32, 0, 0, 128, 8, 128 > 113 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 114 string _ = "Fox Ciel"; > 115 END > 116 */ > 117 CASE(8) > 118 int cards_[] = {461, 443, 177, 366, 499, 384, 125, 499, 372, 374, 39, 28 > 119 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 120 string _ = "Toastman"; > 121 END > 122 CASE(9) > 123 int cards_[] = {511, 0}; > 124 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 125 string _ = "Fox Ciel"; > 126 END > 127 CASE(10) > 128 int cards_[] = {2, 0, 0, 0, 32, 0, 0, 0, 0, 64, 0, 32, 0, 0, 128, 8, 128 > 129 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 130 string _ = "Fox Ciel"; > 131 END > 132 } > 133 // END CUT HERE
Added lib/typical/BigIntegerUseCase.java version [49868c43512ca5f3]
> 1 import java.math.*; > 2 import java.util.*; > 3 > 4 public class ZenoDivision { > 5 static BigInteger ZERO = BigInteger.ZERO; > 6 static BigInteger ONE = BigInteger.ONE; > 7 static BigInteger TWO = BigInteger.valueOf(2); > 8 static BigInteger TEN = BigInteger.TEN; > 9 > 10 public String cycle(String a_, String b_) > 11 { > 12 BigInteger a = new BigInteger(a_); > 13 BigInteger b = new BigInteger(b_); > 14 > 15 if( b.remainder(TWO).equals(ZERO) ) > 16 return "impossible"; > 17 if( a.equals(ZERO) && b.equals(ONE) ) > 18 return "-"; > 19 if( a.equals(ONE) && b.equals(ONE) ) > 20 return "*"; > 21 > 22 int x = 1; > 23 while( !TWO.modPow(BigInteger.valueOf(x),b).equals(ONE) ) { > 24 x++; > 25 if( x >= 61 ) > 26 return "impossible"; > 27 } > 28 > 29 BigInteger z = TWO.pow(x).subtract(ONE).divide(b); > 30 String str = a.multiply(z).toString(2); > 31 while( str.length() < x ) > 32 str = "0" + str; > 33 > 34 String answer = ""; > 35 for(int i=0; i<str.length(); ++i) > 36 answer += (str.charAt(i)=='1' ? "*" : "-"); > 37 return answer; > 38 } > 39 };