SHARE
TWEET

Uva 11658 — Best Coalitions

a guest Dec 14th, 2018 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int , int> pi;
  6. typedef pair<double , int > dpi;
  7. typedef pair<long long , long long> pll;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef vector<pi> vpi;
  11. typedef unsigned long long ull;
  12. #define sc(a) scanf("%d",&a)
  13. #define scl(a) scanf("%lld",&a)
  14. #define scd(a) scanf("%lf" , &a)
  15. #define sch(a) scanf("%c" , &a)
  16. #define blank printf("\n")
  17. #define pla printf("plapla\n")
  18. #define pb push_back
  19. const int MAX = 1e5+55;
  20. const int inf = 1e9+77;
  21. const int MOD = 1e9+7;
  22. const double PI = 3.14159265359;
  23. const double eps = 1e-7;
  24.  
  25. int n , x;
  26. int a[150];
  27. int dp[105][10005];
  28. int solve(int id , int sum){
  29.     if(id == n){
  30.         if(sum > 5000)
  31.             return 0;
  32.         return inf;
  33.     }
  34.     int &res = dp[id][sum];
  35.     if(res != -1)
  36.         return res;
  37.     res = inf;
  38.     if(id != x - 1)
  39.         res = min(res , solve(id + 1 , sum));
  40.     res = min(res , solve(id + 1 , sum + a[id]) + a[id]);
  41.     return res;
  42. }
  43.  
  44.  
  45. int main(){
  46. //freopen("output.txt" , "w" , stdout);
  47. //freopen("input.txt" , "r" , stdin);
  48.  
  49.  
  50. while(1){
  51. memset(dp , -1 , sizeof(dp));
  52.  
  53.     sc(n);sc(x);
  54.     if(!n && !x)
  55.         break;
  56.     double d;
  57.     for(int i = 0 ; i < n ; ++i){
  58.         int r , b;
  59.         scanf("%d.%d" , &r , &b);
  60.         a[i] = r * 100 + b;
  61.     }
  62.     double ans;
  63.     if(a[x-1] > 5000)
  64.         ans = 100.00;
  65.     else{
  66.         int res = solve(0 , 0);
  67.         ans = (1.0 * a[x-1] * 100.0) / res;
  68.     }
  69.     printf("%.2f\n" , ans);
  70. }
  71.  
  72.  
  73.  
  74. return 0;
  75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top