a1523a752e 2013-05-03        kinaba: #include <iostream>
a1523a752e 2013-05-03        kinaba: #include <sstream>
a1523a752e 2013-05-03        kinaba: #include <iomanip>
a1523a752e 2013-05-03        kinaba: #include <vector>
a1523a752e 2013-05-03        kinaba: #include <string>
a1523a752e 2013-05-03        kinaba: #include <map>
a1523a752e 2013-05-03        kinaba: #include <set>
a1523a752e 2013-05-03        kinaba: #include <algorithm>
a1523a752e 2013-05-03        kinaba: #include <numeric>
a1523a752e 2013-05-03        kinaba: #include <iterator>
a1523a752e 2013-05-03        kinaba: #include <functional>
a1523a752e 2013-05-03        kinaba: #include <complex>
a1523a752e 2013-05-03        kinaba: #include <queue>
a1523a752e 2013-05-03        kinaba: #include <stack>
a1523a752e 2013-05-03        kinaba: #include <cmath>
a1523a752e 2013-05-03        kinaba: #include <cassert>
a1523a752e 2013-05-03        kinaba: using namespace std;
a1523a752e 2013-05-03        kinaba: typedef long long LL;
a1523a752e 2013-05-03        kinaba: typedef long double LD;
a1523a752e 2013-05-03        kinaba: typedef complex<LD> CMP;
a1523a752e 2013-05-03        kinaba: 
a1523a752e 2013-05-03        kinaba: class EllysRoomAssignmentsDiv1 { public:
a1523a752e 2013-05-03        kinaba: 	double getAverage(vector <string> ratings)
a1523a752e 2013-05-03        kinaba: 	{
a1523a752e 2013-05-03        kinaba: 		stringstream sin(accumulate(ratings.begin(), ratings.end(), string()));
a1523a752e 2013-05-03        kinaba: 		vector<int> rs;
a1523a752e 2013-05-03        kinaba: 		for(int r; sin>>r; ) rs.push_back(r);
a1523a752e 2013-05-03        kinaba: 
a1523a752e 2013-05-03        kinaba: 		int N = rs.size();
a1523a752e 2013-05-03        kinaba: 		int R = (N%20==0 ? N/20 : N/20+1);
a1523a752e 2013-05-03        kinaba: 		int Elly = rs.front();
a1523a752e 2013-05-03        kinaba: 		sort(rs.rbegin(), rs.rend());
a1523a752e 2013-05-03        kinaba: 		int ei = find(rs.begin(), rs.end(), Elly) - rs.begin();
a1523a752e 2013-05-03        kinaba: 
a1523a752e 2013-05-03        kinaba: 		double exp = 0.0;
a1523a752e 2013-05-03        kinaba: 		for(int r=0,n=0; r<N; r+=R,++n) {
a1523a752e 2013-05-03        kinaba: 			if(r+R<=N) {
a1523a752e 2013-05-03        kinaba: 				// full
a1523a752e 2013-05-03        kinaba: 				if(r<=ei && ei<r+R) {
a1523a752e 2013-05-03        kinaba: 					exp += Elly;
a1523a752e 2013-05-03        kinaba: 				} else {
a1523a752e 2013-05-03        kinaba: 					exp += accumulate(rs.begin()+r, rs.begin()+r+R, 0.0) / R;
a1523a752e 2013-05-03        kinaba: 				}
a1523a752e 2013-05-03        kinaba: 				if(r+R>=N) {
a1523a752e 2013-05-03        kinaba: 					return exp / (n+1);
a1523a752e 2013-05-03        kinaba: 				}
a1523a752e 2013-05-03        kinaba: 			} else {
a1523a752e 2013-05-03        kinaba: 				// partial
a1523a752e 2013-05-03        kinaba: 				int K = N-r;
a1523a752e 2013-05-03        kinaba: 				double pL = double(K)/R;
a1523a752e 2013-05-03        kinaba: 				if(r<=ei && ei<r+R) {
a1523a752e 2013-05-03        kinaba: 					exp += Elly;
a1523a752e 2013-05-03        kinaba: 					return exp / (n+1);
a1523a752e 2013-05-03        kinaba: 				} else {
a1523a752e 2013-05-03        kinaba: 					double aveLast = accumulate(rs.begin()+r, rs.end(), 0.0) / K;
a1523a752e 2013-05-03        kinaba: 					return (exp+aveLast)/(n+1)*pL + (exp)/n*(1-pL);
a1523a752e 2013-05-03        kinaba: 				}
a1523a752e 2013-05-03        kinaba: 			}
a1523a752e 2013-05-03        kinaba: 		}
a1523a752e 2013-05-03        kinaba: 		return -1;
a1523a752e 2013-05-03        kinaba: 	}
a1523a752e 2013-05-03        kinaba: };
a1523a752e 2013-05-03        kinaba: 
a1523a752e 2013-05-03        kinaba: // BEGIN CUT HERE
a1523a752e 2013-05-03        kinaba: #include <ctime>
a1523a752e 2013-05-03        kinaba: double start_time; string timer()
a1523a752e 2013-05-03        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
a1523a752e 2013-05-03        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
a1523a752e 2013-05-03        kinaba:  { os << "{ ";
a1523a752e 2013-05-03        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
a1523a752e 2013-05-03        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
a1523a752e 2013-05-03        kinaba: void verify_case(const double& Expected, const double& Received) {
a1523a752e 2013-05-03        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
a1523a752e 2013-05-03        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
a1523a752e 2013-05-03        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
a1523a752e 2013-05-03        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
a1523a752e 2013-05-03        kinaba: #define END	 verify_case(_, EllysRoomAssignmentsDiv1().getAverage(ratings));}
a1523a752e 2013-05-03        kinaba: int main(){
a1523a752e 2013-05-03        kinaba: 
a1523a752e 2013-05-03        kinaba: CASE(0)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = {"1924 1242 1213 1217 2399 1777 2201 2301 1683 2045 ", "1396 2363 1560 2185 1496 2244 2117 2207 2098 1319 ",
a1523a752e 2013-05-03        kinaba:  "2216 1223 1256 2359 2394 1572 2151 2191 2147 2253 ", "1633 2217 2211 1591 1310 1209 1430 1445 1988 2030 ",
a1523a752e 2013-05-03        kinaba:  "1947 1202 1203"};
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = 1821.3291005291007;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: CASE(1)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = {"3380 3413 3254 3515 2885 2946 2790 3140"};
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = 3165.375;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: CASE(2)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = {"2367 1395 1639 1842 1426 2393 2348 1571 2077 12", "2", "2 1966 1495 13",
a1523a752e 2013-05-03        kinaba:  "09 1251 3039 1566 1989 2083 1819 1875 ", "1579 2206 1503 1461 2262 2116 1429 2150 1834 2097 ",
a1523a752e 2013-05-03        kinaba:  "2093 1518 1923 1796 1669 2342 1826 2374 1635 1683 ", "1656 2190 1632 1946 1207 1293 2029 2243 2252 1559 ",
a1523a752e 2013-05-03        kinaba:  "2366 1590 1563 2319 1391 1255 1727 1565 1911 1679 ", "1282 2358 1682 2148 3555 2362 1208 2044 1949 1980 ",
a1523a752e 2013-05-03        kinaba:  "1983 2215 2184 1545 1665 2146 1272 2110 1889 1829 ", "1808 2065 1987 1297 2216 1609 1318 1816 1444 20", "00 1404"};
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = 1824.662456140351;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: CASE(3)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = {"2869 3239 1609 2367 1836 1663 1697 2317 1475 2212 ", "2188 2073 1263 1391 1495 3010 1243 2198 1782 1564 ",
a1523a752e 2013-05-03        kinaba: "3594 1219 2037 1473 1624 1435 2159 2315 2056 3029 ", "1863 1297 2245 3206 3510 1728 1246 1230 1875 3511 ",
a1523a752e 2013-05-03        kinaba: "1241 2775 1255 2304 2013 1205 2070 2763 1518 2344 ", "1690 1398 2320 1912 2752 2155 1778 1644 2230 3026 ",
a1523a752e 2013-05-03        kinaba: "1817 1401 1962 1470 1387 2339 3443 1510 2094 2374 ", "1273 1664 2853 1907 2380 3265 2786 1298 1983 1899 ",
a1523a752e 2013-05-03        kinaba: "1507 3252 2176 1452 1261 1981 1570 1207 2107 3550 ", "1282 3331 1254 2276 2096 1716 1966 3389 1766 2068 ",
a1523a752e 2013-05-03        kinaba: "3006 1802 1698 1555 1971 1509 1531 1556 2044 2358 ", "2327 2241 3182 2152 1514 2219 1559 1895 1992 2046 ",
a1523a752e 2013-05-03        kinaba: "1200 1915 1930 2296 1859 1501 1960 1683 1222 1288 ", "1808 1360 2177 2711 1286 1562 2078 1801 1834 2808 ",
a1523a752e 2013-05-03        kinaba: "1948 1674 1305 3031 2160 2252 1613 1621 2345 1850 ", "2169 2106 1918 1309 1317 1417 1670 2733 1946 1844 ",
a1523a752e 2013-05-03        kinaba: "1774 1956 1355 1336 1300 1349 2283 1247 3258 3415 ", "2795 1978 1990 1394 2347 1337 1340 1503 1722 3528 ",
a1523a752e 2013-05-03        kinaba: "2139 2968 2257 1312 2148 2166 1460 2216 1632 1325 ", "1404 1878 2197 1524 2030 1438 1973 1444 2191 1606 ",
a1523a752e 2013-05-03        kinaba: "3390 1866 1688 1779 3027 2254 1582 2123 3105 1568 ", "2036 1579 2995 1591 1933 1382 1596 2364 3310 1856 ",
a1523a752e 2013-05-03        kinaba: "3427 1816 1344 1304 3269 1906 1646 1480 2040 1725 ", "2766 1496 1265 2050 1842 2341 1367 1679 1202 1546 ",
a1523a752e 2013-05-03        kinaba: "2300 1936 2224 1846 2987 2248 1657 2907 1958 1853 ", "3326 1943 3336 2801 2839 2357 1819 2266 1727 2200 ",
a1523a752e 2013-05-03        kinaba: "2385 1904 1323 1710 1796 1594 2262 2798 1952 2292 ", "2204 1916 3572 1477 1280 1961 1270 1250 2000 2089 ",
a1523a752e 2013-05-03        kinaba: "3584 1612 1873 1451 2004 3174 1251 3011 3474 2386 ", "1330 1758 1271 3540 1497 1284 1839 2383 1489 2326 ",
a1523a752e 2013-05-03        kinaba: "2822 2124 2307 1313 3263 1804 2001 1338 2161 1303 ", "2016 1488 2015 1558 1522 2267 1567 1676 2221 1201 ",
a1523a752e 2013-05-03        kinaba: "1576 1711 1887 2228 1539 1227 2392 2109 1616 2183 ", "2362 2784 2057 1411 1318 2097 1208 1672 1379 1339 ",
a1523a752e 2013-05-03        kinaba: "1545 1461 3370 1369 1763 1425 1322 1897 1395 1209 ", "1665 2373 1645 1447 2393 1426 1293 1508 2049 2378 ",
a1523a752e 2013-05-03        kinaba: "2234 1879 1949 1266 1849 3164 1260 2181 1611 1935 ", "1348 2021 3332 1820 1316 2261 3077 3328 1892 1324 ",
a1523a752e 2013-05-03        kinaba: "2035 3251 1893 1910 1474 1557 2923 2024 2196 1571 ", "1980 2072 1924 2017 1770 2240 1659 3195 1486 3122 ",
a1523a752e 2013-05-03        kinaba: "1341 1521 1890 1419 3229 1977 2366 1267 3458 2210 ", "2157 1523 1399 2146 1228 1415 1256 1642 1687 2184 ",
a1523a752e 2013-05-03        kinaba: "1865 3089 3581 1429 2313 1352 1272 2285 1390 2209 ", "1785 1449 1295 1410 1239 1416 2354 1281 1840 2265 ",
a1523a752e 2013-05-03        kinaba: "2330 3295 1353 1423 1204 2150 2116 3588 1908 1976 ", "2233 1923 1635 1825 1469 2251 1792 1249 2125 2100 ",
a1523a752e 2013-05-03        kinaba: "1833 2281 2142 2093 1920 2144 1565 1590 2826 3045 ", "3475 1911 1695 2067 1634 2319 1376 2348 1529 1682"};
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = 1985.7041666666669;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: CASE(4)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = {"1298 2272 2618 1344 3020 3212 3419 1754 3571 2835 ", "3049 2893 1970 3006 3244 3451 3273 2039 3826 2199 ", "3159"};
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = 2670.4545454545455;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: /*
a1523a752e 2013-05-03        kinaba: CASE(5)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = ;
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = ;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: CASE(6)
a1523a752e 2013-05-03        kinaba: 	string ratings_[] = ;
a1523a752e 2013-05-03        kinaba: 	  vector <string> ratings(ratings_, ratings_+sizeof(ratings_)/sizeof(*ratings_));
a1523a752e 2013-05-03        kinaba: 	double _ = ;
a1523a752e 2013-05-03        kinaba: END
a1523a752e 2013-05-03        kinaba: */
a1523a752e 2013-05-03        kinaba: }
a1523a752e 2013-05-03        kinaba: // END CUT HERE