11658 - Best Coalitions

[LucasSchm]

I tried a recursive/backtracking solution but with the time limit of 1sec i get TLE. So any hints of how to solve it without recrusion?

Thanks.

[saiful_sust]

I also try this with backtrck .......

Some PLZ tell me how to solve this.....
some hints needed...........

[Igor9669]

It is a standart dp problem!
Don't use double, int is enough here!!

[Jehad Uddin]

i used DP bt got WA, pls Help...
Here is my code,

Code: Select all

#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;


bool v[10005];

int no[200],n;

int parse(string str)
{
   int i,j,k,l;
   j=0;
   for(i=0;i<str.length()&&str[i]!='.';i++)
   j=j*10+str[i]-48;
   j=j*100;
   if(i<str.length()&&str[i]=='.') i++;
   for(k=0,l=0;i<str.length();i++,k++)
   l=l*10+str[i]-48;
   if(k<2) l=l*10;
   j+=l;
   return j;

}

int main()
{
    
    int x,i,j,k,m;
    double s;
    string str;
    while(cin>>n>>x)
    {
       if(n==0&&x==0) break;
       for(i=1,j=0;i<=n;i++)
       {
          cin>>str;
          k=parse(str);
          if(x==i) m=k;
          else no[j++]=k;
       }
       
       sort(no,no+j);
      
       if(m>=5000) cout<<"100.00"<<endl;
       else
       {
           memset(v,0,sizeof(v));
           v[0]=true;
           for(i=0;i<j;i++)
           {
               
               for(k=5000;k>=1;k--)
               if(!v[k])
               {
                   if(no[i]<=k)
                   {
                       v[k]=v[k-no[i]];
                       
                   }
                   else v[k]=false;
                   

               }
           }
       
          for(k=5000;k>=1;k--)
          if(v[k]) break;
          
          s=double(m)/double(10000-k);
          s=s*100.0;
          printf("%.2lf\n",s);
          
       }
    
    
    
    }    
    
    
    
    
    return 0;
}

[LucasSchm]

i used DP bt got WA, pls Help...
Here is my code,

Code: Select all

#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;


bool v[10005];

int no[200],n;

int parse(string str)
{
   int i,j,k,l;
   j=0;
   for(i=0;i<str.length()&&str[i]!='.';i++)
   j=j*10+str[i]-48;
   j=j*100;
   if(i<str.length()&&str[i]=='.') i++;
   for(k=0,l=0;i<str.length();i++,k++)
   l=l*10+str[i]-48;
   if(k<2) l=l*10;
   j+=l;
   return j;

}

int main()
{
    
    int x,i,j,k,m;
    double s;
    string str;
    while(cin>>n>>x)
    {
       if(n==0&&x==0) break;
       for(i=1,j=0;i<=n;i++)
       {
          cin>>str;
          k=parse(str);
          if(x==i) m=k;
          else no[j++]=k;
       }
       
       sort(no,no+j);
      
       if(m>=5000) cout<<"100.00"<<endl;
       else
       {
           memset(v,0,sizeof(v));
           v[0]=true;
           for(i=0;i<j;i++)
           {
               
               for(k=5000;k>=1;k--)
               if(!v[k])
               {
                   if(no[i]<=k)
                   {
                       v[k]=v[k-no[i]];
                       
                   }
                   else v[k]=false;
                   

               }
           }
       
          for(k=5000;k>=1;k--)
          if(v[k]) break;
          
          s=double(m)/double(10000-k);
          s=s*100.0;
          printf("%.2lf\n",s);
          
       }
    
    
    
    }    
    
    
    
    
    return 0;
}

Try this one:

Code: Select all

4 4
25.00
25.00
25.00
25.00

My ACC:

Code: Select all

33.33

[Jehad Uddin]

thank you

Code: Select all

code removed got acc.

[razor]

I used dp knapsack, but why wa?

Code: Select all

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <algorithm>

#define FOR(i, a, b) for(int i = int(a); i < int(b); i++)
#define sz(a) int((a).size())
#define tr(c, i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(c) (c).begin(),(c).end()
#define INF 2000000000
#define EPS 1e-5
#define PB push_back
#define MP make_pair
#define S second
#define F first
#define X first
#define Y second
#define DEBUG(x) printf("debugging.. %d\n", x);
using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

int n, x, a[105];
bool can[100005];

int main() {
	while(true) {
		scanf("%d%d", &n, &x);
		
		if(n == 0 && x == 0) break;
		
		int col, id = 0;
		for(int i = 0; i < n; ++i) {
			int ta, tb;
			scanf("%d.%d", &ta, &tb);
			
			if(i == x-1) { col = ta*100 + tb; continue; }
			
			a[id++] = ta*100 + tb;
		}
		
		memset(can, 0, sizeof(can));
		can[0] = 1;
		
		int sum = 0;
		for(int i = 0; i < id; ++i) {
			for(int j = 0; j <= sum; ++j)
				if(can[j] && j + a[i] <= 10000)
					can[j+a[i]] = 1;
					
			sum += a[i];
		}
		
		int mi = INF;
		for(int i = 0; i <= 10000; ++i)
			if(can[i] && col + i > 5000)
				mi = min(mi, col + i);
				
		double ans = ((double) col)/((double) mi) * 100.0;
		printf("%.2lf\n", ans);
	}
	
	return 0;
}

[lamphanviet]

To someone who got WA for this problem, try using scanf("%d.%d", ..) instead of scanf("%lf", ..).