Блог пользователя MarioYC

Timus 1641 - Duties
Автор MarioYC, 13 лет назад, По-английски

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;
}
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Have you checked the fact that "each student should be on duty atleast once" . ?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
test 10 3 5
you use 6 days, this is uncorrect.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Seems like my initial assignment is not optimum. The only better way that I've come up with is non-bipartite matching though, this seems too much since the problem was supposed to be solved by high school students.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Replace
          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;
      into
          int room[100];
          for(int i = 0; i < n; ++i)
              room[i] = i % k;
      and got accepted ;)
      → Ответить