410 - Station Balance

[sohel]

Have you looked at the discussions of this thread - http://acm.uva.es/board/viewtopic.php?f ... 36&start=0
.. and don't create a new thread for a problem that already exists.

[Mehadi]

Got Accepted.
Thnaks Jan

[behdad]

I test all the test cases I found here and all of them are right.
it's my code, it's make me happy if you can find any problem

Code: Select all

#include<iostream>
#include<fstream>
#include<math.h>
#include<string>
#include<algorithm>
#include <iomanip>

using namespace std;

int main()
{
	int n=0;
	int m=0;
	int c=1;

	while(cin>>n){

		cin>>m;
		int i=0;
		int arr[22]={0};
		long double all=0;
	
		for(i=0;i<m;i++){
			cin>>arr[i];
			all+=arr[i];
		}
		sort(arr,arr+m);

		int ar[22][2]={0};

		if(m%2==0){
			for(i=0;i<n;i++){
				ar[i%n][0]=arr[i];
			}
			for(;i<m;i++){
				ar[n-(i%n)-1][1]=arr[i];
			}
		}
		else{
			for(i=0;i<n-1;i++){
				ar[i%n][0]=arr[i];
			}
			for(;i<m-1;i++){
				ar[n-((i+1)%n)-2][1]=arr[i];
			}
			ar[n-1][0]=arr[m-1];
		}
		cout<<"Set #"<<c<<endl;

		for(i=0;i<n;i++){
			cout<<" "<<i<<": ";
			if(ar[i][0]!=0)
				cout<<ar[i][0]<<" ";
			if(ar[i][1]!=0)
				cout<<ar[i][1];
			cout<<endl;
		}

		long double sum=0;
		long double av=all/n;


		for(i=0;i<n;i++){
			long double re = ar[i][0]+ar[i][1]-av;
			if(re<0)
				sum+=((-1)*re);
			else
				sum+=re;
		}

		cout<<"IMBALANCE = "<< setiosflags(ios::fixed) << setprecision(5) << sum<<endl;


		c++;
	}

	return 0;
}

[mmfrb]

Code: Select all

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int c, s, specimens[10], a, chamberNumber;
int last, init;
double media, imbalance, c1, a1, actual;



int main()
{
	int cases = 0;
	while(scanf("%d %d", &c, &s) == 2)
	{
		if(cases) printf("\n");
		a = 0;
		imbalance = 0;
		chamberNumber = 0;
		for(int i = 0; i < s; ++i)
		{
			scanf("%d", &specimens[i]);
			a += specimens[i];
		}
		a1 = a; c1 = c;
		media = a1/c1;
		last = 2*c;
		for(int i = s; i < last; ++i) specimens[i] = 0;
		sort(specimens, specimens+last);
		init = 0; last--;
		printf("Set #%d\n", ++cases);
		while(last - init >= 1)
		{
			printf(" %d:", chamberNumber++);
			actual = fabs(specimens[init] + specimens[last] - media);
			if(specimens[last]) printf(" %d", specimens[last]);
			if(specimens[init]) printf(" %d", specimens[init]);
			printf("\n");
			imbalance += actual;
			init++;
			last--;
		}
		printf("IMBALANCE = %.5lf\n", imbalance);
	}
	return 0;
}

Why PE? Pleaseee help me

[brianfry713]

The final line of output for each set should be a blank line. (Follow the sample output format.)
Print an extra newline at the end of the output.

[anieli]

Hi, everyone...

I need some help with my submission, because it's return "time limit exceed"

Here's my code, in Java:

Code: Select all

import java.text.DecimalFormat;
import java.util.*;

public class Main
{
	public static void main(String[] args) [code]

{
Scanner scan = new Scanner(System.in);
int test = 0;
while (scan.hasNext())
{
int c,s;
test++;
c = scan.nextInt();
s = scan.nextInt();

int i,j;
int zeros=2*c-s;
int[] a = new int[zeros+s];
for (i=0;i<zeros;i++) a=0;
s=s+zeros;

for (j=i;j<s;j++)
{
a[j] = scan.nextInt();
}

Arrays.sort(a);

int[][] ans = new int[c][2];

for (int is=0;is<s/2;is++)
{
ans[is][0]=a[is];
ans[is][1]=a[s-is-1];

}

System.out.printf("Set #%d\n",test);
for(i=0;i<c;i++)
{
System.out.printf("%d:",i);
if(ans[0]!=0)
{
System.out.printf(" %d %d\n",ans[0],ans[1]);
}
else if(ans[1]!=0)
{
System.out.printf(" %d\n",ans[1]);
}
else {
System.out.printf("\n");
}
}
double wq,imbalance;
imbalance=0;
wq=0;
for (i=0;i<s;i++) wq=wq+a;
wq=wq/(c);
double x=0;
for (i=0;i<c;i++)
{
x=ans[0]+ans[1]-wq;
if(x<0)
x=x*(-1);
imbalance=imbalance+x;
}
DecimalFormat df = new DecimalFormat("######.00000");
String str = df.format(imbalance);
str = str.replace(",",".");
System.out.println("IMBALANCE = "+str);
System.out.printf("\n");

}
}
}
[/code]

I apreciate any help with this.

[brianfry713]

Try using BufferedReader and BufferedWriter, or code in C++ instead.

[dhruba07]

Thanks to Brianfry I got AC.

The problem is a special output problem.The order of the specimen doesn't matter as long as the partitioning and the imbalance is right.

[brianfry713]

Input:

Code: Select all

1 2
1 1

AC output:

Code: Select all

Set #1
 0: 1 1
IMBALANCE = 0.00000

[double_zero]

I dont Know why I get WA, Plz Help,

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>
#include<vector>
#include <fstream>
#include <map>
//#define cin fin
#define x first
#define y second
#define pairii pair<int, int>
#define mappi map< pairii , int>
#define INF (int) 1e6

using namespace std;

int n, c, tc=1; pairii a[20], b[20]; mappi mp; vector<pairii> v[20];

bool cmp(pairii a, pairii b){
	if(a.x>b.x)
		return 1;
	else if(a.x==b.x && a.y<b.y)
		return 1;
	return 0;
}

bool cmp2(vector<pairii> a, vector<pairii> b){
	if(a.size() && b.size() && a[a.size()-1].y<b[b.size()-1].y)
		return 1;
	return 0;
}

int main(){
	//ifstream fin("in.txt");
	
	while(cin >> c >> n){
		int sum=0;
		for(int i=0 ; i<n ; i++){
			cin >> a[i].x; a[i].y=i;
			b[i]=a[i];
			sum+=a[i].x;
		}
		float avg=sum/(float)c;
		sort(b,b+n,cmp);
		int flag=1,i=-1,j=0;
		while(flag){
			while(j<c && flag){
				if(++i>=n){flag=0; break;}
				mp[b[i]]=j;
				j++;
			}
			j--;
			while(j>=0 && flag){
				if(++i>=n){flag=0; break;}
				mp[b[i]]=j;
				j--;
			}
			j++;
		}
		for(int i=0 ; i<n ; i++)
			v[mp[a[i]]].push_back(a[i]);
		sort(v,v+c,cmp2);
		float imb=0;
		printf("Set #%d\n", tc++);
		for(int i=0 ; i<c ; i++){
			printf(" %d:",i); float mc=0;
			for(int j=0 ; j<v[i].size() ; j++){
				printf(" %d ",v[i][j].x);
				mc+=v[i][j].x;
			}
			printf("\n");
			imb+=fabs(avg-mc);
		}
		printf("IMBALANCE = %.5f\n\n", imb);
		for(int i=0 ; i<20 ; i++)
			v[i].clear();
		mp.clear();
	}
	return 0;
}

[brianfry713]

The masses in your output should be separated by exactly one blank.

[alekscooper]

Hello guys,

please help, I tested all the cases in the problem description, uDebug and this thread, however, I got WA.

Here's the code:

Code: Select all

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>


using namespace std;
typedef vector<int> chamber;


int sum_chamber(const vector<chamber> &l, int nChamber) {
    int sum = 0;
    for (int i : l[nChamber])
        sum += i;
    return sum;
}


int sum_total(const vector<chamber> &l) {
    int sum = 0;
    for (int i = 0; i < l.size(); i++)
        sum += sum_chamber(l, i);
    return sum;
}


double imbalance (const vector<chamber> &l) {
    double imb = 0;
    double AM = (double)sum_total(l) / l.size();
    for (int i = 0; i < l.size(); i++) {
        imb += abs(sum_chamber(l, i) - AM);
    }
    return imb;
}


void print(const vector<chamber> &l, int nSet) {
    printf("Set #%d\n", nSet);
    for (int i = 0; i < l.size(); i++) {
        printf("%2d:", i);
        for (int j = 0; j < l[i].size(); j++)
            printf(" %d", l[i][j]);
        printf("\n");
    }
    printf("IMBALANCE = %.5lf\n\n", imbalance(l));
}


void testcase (int nCase, int &C, int &S) {
    
    vector<int> stations;
    int st = 0;
    for (int i = 0; i < S; i++) {
        scanf("%d", &st);
        stations.push_back(st);
    }
    
    sort(stations.begin(), stations.end());
    
    vector<chamber> lab;
    lab.resize(C);
    
    if (S <= 2 * C - 1) {
        int index = 0;
        for (int i = S - C; i < S; i++)
            lab[index++].push_back(stations[i]);

        index = 0;
        for (int i = 0; i < S - C; i++)
            lab[index++].push_back(stations[S - C - i - 1]);
    }
    
    else {
        
        // number of single speciment chambers
        int single = S - (S / 2) * 2;
        
        // loading single-specimen chambers
        for (int k = -1; k >= -single; k--)
            lab[lab.size() + k].push_back(stations[stations.size() + k]);
        
        // loading double-specimen chambers
        int iterate = (S - single) / 2;
        int l = 0;
        int r = S - single - 1;
        for (int j = 0; j < iterate; j ++)
            lab[j].push_back(stations[l++]);
        for (int j = 0; j < iterate; j ++)
            lab[j].push_back(stations[r--]);
    }
    
    // print the outcome
    print(lab, nCase);
}

int main(int argc, const char * argv[]) {
    
    int nCases = 1;
    int nC = 0, nS = 0;
    while (scanf("%d %d", &nC, &nS) != EOF)
        testcase(nCases++, nC, nS);
}

Any help will be highly appreciated.