Informatika gyűjtemény

Egy szinttel feljebb mb_teams.c

2004050607080910

<<  12. óra  >>

<<  Csapatok  >>

NézetNyomtat

mb_teams.c (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 8 KB
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    /* ki ismer kit. ez egy ketdimenzios tomb tulajdonkeppen,
     * ha a ismeri b-t, akkor know[a][b] == 1 */
    uint8_t *know;
    /* hany darab kocka van... */
    size_t persons;
    /* a csoportok. az embereket ugyanis eloszor csoportokra osztja.
     * a ket csoport: team[2n] es team[2n + 1], es ugy epul fel, hogy
     * aki team[2n]-ben szerepel, az nem lehet egyutt a team[2n + 1]
     * csapat tagjaival */
    uint8_t *team;
    /* a csapatok szama, legfeljebb az emberek szamanak a fele.
     * a team tomb ertelemszeruen 0 es 2teams-1 indexelodik */
    size_t teams;
    /* az osszetartozo csoportok tagnainak szamanak kulonbsege */
    int *diff;
    /* az elojelek, amik megmondjak, hogy a csoportokat hogyan kell
     * osszevalogatni, hogy a kulonbseg minimalis legyen */
    int8_t *sign;
    /* ez is ugyanaz, de ez a backtrack alatt hasznalt */
    int8_t *sign_tmp;
    /* ez itt meg a minimalis kulonbseg */
    int min;
} teams_t;

static void teams_init(teams_t *t)
{
    t->know = 0;
    t->persons = 0;
    t->team = 0;
    t->teams = 0;
    t->diff = 0;
    t->sign = 0;
    t->sign_tmp = 0;
    t->min = -1;
}

static void teams_free(teams_t *t)
{
    if (t->sign_tmp)
        free(t->sign_tmp);

    if (t->sign)
        free(t->sign);

    if (t->diff)
        free(t->diff);

    if (t->team)
        free(t->team);

    if (t->know)
        free(t->know);
}

static int teams_alloc(teams_t *t, size_t persons)
{
    size_t i, p2 = persons * persons;

    t->know = malloc(p2 * sizeof(uint8_t));
    if (!t->know) {
        fprintf(stderr, "Could not allocate memory for 'know'\n");
        return 0;
    }

    for (i = 0; i < p2; i++)
        t->know[i] = 0;

    t->persons = persons;

    t->team = malloc(persons * 2 * sizeof(uint8_t));
    if (!t->team) {
        fprintf(stderr, "Could not allocate memory for 'team'\n");
        return 0;
    }

    for (i = 0; i < persons * 2; i++)
        t->team[i] = 0;

    t->teams = 0;

    t->diff = malloc(persons * sizeof(int));
    if (!t->diff) {
        fprintf(stderr, "Could not allocate memory for 'diff'\n");
        return 0;
    }

    t->sign = malloc(persons * sizeof(int8_t));
    if (!t->sign) {
        fprintf(stderr, "Could not allocate memory for 'sign'\n");
        return 0;
    }

    t->sign_tmp = malloc(persons * sizeof(int8_t));
    if (!t->sign_tmp) {
        fprintf(stderr, "Could not allocate memory for 'sign_tmp'\n");
        return 0;
    }

    return 1;
}

static inline int know_get(teams_t *t, size_t i, size_t j)
{
    return *(t->know + i * t->persons + j);
}

static inline void know_set(teams_t *t, size_t i, size_t j, uint8_t v)
{
    *(t->know + i * t->persons + j) = v;
}

static inline int know(teams_t *t, size_t a, size_t b)
{
    return (know_get(t, a, b) != 0 && know_get(t, b, a) != 0);
}

/*
 * beolvassa az input fajlt
 */
static int teams_read(teams_t *t)
{
    size_t persons, i, face;

    if (scanf("%u", &persons) != 1) {
        fprintf(stderr, "Wrong input\n");
        return 0;
    }

    if (!teams_alloc(t, persons))
        return 0;

    for (i = 0; i < persons; i++)
        while (1) {
            if (scanf("%u", &face) != 1) {
                fprintf(stderr, "Wrong input\n");
                return 0;
            }

            if (face == 0)
                break;

            know_set(t, i, face - 1, 1);
        }

    return 1;
}

/*
 * az embereket csoportokra bontja
 * i: az ember
 * team: a csoport
 *
 * return: 0 - ha nem sikerult a csoportra bontas, tehat megoldas sem lesz
 *     1 - kiraly minden
 */
static int team_fill(teams_t *t, size_t i, uint8_t team)
{
    size_t j;
    uint8_t next = (team % 2 == 0) ? team + 1 : team - 1;

    /* ha az ember mar benne van a csoportban, akkor kiraly */
    if (t->team[i] == team)
        return 1;

    /* ha az ember a masik csoportban van, akkor bizony hiba van */
    if (t->team[i] == next)
        return 0;

    /* ha az ember nem 'a csoport parja' csoportban van, akkor jo */
    if (t->team[i] != 0)
        return 1;

    t->team[i] = team;

    for (j = 0; j < t->persons; j++)
        if (!know(t, i, j) && i != j)
            if (!team_fill(t, j, next))
                return 0;

    return 1;
}

inline int abs(int x)
{
    return (x >= 0) ? x : -x;
}

/*
 * az embereket tobb csoportba bontja, ahol a ket egymashoz tartozo csoport
 * tagjai nem lehetnek egy csapatban
 */
static int team_separate(teams_t *t)
{
    size_t i, j, a, b;

    for (i = 0; i < t->persons; i++) {
        if (t->team[i] != 0)
            continue;

        if (!team_fill(t, i, 2 * t->teams))
            return 0;

        t->teams++;
    }

    for (i = 0; i < t->teams; i++) {
        a = 0;
        b = 0;

        for (j = 0; j < t->persons; j++)
            if (t->team[j] == 2 * i)
                a++;
            else if (t->team[j] == 2 * i + 1)
                b++;

        t->diff[i] = a - b;
    }

    return 1;
}

/*
 * a backtrack leert az aljara, kiszamolja hogy mennyi lett az osszeg
 */
static void diff_calc(teams_t *t)
{
    size_t i;
    int sum = 0;

    for (i = 0; i < t->teams; i++)
        sum += t->diff[i] * t->sign_tmp[i];

    if (t->min < 0 || t->min > abs(sum)) {
        t->min = abs(sum);
        memcpy(t->sign, t->sign_tmp, t->teams * sizeof(int8_t));
    }
}

/*
 * a brutalis exponencialis fuggveny, ami vegigprobalja az osszes lehetoseget,
 * hogy lehetoleg minel kisebb legyen az csapatok tagjainak szama kozti
 * kulonbseg. annyi optimalizacio van benne, hogy ha a csoportok kozott
 * a kulonbseg kisebb mint 1, akkor nem agazik szanaszejjel, mert azt esszel
 * be lehet rakni
 */
static void diff_backtrack(teams_t *t, size_t i)
{
    size_t j;

    for (j = i; j < t->teams; j++) {
        if (abs(t->diff[j]) > 1)
            break;

        t->sign_tmp[j] = 0;
    }

    if (j == t->teams) {
        diff_calc(t);
    } else {
        t->sign_tmp[j] = 1;
        diff_backtrack(t, j + 1);

        t->sign_tmp[j] = -1;
        diff_backtrack(t, j + 1);
    }
}

static void teams_min(teams_t *t)
{
    diff_backtrack(t, 0);
}

/*
 * az osszehasonlito fuggveny, hogy a csapattagok megiscsak novekvo sorrendben
 * legyenek
 */
int teams_cmp(const void *a, const void *b)
{
    const uint8_t *t = a, *u = b;

    return (int)*t - (int)*u;
}

/*
 * kiirja a csapatokat
 */
void teams_write(teams_t *t)
{
    uint8_t *team_a, *team_b, *team1_ptr, *team2_ptr;
    size_t a = 0, b = 0, i, j, *team1_cnt, *team2_cnt;

    team_a = malloc(t->persons * sizeof(uint8_t));
    if (!team_a) {
        fprintf(stderr, "Could not allocate memory for 'team_a'\n");
        return;
    }

    team_b = malloc(t->persons * sizeof(uint8_t));
    if (!team_b) {
        fprintf(stderr, "Could not allocate memory for 'team_b'\n");
        free(team_a);
        return;
    }

    for (i = 0; i < t->teams; i++) {
        /* besuszterolja azokat a csoportokat, ahol egyenloen vannak */
        if (t->diff[i] == 0) {
            team1_ptr = team_a;
            team1_cnt = &a;
            team2_ptr = team_b;
            team2_cnt = &b;
        /* azok a csoportok jonnek, amikor szinten ebben a formaban
         * kell hozzaadni */
        } else if (t->sign[i] > 0) {
            team1_ptr = team_a;
            team1_cnt = &a;
            team2_ptr = team_b;
            team2_cnt = &b;
        /* most viszont a csoport tagjait forditva kell hozzaadni */
        } else if (t->sign[i] < 0) {
            team1_ptr = team_b;
            team1_cnt = &b;
            team2_ptr = team_a;
            team2_cnt = &a;
        } else {
            continue;
        }

        for (j = 0; j < t->persons; j++)
            if (t->team[j] == 2 * i)
                team1_ptr[(*team1_cnt)++] = j;
            else if (t->team[j] == 2 * i + 1)
                team2_ptr[(*team2_cnt)++] = j;
    }

    for (i = 0; i < t->teams; i++) {
        /* most azok jonnek, ahol egy ember kulonbseg van a
         * csoportok kozott, itt nyilvan azt noveljuk, amelyik kisebb */
        if (t->sign[i] != 0 || abs(t->diff[i]) != 1)
            continue;

        if ((t->diff[i] > 0 && (int)a - (int)b < 0) ||
            (t->diff[i] < 0 && (int)a - (int)b > 0)) {
            team1_ptr = team_a;
            team1_cnt = &a;
            team2_ptr = team_b;
            team2_cnt = &b;
        } else {
            team1_ptr = team_b;
            team1_cnt = &b;
            team2_ptr = team_a;
            team2_cnt = &a;
        }

        for (j = 0; j < t->persons; j++)
            if (t->team[j] == 2 * i)
                team1_ptr[(*team1_cnt)++] = j;
            else if (t->team[j] == 2 * i + 1)
                team2_ptr[(*team2_cnt)++] = j;
    }

    /* meg erre is van ido, olyan gyors az algo :) */
    qsort(team_a, a, sizeof(uint8_t), teams_cmp);
    qsort(team_b, b, sizeof(uint8_t), teams_cmp);

    printf("%d", a);
    for (i = 0; i < a; i++)
        printf(" %d", team_a[i] + 1);
    printf("\n");

    printf("%d", b);
    for (i = 0; i < b; i++)
        printf(" %d", team_b[i] + 1);
    printf("\n");

    free(team_b);
    free(team_a);
}

int main(void)
{
    teams_t t;

    teams_init(&t);

    if (!teams_read(&t)) {
        teams_free(&t);
        return 1;
    }

    if (!team_separate(&t)) {
        printf("No solution\n");
    } else {
        teams_min(&t);
        teams_write(&t);
    }

    teams_free(&t);

    return 0;
}
(Vissza)