Informatika gyűjtemény

Egy szinttel feljebb uj_robot.cpp

2004050607080910

<<  19. óra  >>

<<  Robot  >>

NézetNyomtat

uj_robot.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: us-ascii
Méret: 2 KB
/*
    Informatika: algoritmus szakkor
    Feladat: Robot
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/19ora/robot
    Uray M. Janos, 2010. 2. 23.
*/
#include <iostream>
#include <fstream>
using namespace std;

#define MaxObj 10000

struct sObj {
    short X, Y;
};

bool Read (const char *, int &, sObj *);
bool Write (const char *, int, int, const int *);

void Calc (int, const sObj *, int &, int &, int *);

// Minimum- es maximumszamitas
int Max (int A, int B) {
    return A > B ? A : B;
}
int Min (int A, int B) {
    return A < B ? A : B;
}
int Max (int A, int B, int C) {
    return A > B ?
        (A > C ? A : C) :
        (B > C ? B : C);
}
int Min (int A, int B, int C) {
    return A < B ?
        (A < C ? A : C) :
        (B < C ? B : C);
}
// Ket oldalbol kiszamitja a teglalap keruletet
int Rect (int X, int Y) {
    return 2 * (X + Y);
}

int main (int nArgs, char * Arg []) {
    int nObj, nGr, Time;
    sObj Obj[MaxObj];
    int Gr[MaxObj];
    // Parameterek ellenorzese
    if (nArgs < 3)
        return 1;
    // Olvasas
    if (!Read(Arg[1], nObj, Obj))
        return 1;
    // A feladat megoldasa
    Calc(nObj, Obj, Time, nGr, Gr);
    // Kiiras
    if (!Write(Arg[2], Time, nGr, Gr))
        return 1;
    return 0;
}

// Olvasas allomanybol
bool Read (const char * FN, int & nObj, sObj * Obj) {
    fstream F(FN, fstream::in);
    if (F.fail())
        return false;
    F >> nObj;
    for (int I = 0; I < nObj; I++)
        F >> Obj[I].X >> Obj[I].Y;
    F.close();
    return true;
}
// Iras allomanyba
bool Write (const char * FN, int Time, int nGr, const int * Gr) {
    fstream F(FN, fstream::out);
    if (F.fail())
        return false;
    F << Time << endl;
    for (int I = 0; I < nGr; I++)
        F << Gr[I] << " ";
    F << endl;
    F.close();
    return true;
}

void Calc (int nObj, const sObj * Obj, int & Time, int & nGr, int * Gr) {
    int Opt[MaxObj], GrLen[MaxObj];
    int O1, O2, O3;
    int I, J;
    // N = 1, 2, 3-ra megoldas kezzel (erdemes egyutt vinni oket)
    if (nObj > 0) {
        Opt[0] = Rect(Obj[0].X, Obj[0].Y);
        GrLen[0] = 1;
    }
    if (nObj > 1) {
        Opt[1] = Rect(Max(Obj[0].X, Obj[1].X), Max(Obj[0].Y, Obj[1].Y));
        GrLen[1] = 2;
    }
    if (nObj > 2) {
        Opt[2] = Rect(Max(Obj[0].X, Obj[1].X, Obj[2].X), Max(Obj[0].Y, Obj[1].Y, Obj[2].Y));
        GrLen[2] = 3;
    }
    // N > 3-ra megoldas
    for (int I = 3; I < nObj; I++) {
        // A haromfele sebesseg kiszamitasa
        O1 = Opt[I - 1] + Rect(Obj[I].X, Obj[I].Y);
        O2 = Opt[I - 2] + Rect(Max(Obj[I - 1].X, Obj[I].X), Max(Obj[I - 1].Y, Obj[I].Y));
        O3 = Opt[I - 3] + Rect(Max(Obj[I - 2].X, Obj[I - 1].X, Obj[I].X), Max(Obj[I - 2].Y, Obj[I - 1].Y, Obj[I].Y));
        // Az optimum kivalasztasa
        Opt[I] = Min(O1, O2, O3);
        if (Opt[I] == O1)
            GrLen[I] = 1;
        else if (Opt[I] == O2)
            GrLen[I] = 2;
        else
            GrLen[I] = 3;
    }
    // A fordulok megszamolasa
    nGr = 0;
    I = nObj - 1;
    while (I >= 0) {
        I -= GrLen[I];
        nGr++;
    }
    // A fordulok feltoltese
    I = nObj - 1;
    J = 1;
    while (I >= 0) {
        Gr[nGr - J] = GrLen[I];
        I -= GrLen[I];
        J++;
    }
    // Vegeredmeny
    Time = Opt[nObj - 1];
}
(Vissza)