11204 - Musical instruments

[rio]

With my poor English, I can't understand the problem statement.
Could someone explain the sample i/o?

Thanks in advance.

[mf]

I couldn't completely understand it either, but this is what I've got accepted with:
find the number of maximum-size subsets of students, such that all these students have different most-preferred instrument.

The input gives for each student a permutation of {1,...,N}, the position of 1 in it is the number of student's most-preferred instrument.

For example, in the 3rd sample student's most preferred instruments are 3, 3, 2, 2; so you could assign these instruments to two students in 4 ways.

[little joey]

The input gives for each student a permutation of {1,...,N}, the position of 1 in it is the number of student's most-preferred instrument.

Yes, this is essential, because the problem statement suggests otherwise:

N numbers between 1 and N which determine the priority

which indicates that the highest number determines the highest priority. The sample I/O, however, supports mf's interpretation, which is correct.

[rio]

Thanks mf and joey. I understand it and got AC.

[hamedv]

i can't find the bug of my code.
can anyine help me?

Code: Select all

var
  a : array [1..32, 1..32] of integer;
  num : array [1..1024] of integer;
  s : array [1..32] of boolean;
  i, j, m, n, t, l : integer;

procedure count(sum, row : integer; s : array of boolean);
begin
  if row > m then
    inc(num[sum]) else
    for i := 1 to m do
      if not s[i] then
      begin
        s[i] := true;
        count(sum+a[row][i], row+1, s);
        s[i] := false;
      end;
end;

begin
  readln(t);
  for i := 1 to 32 do s[i] := false;
  for l := 1 to t do
  begin
    readln(n, m);
    for i := 1 to m do
      for j := 1 to n do
        read(a[i, j]);
    for i := 1 to 1024 do num[i] := 0;
    count(0, 1, s);
    i := 1;
    while num[i] = 0 do inc(i);
    writeln(num[i]);
  end;
end.

[hamedv]

i can't find the bug of my code.
can anyine help me?

Code: Select all

#include <iostream>

using namespace std;

int num[1025], m, n, t, l, a[32][32], i, j;

struct M{
	bool s[32];
};

M s;

void count(int sum, int row, M s, int a[32][32])
{
	if (row == m)
		num[sum]++;
	for (i = 0; i < m; i++)
		if (s.s[i] == 0)
		{
			s.s[i] = 1;
			count(sum+a[row][i], row+1, s, a);
			s.s[i] = 0;
		}
}

int main()
{
	for (i = 0; i < 32; i++)
		s.s[i] = 0;
	cin >> t;
	for (l = 0; l < t; l++)
	{
		cin >> n >> m;
		for (i = 0; i < m; i++)
			for (j = 0; j < n; j++)
				cin >> a[i][j];
		memset(num, 0, sizeof num);
		count(0, 0, s, a);
		i = 0;
		while (num[i] == 0) i++;
		cout << num[i] << "\n";
	}
}

[little joey]

I think you misunderstood the problem statement. The sentence

Julio wants to make a distribution in which the biggest number of students have their favourite musical instrument

means that a student either gets his favorite instrument or no instrument at all.

The whole priority thing is just meant to confuse you, which it obviously did...

[sohel]

.. and it was nice to see you converting the 'Pascal' code to that of 'C++' in expectation of more response !

[beginner]

I keep getting WA, is there anyone that can help me ?
Basically my algorithm is count the number of students that have the same favorite instruments and then count the total of combination among the students.
For example in the third case there are 2 students for 3rd instrument and 2 students for 2nd instrument and at the end we have 2*2 which is 4 ways to arrange them. can someone point me out where is my mistake ?

Thanks in advance.

[Jan]

Your algorithm looks correct to me. However, you can post your code..

[beginner]

Below is my code. Thanks for checking it

Code: Select all

#include<iostream>
#include<string.h>

using namespace std;

int main(){
    int nout,ninst,nstu,p;
    int count[100];
    
    cin>>nout;
    for(int i=0;i<nout;i++){
        cin>>ninst>>nstu;
        memset(count,0,sizeof(count));
        for(int j=0;j<nstu;j++){
            for(int k=0;k<ninst;k++){
                cin>>p;
               if(p==1)
                    count[k+1]++;
            }
        }
        unsigned long res=1;
        for(int j=0;j<ninst;j++)
            if(count[j]>1)
                res*=count[j];
        cout<<res<<endl;
    }
    
    return 0;   
}

[Jan]

Check two parts

Code: Select all

count[k+1]++; // So, you are starting from 1

Code: Select all

for(int j=0;j<ninst;j++) // j should be 1 to ninst. right?
    if(count[j]>1)

[beginner]

Hi Jan,

yes you're right. thanks for point that out.
I've got AC finally.... I need to practice more since i even didn't realize that simple mistake. thanks for your help