OJ Board

Posted: **Sun May 20, 2007 6:57 pm**

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

Thanks in advance.

Posted: **Sun May 20, 2007 7:12 pm**

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.

Posted: **Sun May 20, 2007 7:28 pm**

mf wrote: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.

Posted: **Mon May 21, 2007 8:13 am**

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

Posted: **Thu Jun 14, 2007 10:07 am**

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.

Posted: **Mon Jun 18, 2007 7:26 pm**

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";
	}
}

Posted: **Mon Jun 18, 2007 11:46 pm**

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...

Posted: **Tue Jun 19, 2007 6:40 am**

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

Posted: **Thu Oct 25, 2007 9:02 pm**

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.

Posted: **Thu Oct 25, 2007 10:18 pm**

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

Posted: **Fri Oct 26, 2007 5:36 am**

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;   
}

Posted: **Fri Oct 26, 2007 5:00 pm**

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)

Posted: **Sat Oct 27, 2007 5:00 pm**

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

OJ Board

11204 - Musical instruments

11204 - Musical instruments