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

Added SRM/504.5/1A.cpp version [7026c83513549f24]

            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 TheNumbersWithLuckyLastDigit { public:
           23  + int find(int n)
           24  + {
           25  +  int feasible[10][2] = {
           26  +   {20, 5}, // 4+4+4+4+4
           27  +   {11, 2}, // 4+7
           28  +   {12, 3}, // 4+4+4 (4+4+7+7)
           29  +   {23, 5}, // 4+4+4+4+7
           30  +   { 4, 1}, // 4     (7+7)
           31  +   {15, 3}, // 4+4+7
           32  +   {16, 4}, // 4+4+4+4
           33  +   { 7, 1}, // 7
           34  +   { 8, 2}, // 4+4   (4+7+7)
           35  +   {19, 4}, // 4+4+4+7
           36  +  };
           37  +  if( feasible[n%10][0] <= n )
           38  +   return feasible[n%10][1];
           39  +  return -1;
           40  + }
           41  +};
           42  +
           43  +// BEGIN CUT HERE
           44  +#include <ctime>
           45  +double start_time; string timer()
           46  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           47  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           48  + { os << "{ ";
           49  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           50  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           51  +void verify_case(const int& Expected, const int& Received) {
           52  + bool ok = (Expected == Received);
           53  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           54  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           55  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           56  +#define END  verify_case(_, TheNumbersWithLuckyLastDigit().find(n));}
           57  +int main(){
           58  +
           59  +CASE(0)
           60  + int n = 99;
           61  + int _ = 4;
           62  +END
           63  +CASE(1)
           64  + int n = 11;
           65  + int _ = 2;
           66  +END
           67  +CASE(2)
           68  + int n = 13;
           69  + int _ = -1;
           70  +END
           71  +CASE(3)
           72  + int n = 1234567;
           73  + int _ = 1;
           74  +END
           75  +CASE(4)
           76  + int n = 1;
           77  + int _ = 2;
           78  +END
           79  +CASE(5)
           80  + int n = 1000000000;
           81  + int _ = -1;
           82  +END
           83  +
           84  +}
           85  +// END CUT HERE

Added SRM/504.5/1B.java version [40bffdccb4631d69]

            1  +import java.math.*;
            2  +import java.util.*;
            3  +
            4  +public class TheJackpotDivOne {
            5  + public long[] find(long[] money, long jackpot)
            6  + {
            7  +  long M = 0;
            8  +  for(int i=0; i<money.length; ++i)
            9  +   if( M < money[i] )
           10  +    M = money[i];
           11  +
           12  +  boolean unsat_case = false;
           13  +  {
           14  +   long J = jackpot;
           15  +   for(int i=0; i<money.length; ++i) {
           16  +    J -= M-money[i];
           17  +    if( J < 0 )
           18  +     {unsat_case = true; break;}
           19  +   }
           20  +   if( !unsat_case ) {
           21  +    // everyones get M, and J left.
           22  +    long[] result = new long[money.length];
           23  +    for(int i=0; i<money.length; ++i)
           24  +     result[i] = M + (J / money.length) + (i<J%money.length ? 1 : 0);
           25  +    Arrays.sort(result);
           26  +    return result;
           27  +   }
           28  +  }
           29  +  {
           30  +   long J = jackpot;
           31  +   BigInteger N = BigInteger.valueOf(money.length);
           32  +   while( J>0 ) {
           33  +    Arrays.sort(money);
           34  +
           35  +    BigInteger sum = BigInteger.ZERO;
           36  +    for(int i=0; i<money.length; ++i)
           37  +     sum = sum.add(BigInteger.valueOf(money[i]));
           38  +    long ave = sum.divide(N).add(BigInteger.ONE).longValue();
           39  +
           40  +    long give = ave - money[0];
           41  +    if( J < give )
           42  +     give = J;
           43  +    J -= give;
           44  +    money[0] += give;
           45  +   }
           46  +   Arrays.sort(money);
           47  +   return money;
           48  +  }
           49  + }
           50  +};

Added SRM/504.5/1C.cpp version [1f5d9f15dbb3d7e2]

            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 TheTicketsDivOne { public:
           23  + double find(int n, int m)
           24  + {
           25  +  vector<double> p(1, 1.0);
           26  +  for(int N=2; N<=n; ++N) {
           27  +   vector<double> q(N, 0.0);
           28  +
           29  +   // q[0] = 1/6 + 1/2 q[N-1]
           30  +   // q[i] = 1/2 q[i-1] + 1/3 p[i-1]
           31  +
           32  +   double s = 1.0/6;
           33  +   double f = 1.0/3;
           34  +   for(int i=N-2; i>=0; --i) {
           35  +    f = f/2;
           36  +    s += f*p[i];
           37  +   }
           38  +   q[0] = s / (1.0 - pow(0.5, N));
           39  +   for(int i=1; i<N; ++i)
           40  +    q[i] = q[i-1]/2.0 + p[i-1]/3.0;
           41  +
           42  +   p.swap(q);
           43  +  }
           44  +  return p[m-1];
           45  + }
           46  +};
           47  +
           48  +// BEGIN CUT HERE
           49  +#include <ctime>
           50  +double start_time; string timer()
           51  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           52  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           53  + { os << "{ ";
           54  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           55  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           56  +void verify_case(const double& Expected, const double& Received) {
           57  + bool ok = (abs(Expected - Received) < 1e-9);
           58  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           59  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           60  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           61  +#define END  verify_case(_, TheTicketsDivOne().find(n, m));}
           62  +int main(){
           63  +
           64  +CASE(0)
           65  + int n = 2;
           66  + int m = 1;
           67  + double _ = 0.4444444444444444;
           68  +END
           69  +CASE(1)
           70  + int n = 2;
           71  + int m = 2;
           72  + double _ = 0.5555555555555556;
           73  +END
           74  +CASE(2)
           75  + int n = 1;
           76  + int m = 1;
           77  + double _ = 1.0;
           78  +END
           79  +CASE(3)
           80  + int n = 3;
           81  + int m = 2;
           82  + double _ = 0.31746031746031744;
           83  +END
           84  +CASE(4)
           85  + int n = 1000;
           86  + int m = 500;
           87  + double _ = -1;
           88  +END
           89  +CASE(5)
           90  + int n = 1;
           91  + int m = 1;
           92  + double _ = 1.0;
           93  +END
           94  +CASE(6)
           95  + int n = 1000;
           96  + int m = 1000;
           97  + double _ = -1;
           98  +END
           99  +CASE(7)
          100  + int n = 1000;
          101  + int m = 1;
          102  + double _ = -1;
          103  +END
          104  +
          105  +}
          106  +// END CUT HERE