Informatika gyűjtemény

Egy szinttel feljebb uj_vasut.cpp

2004050607080910

<<  22. óra  >>

<<  Vasút  >>

NézetNyomtat

uj_vasut.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: 3 KB
/*
    Informatika: algoritmus szakkör
    Feladat: Vasút
    Forrás: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/22ora/vasut
    Uray M. János, 2010. márc. 16.
*/
#include <fstream>
using namespace std;

#define MaxM 1001

typedef unsigned char byte;
typedef unsigned short word;

// A bitmező legkisebb helyiértékű bitjének sorszáma
int MB[16] = {5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1};

// A vagonok jelzőszáma a szerelvényben
word Dat[MaxM];
// Egy vagontól nézve a legkisebb jelzőszámű vagon
int MinFrom[MaxM];

inline int min (int A, int B) {
    return A < B ? A : B;
}

void FillMinFrom (void);
bool CanBe (byte, byte, byte, int);

int main (int nArgs, char * Arg []) {
    int Num, M;
    if (nArgs < 3)
        return 1;
    fstream fIn(Arg[1], fstream::in), fOut(Arg[2], fstream::out);
    if (fIn.fail() | fOut.fail()) {
        fIn.close();
        fOut.close();
        return 1;
    }
    fIn >> Num;
    for (int I = 0; I < Num; I++) {
        M = 0;
        do
            fIn >> Dat[M++];
        while (Dat[M - 1] != 0);
        FillMinFrom();
        fOut << (CanBe(1, 0, 0, 0) ? "IGEN" : "NEM") << endl;
    }
    fIn.close();
    fOut.close();
    return 0;
}


// Dat[] alapján kitölti MinFrom[]-t.
void FillMinFrom (void) {
    int I;
    for (I = 0; Dat[I]; I++);
    MinFrom[I--] = 5;
    for (; I >= 0; I--)
        MinFrom[I] = min(MinFrom[I + 1], Dat[I]);
}

/*
    Rekurzív függvény: visszaadja, hogy adott A, C és D állapotra az
    adott pozíciótól kezdve megoldható-e a probléma.
    A: az A-ban a legelső kocsi sorszáma
    C: bitmező: milyen számú kocsik vannak C-ben
    D: bitmező: milyen számú kocsik vannak D-ben
*/
bool CanBe (byte A, byte C, byte D, int X) {
    // Amit lehet, azt C-ből és D-ből A-ba visszük.
    int Mask = ~((1 << MinFrom[X]) - 1);
    C &= Mask;
    D &= Mask;
    
    switch (Dat[X]) {
        // Nincs több kocsi
        default:
            // Akkor oldható meg, ha a C-ből és D-ből át tudnak menni
            // a kocsik A-ba.
            return MB[C] >= A && MB[D] >= A;
        
        // 1-es jelű kocsi jön
        case 1:
            // Akkor oldható meg, ha A-ban még nincs 1-esnél nagyobb,
            // és a maradék is megoldható
            return A == 1 && CanBe(A, C, D, X + 1);
        
        // 2-es jelű kocsi jön
        case 2:
            // Ha A-ban 2-esnél nagyobb áll, akkor nem oldható meg.
            if (A > 2)
                return false;
            // Ha valahol 2-es áll legelöl, akkor oda mehet a kocsi.
            if (A == 2 || (C & 3) == 2 || (D & 3) == 2)
                return CanBe(A, C, D, X + 1);
            // Ha már nem jön többé 1-es, akkor mehet a kocsi A-ba.
            if (MinFrom[X] > 1)
                return CanBe(2, C, D, X + 1);
            // Egyébként C-be vagy D-be megy.
            return CanBe(A, C | 2, D, X + 1) || CanBe(A, C, D | 2, X + 1);
        
        // 3-as jelű kocsi jön
        case 3:
            // Ha A-ban 3-asnál nagyobb áll, akkor nem oldható meg.
            if (A > 3)
                return false;
            // Ha valahol 3-as áll legelöl, akkor oda mehet a kocsi.
            if (A == 3 || (C & 7) == 4 || (D & 7) == 4)
                return CanBe(A, C, D, X + 1);
            // Ha már nem jön 3-asnál kisebb, akkor mehet a kocsi A-ba
            if (MinFrom[X] > 2)
                return CanBe(3, C, D, X + 1);
            // Egyébként C-be vagy D-be megy (ha ott még nincs kisebb).
            return ((C & 3) == 0 && CanBe(A, C | 4, D, X + 1)) || ((D & 3) == 0 && CanBe(A, C, D | 4, X + 1));
        
        // 4-es jelű kocsi jön
        case 4:
            // Ha A-ban 4-esnél nagyobb áll, akkor nem oldható meg.
            if (A > 4)
                return false;
            // Ha valahol 4-es áll legelöl, akkor oda mehet a kocsi.
            if (A == 4 || C == 8 || D == 8)
                return CanBe(A, C, D, X + 1);
            // Ha már csak 4-esek jönnek, akkor megoldható.
            if (MinFrom[X] > 3)
                return true;
            // Egyébként C-be vagy D-be megy.
            return ((C & 7) == 0 && CanBe(A, C | 8, D, X + 1)) || ((D & 7) == 0 && CanBe(A, C, D | 8, X + 1));
    }
}
(Vissza)