• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           69  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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(*answers_));
           77  + long long _ = 2LL;
           78  +END
           79  +CASE(1)
           80  + int answers_[] = {5, 8};
           81  +   vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_));
           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(*answers_));
           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(*answers_));
           92  + long long _ = 8LL;
           93  +END
           94  +CASE(4)
           95  + int answers_[] = {1, 0, 1};
           96  +   vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_));
           97  + long long _ = 0LL;
           98  +END
           99  +/*
          100  +CASE(5)
          101  + int answers_[] = ;
          102  +   vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_));
          103  + long long _ = LL;
          104  +END
          105  +CASE(6)
          106  + int answers_[] = ;
          107  +   vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_));
          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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           70  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,64,128,256};
          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, 0, 4, 0, 0, 1, 0, 0, 64, 0, 0, 128, 0, 16, 0, 8, 0, 18, 260, 257, 2, 0, 64, 0, 0, 0, 40, 0, 0, 1, 0, 0, 1, 0};
          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, 285, 203, 33, 429, 469, 458, 163, 154, 438, 508};
          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, 0, 4, 0, 0, 1, 0, 0, 64, 0, 0, 128, 0, 16, 0, 8, 0, 18, 260, 257, 2, 0, 64, 0, 0, 0, 40, 0, 0, 1, 0, 0, 1, 0};
          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  +};