Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on May 6th, 2012  |  syntax: None  |  size: 1.42 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <vector>
  2. #include <map>
  3. #include <set>
  4. #include <queue>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <sstream>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <cstdio>
  11. #include <cmath>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <ctime>
  15. using namespace std;
  16. #define DB(x) { cerr << #x << ": " << x << " "; }
  17. #define forn(i, n)  for (int i = 0; i < (int)(n); ++i)
  18. #define sqr(x) ((x)*(x))
  19. typedef long double ld;
  20. typedef long long ll;
  21. typedef vector <int> vi;
  22. typedef pair <int,int> pii;
  23. const ld PI = acos(-1.0);
  24.  
  25. const int N = 1010;
  26. int n, k;
  27. double prices[N], disc[N], c[N][N];
  28.  
  29. void precalc() {
  30.     forn(i, N) {
  31.         c[i][0] = c[i][i] = 1;
  32.         for (int j = 1; j < i; j++)
  33.             c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  34.     }
  35. }
  36.  
  37. void solve() {
  38.     cin >> n >> k;
  39.     forn(i, n) cin >> prices[i];
  40.     sort(prices, prices + n);
  41.     forn(i, k) cin >> disc[i];
  42.     sort(disc, disc + k);
  43.     double res = 0;
  44.     forn(i, n) forn(j, k) {
  45.         if (j > i) continue;
  46.         if (k - j > n - i) continue;
  47.         double add = c[i][j] * c[n - i - 1][k - j - 1] * disc[j] * prices[i];
  48.         res += add;
  49.         //cerr << i << " " << j << " " << add << endl;
  50.     }
  51.     res /= c[n][k] * 100;
  52.     cout << fixed << setprecision(3) << res << endl;
  53. }
  54.  
  55. int main() {
  56.   //freopen("in", "r", stdin);
  57.   //freopen("out", "w", stdout);
  58.   ios_base::sync_with_stdio(0);
  59.  
  60.     precalc();
  61.     int T; cin >> T; forn(t, T) solve();
  62.   return 0;
  63. }