Advertisement
Guest User

Untitled

a guest
May 5th, 2014
301
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //test data:
  2. // 8 80.0 1.0
  3. // 7 1 6 3 4 5 6 5
  4. // 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
  5. //output:
  6. // 0.706194
  7. // 5 6 5 4 3 1 6 7
  8. // 0.8 0.7 0.6 0.5 0.4 0.2 0.3 0.1
  9.  
  10. #include <iostream>
  11. #include <algorithm>
  12. using namespace std;
  13.  
  14. // will work bad for cnt > 10 because 10! = 3628800
  15. int perm[] = {0,1,2,3,4,5,6,7,8,9};
  16. int bestPerm[10];
  17. double sizes[10], L[10];
  18.  
  19. double calc(int cnt, double M, double K, double T) {
  20.     double res = 0.0, usedMemory = 0.0;
  21.     for(int i = 0; i < cnt; i++) {
  22.         int ind = perm[i];
  23.         res += K * sizes[ind] / (M - L[ind] * usedMemory - (T - usedMemory));
  24.         usedMemory += sizes[ind];
  25.     }
  26.     return res;
  27. }
  28.  
  29. int main() {
  30.     int cnt;
  31.     double M,K,T = 0.0;
  32.     cin >> cnt >> M >> K;
  33.     for(int i = 0; i < cnt; i++)
  34.         cin >> sizes[i], T += sizes[i];
  35.     for(int i = 0; i < cnt; i++)
  36.         cin >> L[i];
  37.  
  38.     double bruteRes = 1e16;
  39.     int bruteCnt = 1;
  40.     for(int i = 2; i <= cnt; i++)
  41.         bruteCnt *= i;
  42.     for(int i = 0; i < bruteCnt; i++) {
  43.         double curRes = calc(cnt, M, K, T);
  44.         if( bruteRes > curRes ) {
  45.             bruteRes = curRes;
  46.             for(int j = 0; j < cnt; j++)
  47.                 bestPerm[j] = perm[j];
  48.         }
  49.         next_permutation(perm, perm + cnt);
  50.     }
  51.     cout << bruteRes << "\n";
  52.     for(int i = 0; i < cnt; i++)
  53.         cout << sizes[bestPerm[i]] << " ";
  54.     cout << "\n";
  55.     for(int i = 0; i < cnt; i++)
  56.         cout << L[bestPerm[i]] << " ";
  57.     cout << "\n";
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement