Communication System-pku 1018

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Communication System-pku 1018

Post by farzane » Sat Dec 22, 2007 4:48 pm

Hello all,
I'm trying to solve this problem:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1018

This problem is here too:
http://acm.tju.edu.cn/toj/showp1258.html

but I got WA every time.
I posted it here, because I have learned many things from this forum before, but I didn't see that websites' forum active.and I really need help.
here is my code:

Code: Select all

#include<iostream>
#include<fstream>

using namespace std;

const int size=200;
struct{
	int minB;
	int sumP;
	double r;
}S[size][size];
int main(){
	ifstream cin("c.in");
	int t,n,i,j,k,m[size],B[size][size],P[size][size],cursum,curmin,maxmin,maxsum;
	double maxR,curR;
	for(cin>>t;t>0;t--){
		cin>>n;
		for(i=0;i<n;i++){
			cin>>m[i];
			for(j=0;j<m[i];j++)
				cin>>B[i][j]>>P[i][j];
			if(!m[i]){i--;n--;}
		}
		for(i=0;i<m[0];i++){
			S[0][i].minB=B[0][i];
			S[0][i].sumP=P[0][i];
			S[0][i].r=double(B[0][i])/double(P[0][i]);
		}
		for(i=1;i<n;i++){//i th device
			for(j=0;j<m[i];j++){//j th factory
				curmin=(S[i-1][0].minB<B[i][j])?S[i-1][0].minB:B[i][j];
				cursum=S[i-1][0].sumP+P[i][j];
				curR=double(curmin)/double(cursum);
				maxR=curR;
				maxmin=curmin;
				maxsum=cursum;
				for(k=1;k<m[i-1];k++){
					curmin=(S[i-1][k].minB<B[i][j])?S[i-1][k].minB:B[i][j];
				    cursum=S[i-1][k].sumP+P[i][j];
				    curR=double(curmin)/double(cursum);
					if(maxR<curR){
						maxR=curR;
						maxmin=curmin;
						maxsum=cursum;
					}
					
				}//k
				S[i][j].minB=maxmin;
				S[i][j].sumP=maxsum;
				S[i][j].r=maxR;
				
			}//j
		}//i

		curmin=S[n-1][0].minB;
		cursum=S[n-1][0].sumP;
		curR=double(curmin)/double(cursum);
		maxR=curR;
		maxmin=curmin;
		maxsum=cursum;
		for(k=1;k<m[n-1];k++){
			curmin=S[n-1][k].minB;
		    cursum=S[n-1][k].sumP;
			curR=double(curmin)/double(cursum);
			if(maxR<curR){
				maxR=curR;
				maxmin=curmin;
				maxsum=cursum;
			}
		}
		printf("%d   %d    %.3f\n",maxmin,maxsum,maxR);
	}
	return 0;
}
where is my mistake? Is it in my alghorithm or implementation?
I used DP.S[j] is the situation when we consider devices 0 to i and select the j th factory for device i.

Please help.It's urgent for me.
If someone could provide me with test data , it would help me too. Maybe I could find my bug.

Thanks in Advanecd

Post Reply

Return to “Other words”