Advertisement
Guest User

asdfas

a guest
Sep 28th, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <climits>
  3. #include <limits>
  4. #include <stdlib.h>
  5. #include <math.h>
  6. #include <string.h>
  7. #include <iostream>
  8. #include <fstream>
  9. #include <algorithm>
  10. #include <map>
  11. #include <vector>
  12. #include <set>
  13. #include <queue>
  14.  
  15. long double meals[105];
  16. long double a, b;
  17. long long int cases, size;
  18.  
  19. using namespace std;
  20. int gcd(long long int x, long long int y) { return y ? gcd(y, x % y) : abs(x); }
  21.  
  22. int main()
  23. {
  24.     while(true) {
  25.         cin >> size;
  26.         if(size == 0) break;
  27.         cin >> a;
  28.         cin >> b;
  29.  
  30.         memset(meals, 0x00, sizeof(long double)*105);
  31.         for(long long int i = 0; i < size; i++) {
  32.             long long int meal;
  33.             cin >> meal;
  34.             meals[meal]++;
  35.         }
  36.  
  37.         long double minsum = -1;
  38.         long long int minden, minnum;
  39.         long long int minsden, minsnum;
  40.         long long int cden, cnum;
  41.         for(long long int inum = 1; inum <= 100; inum++) {
  42.             for(long long int iden = 1; iden <= inum; iden++) {
  43.                 long double plate = ((long double)inum) / ((long double)iden);
  44.                 long double sum = 0;
  45.                 long long int snum = 1;
  46.                 long long int sden = 1;
  47.                 for(long long int meal = 1; meal <= 100; meal++) {
  48.                     if(meals[meal] == 0) continue;
  49.                     if(ceil(meal/plate) > 3) {
  50.                         sum = minsum;
  51.                         break;
  52.                     }
  53.                     long double cost = b*ceil(meal/plate) + max((long double) 0.0,a*(ceil(meal/plate)*plate - meal));
  54.                     long long int cnum = b*ceil(meal/plate)*iden;
  55.                     long long int waste = a*(ceil(meal/plate)*inum - meal*iden);
  56.                     if(waste > 0) cnum += waste;
  57.                     long long int cden = iden;
  58.  
  59.                     snum = (sden*cnum + cden*snum)*meals[meal];
  60.                     sden = sden*cden;
  61.                     sum += cost*meals[meal];
  62.                 }
  63.                 if(sum < minsum || minsum < 0) {
  64.                     minsum = sum;
  65.                     minnum = inum;
  66.                     minden = iden;
  67.                     minsnum = snum;
  68.                     minsden = sden;
  69.                 }
  70.             }
  71.         }
  72.         minsnum -= minsden;
  73.         int g = gcd(minsnum, minsden);
  74.         minsnum = minsnum / g;
  75.         minsden = minsden / g;
  76.  
  77.         if(minsden == 1) {
  78.             printf("%lld\n", minsnum);
  79.         } else {
  80.             printf("%lld / %lld\n", minsnum, minsden);
  81.         }
  82.     }
  83.  
  84.    
  85.   return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement