.

Home Wettbewerb Ressourcen Informationen Sponsoren Impressum

Allgemeines Aufgaben Sprachen Musteraufgabe Aufwärmphase Archiv

Inhalt

• Ergebnisse des 1. OWINF
• Aufgabe fluss mit Lösung
• Aufgabe prim mit Lösung
• Aufgabe reise mit Lösung

3
0
1
0
1
1

1
L
0
1
2
L
1
F

Musterlösung

Diese Aufgabe Informatik kann als graphentheoretisches Problem betrachtet werden. Dabei ist jedes Erzeugnis ein Knoten. Wenn zwei sich fressen werden sie durch eine Kante verbunden. Die Richtung des gefressen Werdens ist für das Problem nicht wichtig. Es wird also ein ungerichteter Graph verwendet. Damit das Problem lösbar ist muss es möglich sein durch Entfernen eines Knotens alle Kanten zu beseitigen. Es gibt also einen Knoten der von allen Kanten berührt wird. Wenn dieser Knoten von 3 oder mehr Kanten berührt wird, ist das Problem nicht lösbar. Der Graph hat also höchstens 2 Kanten. Daher wird in dieser Musterlösung auf eine echte Graphenimplementation verzichtet. Es kommen also die folgenden 3 Graphenstrukturen in Frage:

• Ein Graph ohne Kanten
• Ein Graph mit einer Kante
• Ein Graph mit 2 Kanten die einen gemeinsamen Knoten haben.

Der letzte dieser Fälle ist der komplizierteste. Der Knoten, der von beiden Kanten berührt wird, wird dabei mittlerer Knoten genannt. Dieser muss zuerst über den Fluss gebracht werden. Dadurch ist sichergestellt, dass niemand gefressen wird. Jetzt können alle unbeteiligten Erzeugnisse auf die richtige Seite gebracht werden.

Dannach wird eines der übrigen Erzeugnisse auf die richtige Seite gebracht. Dort ist es mit dem Mittleren zusammen. Falls der Graph 2 Kanten hat muss das Mittlere also wieder auf die ursprüngliche Seite gebracht werden. Von dort kann dann das letzte Erzeugniss auf die Seite der Stadt gebracht werden. Da das Mittlere nicht dort ist, wird trotzdem niemand gefressen. Am Ende muss dann noch das Mittlere Erzeugnis auf die richtige Seite gebracht werden.

Die grundsätzliche Strategie ist also immer:

• Mittleres
• L
• unbeteiligte Erzeugnisse rüberbringen und jedes Mal wieder leer zurück
• Linkes
• Mittleres
• Rechtes
• L
• Mittleres
• F

Falls der Graph kleiner ist, also nur eine Kante ist, kann das Vorgehen entsprechend vereinfacht werden.

#include <iostream>
#include <fstream>

using namespace std;

inline void addedge(int, int);

inline void failed();
inline void result();
inline bool isSpecial(int);


int animalnumber; // Die Anzahl der vorhandenen Erzeugnisse
// edge1 und edge2 sind die beiden Kanten. Wenn eine Kante

// nicht existiert werden ihre Knoten auf -1 gesetzt

int edge1a(-1), edge1b(-1), edge2a(-1), edge2b(-1);
// Die maximal 3 Knoten, die von den beiden Kanten berührt werden.

int aMiddle(-1), aLeft(-1), aRight(-1);

int main() 
{
// Eingabe einlesen und in den Graphen übertragen:

	ifstream infile("fluss.in");
	infile >> animalnumber;
	for(int i=0; i<animalnumber; i++) {
		int eatnum;
		infile >> eatnum;
		if(eatnum>2)failed();
		for(int food=0; food<eatnum; food++) {
			int foodnum;
			infile>>foodnum;
			addedge(i, foodnum);
		}
	}
	

// einfachster Fall, kein Erzeugnis frisst etwas:
	if(edge1a==-1 && edge2a==-1) 
	{
		result();
	}	

// Fressgraph hat nur eine Kante:
	if(edge2a==-1) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		result();
	}
// Fressgraph ist nicht zusammenhängend:

	if((edge1a!=edge2a) && (edge1a!=edge2b) 
	&& (edge1b!=edge2a) && (edge1b!=edge2b)) failed();

// Restliche Fälle: Fressgraph hat die Form left-middle-right

	if(edge1a==edge2a) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		aRight=edge2b;
	}
	if(edge1a==edge2b) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		aRight=edge2a;
	}
	if(edge1b==edge2a) 
	{
		aMiddle=edge1b;
		aLeft=edge1a;
		aRight=edge2b;
	}
	if(edge1b==edge2b) 
	{
		aMiddle=edge1b;
		aLeft=edge1a;
		aRight=edge2a;
	}
	result();
}

/*
fügt die Kante (a,b) zum Graphen hinzu
*/
inline void addedge(int a, int b) 
{
	if(edge1a==-1) 
	{
		edge1a=a;
		edge1b=b; 
		return;
	}
	else if((edge1a==a && edge1b==b) || (edge1a==b && edge1b==a)) 
	{
		return;
	}
	else if(edge2a==-1) 
	{
		edge2a=a;
		edge2b=b;
		return;	
	}
	else if((edge2a==a && edge2b==b) || (edge2a==b && edge2b==a)) 
	{
		return;
	}

// Bei mehr als 2 Kanten ist das Problem nicht lösbar:	

	failed(); 
}

/*
Ausgabe, dass das Problem nicht lösbar ist 
und Programm beenden
*/
inline void failed() 
{
	ofstream outfile("fluss.out");
	outfile<<"F"<<endl;
	outfile.close();
	exit(0);
}

/*
Hier wird eine existierende Lösung ausgegeben
*/

inline void result()
{
// zuerst den mittleren rüber damit sich niemand auffrisst:

	ofstream outfile("fluss.out");
	if(aMiddle!=-1) 
	{
		outfile<<aMiddle<<endl;
		outfile<<"L"<<endl;
	}	
// dann alle unbeteiligten Erzeugnisse rüber:

	
	for(int i=0; i<animalnumber; i++) 
	{
		if(!isSpecial(i)) 
		{	
			outfile<<i<<endl;
			outfile<<"L"<<endl;
		}
	}
//(Hier immer auf der Seite des Hofs)

// Jetzt die Problematischen
	if(aMiddle!=-1) {
		outfile<<aLeft<<endl;
		if(aRight!=-1) 
		{
			outfile<<aMiddle<<endl;
			outfile<<aRight<<endl;
			outfile<<"L"<<endl;
			outfile<<aMiddle<<endl;	
		}
	}

// Falls der Fressgraph keine Kanten hat, muss man noch 

// auf die richtige Seite fahren:
	else {
		outfile<<"L"<<endl;
	}
	outfile<<"F"<<endl;
	outfile.close();
	exit(0);		
}


inline bool isSpecial(int i) {
	return (i==aMiddle || i==aLeft || i==aRight);
}

1 11

2
3
5
7

Musterlösung

Naheliegende Lösung

#include <cstdio>

using namespace std;

// Ueberpruefung, ob p eine Primzahl ist
// Annahme: p ist nicht durch Zwei teilbar!
int is_prime (int p)
{
    // p ist hier auf keinen Fall mehr durch Zwei teilbar, deshalb
    // muessen nur noch ungerade Teiler ausprobiert werden.
    for (int i = 3; i * i <= p; i += 2)
        // p ist genau dann durch i teilbar,
        // wenn der rest der Division p / i = 0
        if (p % i == 0) return 0;
    // p war durch kein i teilbar, also ist p eine Primzahl
    return 1;
}

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    // 2 ist ein Sonderfall (und die kleinste moegliche Primzahl):
    if (A < 2) fprintf (fout, "2\n");
    // p ist die naechste ungerade Zahl nach A und wird um zwei
    // erhoeht, solange p < B, deshalb ist p immer ungerade, so
    // wie von der Funktion is_prime gefordert.
    for (int p = ((A+1)/2)*2 + 1; p < B; p+=2)
        // falls p eine Primzahl ist, wird p ausgegeben
        if (is_prime (p)) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
    return 0;
}

Es werden einfach alle Zahlen zwischen A und B auf ihre Primzahleigenschaft getestet und gegebenenfalls ausgegeben. Dieses Programm enthält schon einige Optimierungen:

• Es werden nur die ungeraden Zahlen zwischen A und B auf ihre Primzahleigenschaft getestet, die Zahl 2 wird als Sonderfall behandelt. Der Ausdruck, um die kleinste ungerade Zahl zwischen A und B zu finden ist etwas hässlich, aber erfüllt seinen Zweck: ((A+1)/2)*2 + 1.
• Da bekannt ist, dass keine Zahl, die getestet wird, durch Zwei teilbar ist, muss auch nur auf Teilbarkeit durch ungerade Zahlen ≥ 3 getestet werden.
• Die Teilbarkeit einer zu prüfenden Zahl p kann nur mit Teilern vorliegen, die nicht größer als die Wurzel von p sind.

Beim Primzahltest muss eigentlich nur auf Teilbarkeit durch Primzahlen getestet werden. So könnte eine weitere Optimierung aussehen.

Die Laufzeit des Algorithmus ist nicht leicht zu zeigen: die Funktion is_prime (p) hat im Mittel (für ausreichend großes N) eine Laufzeit, die nicht schlechter ist als log (p). Da p maximal B ist, kann die Laufzeit mit O (log (B)) angegeben werden. Diese Schleife wird etwa N/2 mal aufgerufen, wenn N den Abstand zwischen A und B bezeichnet, daher kann die Gesamtlaufzeit mit O(N * log (B)) angegeben werden.

Das Sieb des Eratosthenes

#include <cstdio>
#include <memory.h>

using namespace std;

// prime_array [p] ist 1, wenn die Zahl A + 1 + p
// keine Primzahl ist!
int not_prime [1000001];

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    memset (not_prime, 0, sizeof (not_prime));
    // alle Zahlen, die durch a teilbar sind als "nicht prim" markieren.
    for (int a = 2; a*a < B; a++) {
        int p_start = (A / a + 1) * a;
        if (p_start == a) p_start += a;

        // p ist zunaechst die Zahl nach A, die durch a teilbar (und nicht a selbst)
        // ist und wird dann so lange um a erhoeht, bis p >= B.
        for (int p = p_start; p < B; p += a)
            not_prime [p-A-1] = 1;
    }
    // alle Zahlen, die jetzt noch nicht "nicht prim" sind,
    // werden ausgegeben
    for (int p = A+1; p < B; p++)
        if (!not_prime [p - A - 1]) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
}

Das Sieb des Eratosthenes ist ein weit bekannter Algorithmus zum Suchen von Primzahlen. Es gibt ein Feld, in dem jedes Element einer Zahl zwischen A und B zugeordnet ist, und auf 1 gesetzt wird, sobald festgestellt wird, dass diese Zahl keine Primzahl ist. Nun werden zunüchst alle geraden Zahlen auf "nicht prim" gesetzt, anschließend alle durch drei teilbaren Zahlen, usw. Auch hier ist die Laufzeit nicht einfach zu zeigen, aber die äußere Schleife wird nur Wurzel (B) mal durchlaufen und die innere Schleife ist ähnlich wie die vorhergehende is_prime Funktion aufgebaut. Die tatsächliche Laufzeit dieses Algorithmus beträgt O (N * log (Wurzel (B))). Für große N und B ist er noch etwas zu langsam.

Dieses Verfahren ist auch sehr schön in der Wikipedia erklärt

Es gibt noch eine entscheidende Verbesserung, die auf obigen Algorithmus angewandt werden kann: die innere Schleife muss nicht für alle Zahlen unter Wurzel(B) ausgeführt werden, sondern lediglich für die Primzahlen. Um dies Sicherzustellen kann man alle Primzahlen im Vorhinein berechnen und nur noch diese verwenden:

#include <cstdio>
#include <list>
#include <memory.h>

using namespace std;

// prime_array [p] ist 1, wenn die Zahl A + 1 + p
// keine Primzahl ist!
int prime_array [1000001], primes [40000], pcount = 0;

void check_prime (int p)
{
    // auf Teilbarkeit durch andere Primzahlen testen
    for (int cp = 0; cp < pcount && primes [cp] * primes [cp] <= p; cp++)
        if (p % primes [cp] == 0) return;
    // diese Zahl ist eine Primzahl
    primes[pcount++] = p;
}

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    memset (prime_array, 0, sizeof (prime_array));
    primes [pcount++] = 2;
    for (int p = 3; p * p < B; p+=2) check_prime (p);
    // alle Zahlen, die durch a teilbar sind als "nicht prim" markieren.
    for (int ia = 0; primes [ia]*primes [ia] < B && ia < pcount; ia++) {
        int a = primes [ia];
        int p_start = (A / a + 1) * a;
        if (p_start == a) p_start += a;

        // p ist zunaechst die Zahl nach A, die durch a teilbar (und nicht a selbst)
        // ist und wird dann so lange um a erhoeht, bis p >= B.
        for (int p = p_start; p < B; p += a)
            prime_array [p-A-1] = 1;
    }
    // alle Zahlen, die jetzt noch nicht "nicht prim" sind,
    // werden ausgegeben
    for (int p = A+1; p < B; p++)
        if (!prime_array [p - A - 1]) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
}

Die Laufzeit für diesen Algorithmus liegt grob bei O(Wurzel (B) * log (Wurzel (B)) + N * log (Wurzel (B) / ln (Wurzel (B)))). Er ist für alle Eingabegrößen schnell genug.

5 6
NewYork
Philadelphia
LosAngeles
WashingtonDC
Chicago
NewYork Philadelphia 120
NewYork LosAngeles 174
LosAngeles Chicago 194
Chicago WashingtonDC 119
Chicago NewYork 145
WashingtonDC Philadelphia 92

NewYork
Philadelphia
WashingtonDC
Chicago
LosAngeles
NewYork

Lösungsidee

An den Beschränkungen Eingabegrößen kann man leicht erkennen, dass es für dieses Problem wohl (derzeit noch) keine effiziente Lösung gibt. Es müssen also alle Möglichkeiten, die Reise zu gestalten, nacheinander durchprobiert werden. Tatsächlich ist diese Aufgabe genau das Problem des Hamilton-Cycles, ein Standardproblem der Informatik. Das Problem ist eigentlich für Graphen definiert: Ist ein gegebener Weg, der jeden Knoten eines Graphen genau einmal besucht, optimal, d.h. ist die Summe seiner Kantengewichte minimal? Natürlich können und sollten die Städte und ihre Verbindungen ebenfalls als Graph interpretiert werden.

Die Aufgabe erfordet allerdings noch einen weiteren Algorithmus, denn es dürfen ja auch indirekte Verbindungen zwischen zwei Städten genutzt werden. Es kann also sein, dass zwei Städte, die in der Ausgabe direkt aufeinanderfolgen, gar nicht direkt miteinander verbunden sind. Deswegen muss auf jeden Fall der Abstand zwischen zwei beliebigen Städten bekannt sein. Es gibt mehrere Algorithmen, die den Abstand zwischen allen Knoten eines Graphen berechnen (All-Pairs Shortest-Paths), am gelaeufigsten und am einfachsten zu implementieren ist jedoch der Floyd-Warshall Algorithmus, der in O (N^3) läuft (wobei N die Anzahl der Knoten ist). Für N ≤ 9 auf jeden Fall ausreichend. (Vergleiche: Tomas H. Cormen et al: Introduction to Algorithms, p. 629)

Es gibt noch ein weiteres Problem, das angsprochen werden sollte: die Namen der Städte müssen auf irgendwelche IDs gemappt werden, damit das Problem vernünftig bearbeitet werden kann. Eine Möglichkeit dies zu tun ist es, alle Namen in einer Liste zu speichern und dann als ID die Position einer Stadt in der Liste zu verwenden. Für C++ bietet die STL allerdings eine wesentlich elegantere und effizientere Möglichkeit: die map Klasse. Die Implementation kann z.B. wie weiter unten aufgelistet geschehen.

Der Algorithmus geht wie folgt vor: Zunächst werden alle kürzesten Pfade ermittelt und in dem Array dist abgespeichert. dist [a][b] enthält dann die Länge der kürzesten Verbindung von a nach b. Anschließend werden mit der rekursiven Funktion find_route alle möglichen Abfolgen der Städte durchprobiert. Wenn ein neuer kürzester Weg gefunden wurde, wird dieser abgespeichert. Um den Suchbaum ein bisschen zu verkleinern, wird abgebrochen, sobald der aktuelle Weg länger als der kürzeste ist.

Laufzeit

Die Laufzeitanalyse ist relativ simpel. Da es sich um ein NP-vollständiges Problem handelt, kann die Laufzeit des All-Pairs Shortest-Paths Algorithmus vernachläsigt werden und die Laufzeit mit O (N!) angegeben werden.

Der Quelltext

#include <cstdio>
#include <map>
#include <string>
#include <list>

using namespace std;

FILE *fin = fopen ("reise.in", "r"),
     *fout = fopen ("reise.out", "w");

#define INFDIST 1000000

map <string, int> IDs;
map <int, string> Cities;


int dist [10][10],          // Distanz zwischen zwei Staedten A und B
    visited [10],           // wurde eine Stadt schon besucht
    min_dist = INFDIST,     // Laenge der kuerzesten Reise
    N, M;

list <int> cur_route,       // aktuell betrachtete Reise
           best_route;      // beste Reise

void find_route (int city, int cur_dist)
{
    int found = 0;

    // Wir koennen abbrechen, wenn die bestehende Route
    // laenger als die beste bisher gefundene ist.
    if (cur_dist > min_dist) visited [city] = 0;

    visited [city] = 1;

    for (int n = 0; n < N; n++) {
        if (!visited [n]) {
            found = 1;
            cur_route.push_back (n);
            find_route (n, cur_dist + dist [city][n]);
            cur_route.pop_back ();
        }
    }

    // Keine Staedte mehr zu besuchen?
    if (found == 0) {
        cur_dist += dist [city][IDs ["NewYork"]];
        // gibt es eine neue beste route
        if (cur_dist < min_dist) {
            cur_route.push_back (IDs ["NewYork"]);
            best_route = cur_route;
            min_dist = cur_dist;
            cur_route.pop_back ();
        }
    }

    visited [city] = 0;
}

int main ()
{
    fscanf (fin, "%d %d", &N, &M);

    for (int n = 0; n < N; n++) {
        char city [32];
        fscanf (fin, "%s", &city);
        int curID = (int)IDs.size ();
        IDs [city] = curID;
        Cities [IDs [city]] = city;
    }

    // zunaechst alle Entfernungen auf
    // das Maximum setzen und jede Stadt hat
    // zu sich selbst die Entfernung 0
    for (int a = 0; a < N; a++)
        for (int b = 0; b < N; b++)
            dist [a][b] = (a == b)?0:INFDIST;

    // direkte Verbindungen einlesen
    for (int m = 0; m < M; m++) {
        char A [32], B [32];
        int D;
        fscanf (fin, "%s %s %d", &A, &B, &D);
        dist [IDs [A]][IDs [B]] = dist [IDs [B]][IDs [A]] = D;
    }

    // All-Pairs Shortest-Paths Algorithmus
    // um indirekte Entfernungen zu ermitteln
    for (int c = 0; c < N; c++) {
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                // ist es kürzer von a nach c zu reisen und dann
                // von c nach b, als von a nach b direkt?
                if (dist [a][c] + dist [c][b] < dist [a][b])
                    dist [a][b] = dist [a][c] + dist [c][b];
            }
        }
    }

    // alle visited zustände auf 0 setzen
    for (int n = 0; n < N; n++)
        visited [n] = 0;

    // in NewYork geht es los
    cur_route.push_back (IDs ["NewYork"]);
    find_route (0, 0);

    // beste gefundene Reise ausgeben
    for (list <int>::iterator it = best_route.begin (); it != best_route.end (); it++)
        fprintf (fout, "%s\n", Cities [*it].c_str ());

    return 0;
}