Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
La idea es basicamente greedy, tomar el mayor disponible y los n menores necesarios
para completar el peso minimo requerido de 50
**/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
int t, n, c, r;
int top, bottom;
int main(){
c = 1;
scanf("%d", &t);
while(t--){
vi W;
scanf("%d", &n);
while(n--){
int aux;
scanf("%d", &aux);
W.push_back(aux);
}
sort(W.begin(), W.end());
r = 0;
top = W.size() -1;
bottom = 0;
while(true){
int maxi = W[top];
int wN = maxi >= 50 ? 0 : 50 / maxi;
bottom += wN;
if( top == bottom ) {
r++;
break;
}
if( bottom > top)
break;
top--;
r++;
}
printf("Case #%d: %d\n", c,r);
c++;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.