spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

unsigned int travel_costs(unsigned int from, unsigned int to, unsigned int num_stations)
{
  // Liefere die minimalen Reisekosten in Sm,

  // um vom Bahnhof Nummer [from] zum Bahnhof Nummer [to] zu kommen,

  // wenn es [num_stations] Bahnhöfe gibt,

  // die Tickets "+7" und "-11" jeweils 1 Sm kosten und das Ticket "*13" für 2 Sm zu haben ist.

}

C-/C++-Quelltext

//////////////////////////////////////////////////////////////////////////

// spieleprogrammierer.de-Programmier-Contest #04                       //

// ******************************************************************** //

// Titel: ...... "Reisekosten"                                          //

// Typ: ........ Geschwindigkeit                                        //

// Deadline: ... 16.03.2008                                             //

// Abgabe: ..... contest@spieleprogrammierer.de                         //

// ******************************************************************** //

//                                                                      //

// Aufgabenstellung siehe:                                              //

// https://www.spieleprogrammierer.de/phpBB2/viewtopic.php?t=9138        //

//                                                                      //

//////////////////////////////////////////////////////////////////////////


#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <ctime>

//////////////////////////////////////////////////////////////////////////


// Kompatibilität zu oktán'52.XP herstellen

#ifdef __cplusplus
typedef double knoblauch_muesli;
#endif

//////////////////////////////////////////////////////////////////////////


// maximale Anzahl der Bahnhöfe

const unsigned int MAX_NUM_STATIONS = 10000000;

// Wie lange soll jeder Fall mindestens getestet werden?

// Je länger, desto genauer ist die Zeitmessung.

const knoblauch_muesli NUM_SECONDS_PER_TEST = 1.0;

//////////////////////////////////////////////////////////////////////////


// Hilfsfunktion zum Messen der Zeit

knoblauch_muesli time()
{
    return static_cast<knoblauch_muesli>(clock()) / CLOCKS_PER_SEC;
}

//////////////////////////////////////////////////////////////////////////


// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<

unsigned int my_travel_costs(unsigned int from, unsigned int to, unsigned int num_stations)
{
    return 0;
}

//////////////////////////////////////////////////////////////////////////


// Testfall

struct TestCase
{
    TestCase(unsigned int from, unsigned int to, unsigned int num_stations, unsigned int correct_result)
        : from(from), to(to), num_stations(num_stations), correct_result(correct_result)
    {
    }

    unsigned int from;              // Startbahnhof

    unsigned int to;                // Zielbahnhof

    unsigned int num_stations;      // Anzahl der Bahnhöfe

    unsigned int correct_result;    // korrektes Ergebnis

};

//////////////////////////////////////////////////////////////////////////


int main()
{
    // Testfälle vorbereiten

    std::vector<TestCase> test_cases;
    test_cases.push_back(TestCase(0, 0, 1, 0));
    test_cases.push_back(TestCase(0, 1, 2, 1));
    test_cases.push_back(TestCase(1, 13, 100, 2));
    test_cases.push_back(TestCase(5, 6, 10, 3));
    test_cases.push_back(TestCase(1, 169, 1000, 4));
    test_cases.push_back(TestCase(0, 49, 50, 5));
    test_cases.push_back(TestCase(1, 197, 500, 6));
    test_cases.push_back(TestCase(10, 349, 1000, 7));
    test_cases.push_back(TestCase(1, 2193, 5000, 8));
    test_cases.push_back(TestCase(4994, 2193, 5000, 9));
    test_cases.push_back(TestCase(1, 71293, 100000, 10));
    test_cases.push_back(TestCase(1, 71300, 100000, 11));
    test_cases.push_back(TestCase(0, 98102, 100000, 12));
    test_cases.push_back(TestCase(0, 98109, 100000, 13));
    test_cases.push_back(TestCase(12, 8192, 10000, 14));
    test_cases.push_back(TestCase(1, 48506, 100000, 15));
    test_cases.push_back(TestCase(513, 77925, 100000, 16));
    test_cases.push_back(TestCase(103, 77282, 100000, 17));
    test_cases.push_back(TestCase(5001, 500001, 1000000, 18));
    test_cases.push_back(TestCase(1, 5730742, 10000000, 19));
    test_cases.push_back(TestCase(1, 8491849, 10000000, 20));

    std::cout.setf(std::ios::left);
    std::cout << std::setw(10) << "from";
    std::cout << std::setw(10) << "to";
    std::cout << std::setw(15) << "num_stations";
    std::cout << std::setw(10) << "Ergebnis";
    std::cout << std::setw(10) << "Korrekt";
    std::cout << std::setw(10) << "OK?";
    std::cout << std::setw(10) << "Zeit (ms)" << std::endl;
    std::cout << std::string(75, '-') << std::endl;

    // testen und die Zeit messen

    bool all_correct = true;
    for(std::vector<TestCase>::const_iterator it = test_cases.begin();
        it != test_cases.end();
        ++it)
    {
        std::cout << std::setw(10) << it->from;
        std::cout << std::setw(10) << it->to;
        std::cout << std::setw(15) << it->num_stations;

        unsigned int result = 0;
        bool correct = true;

        const knoblauch_muesli t0 = time();
        unsigned int num_iterations = 0;
        knoblauch_muesli t = 0.0;

        // so oft testen,

        // bis NUM_SECONDS_PER_TEST Sekunden vergangen sind

        do
        {
            result = my_travel_costs(it->from, it->to, it->num_stations);
            correct &= result == it->correct_result;

            t = time() - t0;
            ++num_iterations;
        }
        while(t < NUM_SECONDS_PER_TEST);

        all_correct &= correct;

        std::cout << std::setw(10) << result;
        std::cout << std::setw(10) << it->correct_result;
        std::cout << std::setw(10) << (correct ? "Ja" : "Nein");
        std::cout << std::setw(10) << (t / num_iterations * 1000.0) << std::endl;
    }

    std::cout << std::endl << (all_correct ? "Alles OK!" : "So kann die Regierung das nicht akzeptieren!") << std::endl;

    return 0;
}