410 - Station Balance

[Revenger]

Can anyone give me a test on which my program fails? It's get WA, but I think that it is correct.

[pascal]Program p410;

Const MaxS = 10;
MaxC = 5;

Var Inf : Array[1..MaxS]of Integer;
Cam : Array[1..MaxC]of Integer;
AM,IM : Extended;
C,S,i,j,t : Integer;
ic,jc,k,p : Integer;
ok : Boolean;

begin
t:=0;
While Not Eof(InPut) Do begin















Writeln('Set #',t);
for i:=1 to C do begin
Write(i:2,':');
if Inf[i*2-1]>0 then Write(' ',Inf[i*2-1]);
if Inf[i*2]>0 then Write(' ',Inf[i*2]);
Writeln;
end;
Writeln('IMBALANCE = ',IM:0:5);
end;
end.[/pascal]

[xenon]

The chambers are numbered 0,1,2,3 and 4, your prog outputs 1,2,3,4,5.
That's an obvious error. Haven't looked at the rest of your algo.

[Revenger]

It still getting WA

[pascal]Program p410;

Const MaxS = 10;
MaxC = 5;

Var Inf : Array[1..MaxS]of Integer;
Cam : Array[1..MaxC]of Integer;
AM,IM : Extended;
C,S,i,j,t : Integer;
ic,jc,k,p : Integer;
ok : Boolean;

begin
t:=0;
While Not Eof(InPut) Do begin
















Writeln('Set #',t);
for i:=1 to C do begin
Write((i-1):2,':');
if Inf[i*2-1]>0 then Write(' ',Inf[i*2-1]);
if Inf[i*2]>0 then Write(' ',Inf[i*2]);
Writeln;
end;
Writeln('IMBALANCE = ',IM:0:5);
end;
end.[/pascal]

[xenon]

I really think you should better check your output formatting against the description before you dump your code on the message board. But hey, that's only my opinion

The final line of output for each set should be a blank line.

I added one writeln statement to your code, and got it accepted. So have a try...

PS. Since the code you published is allmost the solution, and thus a big spoiler, I suggest you remove it. But still, it's only my opinion. No hard feelings, mate

[Revenger]

Thank you very much!
Of cource, I will delete my code

[Zuberul]

I used greedy for this proble.
but got WA.
please give me some I/O.

[roticv]

Hello does anyone know why I keep getting WA for 410?

Code: Select all

#include <stdio.h>
#include <math.h>

int n,m,z,i,j,k,h,f,p,q,ave,total,sub;
int specimen[20],sorted[20],visited[20],visited2[20];
double imbalance;

int compare(const void *a, const void *b){
	if (*(int*)a > *(int*)b)
		return 1;
	return -1;
}

int main(){
	z = 0;
	while (scanf("%d %d ",&m,&n)!=EOF){
		z++;
		ave = 0;
		for (i=0;i<n;i++){
			scanf("%d ",&specimen[i]);
			sorted[i] = specimen[i];
			visited[i] = 0; visited2[i] = 0;
			ave += specimen[i];
		}
		sorted[i] = 0;
		specimen[i] = 0;
		p = m;
		q = n;
		if (n%2 == 1)
			n++;
		total = 0;
		qsort(sorted,n,sizeof(int),compare);
		printf("Set #%d\n",z);
		for (i=0;i<m;i++){
			printf("%2d:",i);
			for (j=0;j<q;j++)
				if (visited[j]!=1){
					visited[j] = 1;
					printf(" %d",specimen[j]);
					for (k=0;k<n;k++)
						if (sorted[k] == specimen[j] && visited2[k] != 1)
							break;
					if (sorted[n-k-1]!=0){
						printf(" %d",sorted[n-k-1]);
					}
					visited2[k] = 1; visited2[n-k-1] = 1;
					for (h=0;h<q;h++)
						if (sorted[n-k-1] == specimen[h] && visited[h]!=1){
							visited[h] = 1;
							break;
						}
					sub = sorted[k] + sorted[n-k-1];
					sub = sub*p - ave;
					if (sub < 0)
						sub = -sub;
					total += sub;
					break;
				}
			printf("\n");
		}
		imbalance = total;
		imbalance /= p;
		printf("IMBALANCE = %.5lf\n\n",imbalance);
	}
	return 0;
}

[kane116]

What's wrong with it? Help me please, thank you!

Code: Select all

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

int dat[10];
int sto[5][2];
int s, c, cot;
double AM, IM;
double CM[5];

int init()
{   for (int i = 0; i < 10; i++)
    {   dat[i] = 0;
        }
        
    for (int i = 0; i < 5; i++)
    {   CM[i] = 0;
        for (int j = 0; j < 2; j++)
        {   sto[i][j] = 0;
            }
        }
    
    s = 0;
    c = 0;
    AM = 0;
    IM = 0;
    }
    
int inpt()
{   cin >> c >> s;
    for (int i = 0; i < s; i++)
    {   cin >> dat[i];
        AM = AM + dat[i];
        }
    AM = AM / c;
    }

int sorting()
{   int tmp;
    
    for (int i = 0; i <= s; i++)
    {   for (int j = 0; j <= s; j++)
        {   if (dat[i] < dat[j])
            {  tmp = dat[i];
               dat[i] = dat[j];
               dat[j] = tmp;
               }
            }
        }
    }

int storing()
{   for (int i = 0; i < c; i++)
    {   sto[i][0] = dat[i];
        CM[i] = CM[i] + dat[i];
        }
    for (int i = 0; i < c; i++)
    {   sto[c - i - 1][1] = dat[c + i];
        CM[c - i - 1] = CM[c - i - 1] + dat[c + i];
        }
    }

int outpt()
{   int tmp;
    char str[10];
    cout << "Set #" << cot << endl;
    for (int i = 0; i < c; i++)
    {   cout << " " << i << ": ";

        for (int j = 0; j < 2; j++)
        {   if (sto[i][j] != 0)
            {  cout << sto[i][j];
               }
            if (sto[i][0] != 0)
            {  cout << " ";
               }
            }
        cout << endl;
        }
    printf("IMBLANCE = %.5f\n", IM);
    cout << endl;
    }

int cal()
{   for (int i = 0; i < c; i++)
    {   IM = IM + fabs(CM[i] - AM);
        }
    }

int main()
{   cot = 0;
    while (! cin.eof())
    {   init();
        cot++;
        inpt();
        sorting();
        storing();
        cal();
        outpt();
        }
    }

[Jan]

There are some problems in your code.

Code: Select all

int init() 
{   for (int i = 0; i < 10; i++) 
    {   dat[i] = 0; 
        } 
        
    for (int i = 0; i < 5; i++) 
    {   CM[i] = 0; 
        for (int j = 0; j < 2; j++) 
        {   sto[i][j] = 0; 
            } 
        } 
    
    s = 0; 
    c = 0; 
    AM = 0; 
    IM = 0; 
    } 

You are declaring i as an integer in every 'for()' statement. Its bad programming practice. You should declare local variables after u declare the function. You should write...

Code: Select all

int init() 
{  
    int i,j; 
    for (i = 0; i < 10; i++) 
    {   dat[i] = 0; 
        } 
        
    for (i = 0; i < 5; i++) 
    {   CM[i] = 0; 
        for (j = 0; j < 2; j++) 
        {   sto[i][j] = 0; 
            } 
        } 
    
    s = 0; 
    c = 0; 
    AM = 0; 
    IM = 0; 
    } 

You are getting wrong answer because u missed something. The problem states that

The first number (1<=C<=5) defines the number of chambers in the centrifuge and the second number (1<=S<=2C) defines the number of specimens in the input set.

So, S<C is correct. So there can be inputs like

Input:

Code: Select all

5 3
1 2 3

And output should be

Output:

Code: Select all

Set #1
 0: 3
 1: 2
 2: 1
 3:
 4:
IMBALANCE = 5.20000

Hope it works.

[roticv]

How come it is not

Set #1
0: 1 2
1: 3
2:
3:
4:
IMBALANCE = 3.60000

[Jan]

Did you notice this....

CM
is the Chamber Mass of chamber i and is computed by summing the masses of the specimens assigned to chamber i.
AM
is the Average Mass of the chambers and is computed by dividing the sum of the masses of all specimens by the number of chambers (C).

Code: Select all

5 3 
1 2 3
Now There are 5 chambers, 3 specimens. Total mass 1+2+3 = 6
And average = 6/5 = 1.20
So, AM = 1.20.

Now the output is

Code: Select all

Set #1 
 0: 3 
 1: 2 
 2: 1 
 3: 
 4: 
IMBALANCE = 5.20000
Imbalance = |3 - AM | + |2 - AM | + |1 - AM | + |0 - AM | + |0 - AM |
          = |3 - 1.2| + |2 - 1.2| + |1 - 1.2| + |0 - 1.2| + |0 - 1.2|
          =    1.8    +    .8     +    .2     +    1.2    +   1.2
          = 5.2

But your output is

Code: Select all

Set #1 
0: 1 2 
1: 3 
2: 
3: 
4: 
IMBALANCE = 3.60000
Imbalance = |3 - AM | + |3 - AM | + |0 - AM | + |0 - AM | + |0 - AM |
          = |3 - 1.2| + |3 - 1.2| + |0 - 1.2| + |0 - 1.2| + |0 - 1.2|
          =    1.8    +    1.8    +   1.2     +    1.2    +   1.2
          = 7.2
So, your output is wrong.

Any other problems?

[Dominik Michniewski]

Ye, I have question

Why output should be:

Code: Select all

Set #1 
 0: 3 
 1: 2 
 2: 1 
 3: 
 4: 
IMBALANCE = 5.20000 

and not

Code: Select all

Set #1 
 0: 1 
 1: 2 
 2: 3 
 3: 
 4: 
IMBALANCE = 5.20000 

or any other ordering with the same imbalance ?

Best regards
DM

[roticv]

Thanks alot. I just realised I made a stupid mistake and that is why I kept getting WA. Anyway, personally I think the order the chambers are printed is not important as it is not clearly stated and there is a special correction program.

[Jan]

To Dominik Michniewski, it is a special correction program. So, any ordering with the same IMBALANCE is correct.

[heckler]

Hey everyone

I