Overview
| SHA1 Hash: | 1535d63ceac6053603d576c44e4280b18871623e |
|---|---|
| Date: | 2011-05-28 15:39:07 |
| User: | kinaba |
| Comment: | 504.5 |
| 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/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) > 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 > 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() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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< > 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).lon > 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) > 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 > 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() > 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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