MarioYC's blog

By MarioYC, 13 years ago, In English

I'm trying to solve this problem with a greedy approach, first assign the number of students assigned to each classroom as to maximize the number of possible pairs. Then make sure that I have chosen a pair for each of them, and then just choose enough available pairs to complete the ones asked. However, I'm getting WA in test case 7, any idea of why this approach fails?

Now AC, my initial assignment was failing. For example: 10 3 5. Thanks to aropan.

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int main(){
    int n,k,m;
    scanf("%d %d %d",&n,&k,&m);
    
    int cont[100];
    
    for(int i = 0,x = n/k;i < m;++i) cont[i] = x;
    for(int i = n % k - 1;i >= 0;--i) ++cont[i];
    
    int room[100];
    
    for(int i = 0,k = 0;i < m;++i)
        for(int j = 0;j < cont[i];++j)
            room[k++] = i;
    
    for(int i = 0;i < n;++i)
        printf("%d\n",room[i] + 1);
    
    bool M[100][100];
    memset(M,false,sizeof(M));
    
    for(int i = 0;i < n;++i)
        for(int j = i + 1;j < n;++j)
            M[i][j] = M[j][i] = (room[i] != room[j]);
    
    bool used[100];
    memset(used,false,sizeof(used));
    
    for(int i = 0;i < n;++i){
        if(!used[i]){
            for(int j = 0;j < n;++j){
                if(M[i][j] && !used[j]){
                    used[i] = true; used[j] = true;
                    M[i][j] = M[j][i] = false;
                    printf("%d %d\n",i + 1,j + 1);
                    --m;
                    break;
                }
            }
        }
        
        if(!used[i]){
            for(int j = 0;j < n;++j){
                if(M[i][j]){
                    used[i] = true;
                    M[i][j] = M[j][i] = false;
                    printf("%d %d\n",i + 1,j + 1);
                    --m;
                    break;
                }
            }
        }
    }
    
    for(int i = 0;i < n && m > 0;++i){
        for(int j = i + 1;j < n && m > 0;++j){
            if(M[i][j]){
                M[i][j] = M[j][i] = false;
                printf("%d %d\n",i + 1,j + 1);
                --m;
            }
        }
    }
    
    return 0;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Have you checked the fact that "each student should be on duty atleast once" . ?
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I use the "used" boolean array for that.
    • 13 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      in the following test case 10th student is never at duty (If u ignore the last line :P )::
      10   5    5