Timus 1641 - Duties - Codeforces

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

Комментарии (8)

Написать комментарий?

mkagenius

13 лет назад, # |

Have you checked the fact that "each student should be on duty atleast once" . ?

→ Ответить

MarioYC

13 лет назад, # ^ |

I use the "used" boolean array for that.

← Rev. 2 →

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

10 5 5

aropan

test 10 3 5

you use 6 days, this is uncorrect.

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.