Overview
| SHA1 Hash: | a1523a752e60c98805eabf747fd39a65d823afd3 |
|---|---|
| Date: | 2013-05-03 00:20:47 |
| User: | kinaba |
| Comment: | 577 |
| 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/577-U/1A.cpp version [6c2e3d110add41a2]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class EllysRoomAssignmentsDiv1 { public: > 23 double getAverage(vector <string> ratings) > 24 { > 25 stringstream sin(accumulate(ratings.begin(), ratings.end(), stri > 26 vector<int> rs; > 27 for(int r; sin>>r; ) rs.push_back(r); > 28 > 29 int N = rs.size(); > 30 int R = (N%20==0 ? N/20 : N/20+1); > 31 int Elly = rs.front(); > 32 sort(rs.rbegin(), rs.rend()); > 33 int ei = find(rs.begin(), rs.end(), Elly) - rs.begin(); > 34 > 35 double exp = 0.0; > 36 for(int r=0,n=0; r<N; r+=R,++n) { > 37 if(r+R<=N) { > 38 // full > 39 if(r<=ei && ei<r+R) { > 40 exp += Elly; > 41 } else { > 42 exp += accumulate(rs.begin()+r, rs.begin > 43 } > 44 if(r+R>=N) { > 45 return exp / (n+1); > 46 } > 47 } else { > 48 // partial > 49 int K = N-r; > 50 double pL = double(K)/R; > 51 if(r<=ei && ei<r+R) { > 52 exp += Elly; > 53 return exp / (n+1); > 54 } else { > 55 double aveLast = accumulate(rs.begin()+r > 56 return (exp+aveLast)/(n+1)*pL + (exp)/n* > 57 } > 58 } > 59 } > 60 return -1; > 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 double& Expected, const double& Received) { > 73 bool ok = (abs(Expected - Received) < 1e-9); > 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(_, EllysRoomAssignmentsDiv1().getAverage(ratings)); > 78 int main(){ > 79 > 80 CASE(0) > 81 string ratings_[] = {"1924 1242 1213 1217 2399 1777 2201 2301 1683 2045 > 82 "2216 1223 1256 2359 2394 1572 2151 2191 2147 2253 ", "1633 2217 2211 1591 1310 > 83 "1947 1202 1203"}; > 84 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 85 double _ = 1821.3291005291007; > 86 END > 87 CASE(1) > 88 string ratings_[] = {"3380 3413 3254 3515 2885 2946 2790 3140"}; > 89 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 90 double _ = 3165.375; > 91 END > 92 CASE(2) > 93 string ratings_[] = {"2367 1395 1639 1842 1426 2393 2348 1571 2077 12", > 94 "09 1251 3039 1566 1989 2083 1819 1875 ", "1579 2206 1503 1461 2262 2116 1429 2 > 95 "2093 1518 1923 1796 1669 2342 1826 2374 1635 1683 ", "1656 2190 1632 1946 1207 > 96 "2366 1590 1563 2319 1391 1255 1727 1565 1911 1679 ", "1282 2358 1682 2148 3555 > 97 "1983 2215 2184 1545 1665 2146 1272 2110 1889 1829 ", "1808 2065 1987 1297 2216 > 98 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 99 double _ = 1824.662456140351; > 100 END > 101 CASE(3) > 102 string ratings_[] = {"2869 3239 1609 2367 1836 1663 1697 2317 1475 2212 > 103 "3594 1219 2037 1473 1624 1435 2159 2315 2056 3029 ", "1863 1297 2245 3206 3510 > 104 "1241 2775 1255 2304 2013 1205 2070 2763 1518 2344 ", "1690 1398 2320 1912 2752 > 105 "1817 1401 1962 1470 1387 2339 3443 1510 2094 2374 ", "1273 1664 2853 1907 2380 > 106 "1507 3252 2176 1452 1261 1981 1570 1207 2107 3550 ", "1282 3331 1254 2276 2096 > 107 "3006 1802 1698 1555 1971 1509 1531 1556 2044 2358 ", "2327 2241 3182 2152 1514 > 108 "1200 1915 1930 2296 1859 1501 1960 1683 1222 1288 ", "1808 1360 2177 2711 1286 > 109 "1948 1674 1305 3031 2160 2252 1613 1621 2345 1850 ", "2169 2106 1918 1309 1317 > 110 "1774 1956 1355 1336 1300 1349 2283 1247 3258 3415 ", "2795 1978 1990 1394 2347 > 111 "2139 2968 2257 1312 2148 2166 1460 2216 1632 1325 ", "1404 1878 2197 1524 2030 > 112 "3390 1866 1688 1779 3027 2254 1582 2123 3105 1568 ", "2036 1579 2995 1591 1933 > 113 "3427 1816 1344 1304 3269 1906 1646 1480 2040 1725 ", "2766 1496 1265 2050 1842 > 114 "2300 1936 2224 1846 2987 2248 1657 2907 1958 1853 ", "3326 1943 3336 2801 2839 > 115 "2385 1904 1323 1710 1796 1594 2262 2798 1952 2292 ", "2204 1916 3572 1477 1280 > 116 "3584 1612 1873 1451 2004 3174 1251 3011 3474 2386 ", "1330 1758 1271 3540 1497 > 117 "2822 2124 2307 1313 3263 1804 2001 1338 2161 1303 ", "2016 1488 2015 1558 1522 > 118 "1576 1711 1887 2228 1539 1227 2392 2109 1616 2183 ", "2362 2784 2057 1411 1318 > 119 "1545 1461 3370 1369 1763 1425 1322 1897 1395 1209 ", "1665 2373 1645 1447 2393 > 120 "2234 1879 1949 1266 1849 3164 1260 2181 1611 1935 ", "1348 2021 3332 1820 1316 > 121 "2035 3251 1893 1910 1474 1557 2923 2024 2196 1571 ", "1980 2072 1924 2017 1770 > 122 "1341 1521 1890 1419 3229 1977 2366 1267 3458 2210 ", "2157 1523 1399 2146 1228 > 123 "1865 3089 3581 1429 2313 1352 1272 2285 1390 2209 ", "1785 1449 1295 1410 1239 > 124 "2330 3295 1353 1423 1204 2150 2116 3588 1908 1976 ", "2233 1923 1635 1825 1469 > 125 "1833 2281 2142 2093 1920 2144 1565 1590 2826 3045 ", "3475 1911 1695 2067 1634 > 126 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 127 double _ = 1985.7041666666669; > 128 END > 129 CASE(4) > 130 string ratings_[] = {"1298 2272 2618 1344 3020 3212 3419 1754 3571 2835 > 131 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 132 double _ = 2670.4545454545455; > 133 END > 134 /* > 135 CASE(5) > 136 string ratings_[] = ; > 137 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 138 double _ = ; > 139 END > 140 CASE(6) > 141 string ratings_[] = ; > 142 vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ra > 143 double _ = ; > 144 END > 145 */ > 146 } > 147 // END CUT HERE