Informatika gyűjtemény

Egy szinttel feljebb tagok.cpp

2004050607080910

<<  11. óra  >>

<<  Tagok  >>

NézetNyomtat

tagok.cpp (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: utf-8
Méret: 2 KB
/*
    Informatika: algoritmus szakkör
    11. óra
    1. feladat
    http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0809/11ora/tagok
    Uray M. János, 2008. december 2.
*/
#include <stdio.h>
#define MaxN 10000
#define MaxK 100

struct {
    // Közvetlen főnök, sorszám
    int B, X;
} S[MaxN];
int N, K;

int Read (char *);
int Write (char *);
int TaskA (void);
int TaskB (int);

int main (int AN, char * Args[]) {
    if (AN < 3)
        return 1;
    if (!Read(Args[1]))
        return 1;
    if (!Write(Args[2]))
        return 1;
    return 0;
}

// Fájl olvasása
int Read (char * FN) {
    FILE * F = fopen(FN, "rt");
    int A;
    
    if (F == NULL)
        return 0;
    fscanf(F, "%d %d\n", &N, &K);
    S[0].B = -1;
    S[0].X = 0;
    for (int I = 1; I < N; I++) {
        fscanf(F, "%d %d %d\n", &A, &S[I].B, &S[I].X);
        S[I].B--;
        S[I].X--;
    }
    fclose(F);
    return 1;
}
// Fájl írása
int Write (char * FN) {
    FILE * F = fopen(FN, "wt");
    
    if (F == NULL)
        return 0;
    fprintf(F, "%d\n", TaskA());
    for (int I = 0; I < K; I++)
        fprintf(F, "%d ", TaskB(I));
    fprintf(F, "\n");
    fclose(F);
    return 1;
}
// A feladat
int TaskA (void) {
    int Q = 0;
    
    for (int I = 0; I < N; I++)
        if (S[I].B == 0)
            Q++;
    return K - Q;
}
// B feladat
// Az X paraméter a feladatban szereplő I-nek felel meg.
int TaskB (int X) {
    // bDone[]: logikai tömb, mely megmutatja, hogy a főnöknek X-edik
    // beosztottja főnöke-e az egyes tagoknak
    // M: a tömbben lévő igazak száma
    // M0: a tömmbe beállított új igazak száma a feltételes ciklusban
    int bDone[MaxN], I, M = 0, M0;
    
    for (I = 0; I < N; I++)
        bDone[I] = 0;
    // Főnök X-edik beosztottjának beállítása
    for (I = 0; I < N; I++)
        if (S[I].B == 0 && S[I].X == X) {
            bDone[I] = 1;
            M++;
        }
    // Ciklus, mely minden lépésben a bDone[]-ban lévő emberek közvetlen
    // beosztottjait is beleteszi bDone[]-ba.
    do {
        M0 = 0;
        for (I = 0; I < N; I++)
            if (!bDone[I] && bDone[S[I].B]) {
                bDone[I] = 1;
                M0++;
            }
        M+= M0;
    } while (M0);
    // Minden tagnak K beosztottja lehet, ez esetünkben M * K helyet jelent.
    // Ebből M - 1 már foglalt.
    return M == 0 ? 0 : M * K - (M - 1);
}
(Vissza)