## 11658 - Best Coalitions

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### 11658 - Best Coalitions

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11658 - Best Coalitions

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

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

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11658 - Best Coalitions

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

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11658 - Best Coalitions

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
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 11658 - Best Coalitions

Jehad Uddin wrote: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
``````

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11658 - Best Coalitions

thank you

Code: Select all

``````code removed got acc.
``````

razor
New poster
Posts: 3
Joined: Wed Oct 19, 2011 6:48 pm

### Why WA?

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
New poster
Posts: 3
Joined: Tue Oct 12, 2010 7:50 am

### Re: 11658 - Best Coalitions

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