Ergebnisse des 2. OWINF

Dies sind die Ergebnisse des 2. OWINF vom 22.04.2006. Wir gratulieren allen Teilnehmern ganz herzlich zu Ihrem Erfolg.

Die ersten 21 Plätze werden Urkunden erhalten und wurden diesbezüglich per Mail kontaktiert. Die Plätze 1, 2 und 4 – also die besten Schüler – wurden mit Büchergutscheinen belohnt.

Wir hoffen, daß allen Teilnehmern Spaß gemacht hat und bedanken uns für Eure Geduld bei den Verzögerungen.

Summe

Du sollst ein Programm schreiben, dass N Zahlen (1≤N≤500.000) summiert.

Jede dieser Zahlen liegt im Bereich -9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807 – sie paßt also in einen Int64 in Freepascal bzw. einen long long int in g++.

Eingabe

Die Eingabedatei summe.in enthält in der ersten Zeile die Zahl N. Jede weitere Zeile enthält genau eine der zu summierenden Zahlen.

Ausgabe

Die erste und einzige Zeile der Datei summe.out soll das Ergebnis enthalten, bzw. ein NEIN, falls das Ergebnis selbst nicht in den Zahlenbereich passt.

Limits

Memory: 10 MB
Laufzeit: 2 Sekunden

Beispiel

Lösung zu: Summe

Hinweis: Im folgenden wird der englische Begriff integer einfach eingedeutscht verwendet. Er bedeutet ganzzahlig oder ganze Zahl. Die Verwendung eines deutschen Äquivalents würde den Text unnötig verkomplizieren. Ebenso wird mit dem Begriff signed bzw. unsigned (vorzeichen-behaftet bzw. nicht vorzeichen-behaftet) verfahren.

Die Lösung der Aufgabe ist technisch relativ schwierig, vor allem da der Umgang mit 64-Bit Integern in C++ zwar inzwischen standardisiert, aber in Lehrbüchern und älteren Compilern Mangelware ist. Daher würde diese Aufgabe wohl nicht im Wettbewerb selbst vorkommen, obwohl es durchaus nützlich sein kann, zu wissen, wie man mit 64-Bit Integern rechnet.

Lösungsteil A: Datentyp wählen und richtig einlesen

Ein vorzeichenbehafteter 64-Bit Integer kann (in der Zweier-Komplement- Darstellung, die von handelsüblichen Rechnern verwendet wird) genau in dem in der Aufgabe angegebenen Bereich

[-9.223.372.036.854.775.808; 9.223.372.036.854.775.807]

liegen – die Zahlen der Eingabedatei können also in einen solchen eingelesen werden, wie in der Aufgabe angegeben war:

long long a;
scanf("%lld", &a);

bzw.

var a: Int64;
begin
  readln(a);

Details: Die Kodierung als Zweier-Komplement

Jeder Integer-Datentyp hat eine bestimmte Größe: Normalerweise arbeitet man heute mit 32-Bit Integern, da die meisten Prozessoren (wie auch der Auswertungsrechner) mit 32 Bits arbeiten. Sie können aber auch mit 8-, 16- oder 64-Bit Integern umgehen. Im folgenden beziehen sich die Beispiele auf einen 8-Bit Integer – sie gelten aber auch äquivalent für alle anderen Typen.

Zahlen werden im Computer als Bits, d.h. in der Binärdarstellung (oder auch im "Dualsystem") gespeichert:

Nun möchte man auch negative Zahlen darstellen können und gibt daher dem ersten Bit die Bedeutung des Vorzeichens.

Anstatt aber die Bedeutung der übrigen Bits einfach gleichzulassen, wie es in der Einer-Komplement-Darstellung der Fall ist

(Dies führt zu einigen Problemen, z.B. bei der Addition oder auch durch die zwei Möglichkeiten, die 0 darzustellen, nämlich als 00000000 und als 10000000.), interpretiert man Zahlen i, die eigentlich größer als 127 wären (also genau die, deren erstes Bit gesetzt ist), als i-256:

Interpretiert man das erste Bit als Vorzeichen, so spricht man von einem signed Integer. Interpretiert man alle Bits wie im üblichen Dualsystem ohne Vorzeichen, so spricht man von einem unsigned Integer.

Daher kann ein 8-Bit signed Integer Zahlen im Bereich [-128;127] darstellen (alle hier verwendeten Intervalle schließen ihre Grenzen mit ein), ein 8-Bit unsigned Integer jedoch Zahlen im Bereich [0;255].

Die Addition

Der Vorteil der Zweier-Komplement-Darstellung ist nun, daß signed Integers ohne Probleme "wie in der Schule gelernt" addiert werden können:

Allerdings kann man bei der Addition sehr leicht aus dem darstellbaren Bereich von [-128;127] herauskommen: Addiert man nämlich zwei zu große Zahlen (etwa 100 und 50) oder zwei zu kleine Zahlen (etwa -120 und -80), so kommt es zu komischen Phenomänen:

Das heißt 100+50=-106 und (-120)+(-80)=x?

Ja! Bei der zweiten Rechnung wird das neunte Bit, die führende 1, einfach weggelassen, da sie nicht mehr in den 8 Bits speicherbar ist. Also (-120)+(-80)=56.

Auch wenn diese Rechnungen mathematisch natürlich falsch sind, führt der Computer sie so aus. Man spricht vom Überlauf: Es ist 127+1=-128 und -128-1=127, vorausgesetzt natürlich, daß man mit 8-Bit signed Integern rechnet.

Für größere Zahlbereiche gilt entsprechendes:

Lösungsteil B: Überlauf erkennen und behandeln

Da auf 32-Bit-Prozessoren nur mit 64-Bit Integern und noch nicht mit 128-Bit Integern gerechnet werden kann, muss man diese Problematik auf jeden Fall berücksichtigen und irgendwie handhaben.

Die im letzten Abschnitt aufgelisteten Informationen kann man nun auf verschiedene Art und Weise verwenden, um das ursprüngliche Problem zu lösen:

Lösung 1: Überlauf vermeiden

So kann man versuchen, den Überlauf komplett zu vermeiden: Man addiert nur Zahlen, bei denen dies ohne Probleme geht, d.h. möglichst zu einer negativen eine positive oder umgekehrt.

Dazu sortiert man zunächst alle Zahlen der Größe nach. Dann summiert man die Zahlen einfach auf, wobei man die nächst kleinste verwendet, wenn die Summe momentan positiv ist, oder die nächst größte, wenn die Summe momentan negativ ist.

Das klappt allerdings nur so lange, wie es tatsächlich nicht zum Überlauf kommt, d.h. die richtige Ausgabe nicht NEIN ist. Tritt bei der Methode ein Überlauf auf, so wäre die richtige NEIN, die in diesem Fall ja auch ausgegeben werden muß. Aber wie entdeckt man, ob das passiert ist?

Nun ja: Hat man zu einer negativen Zahl eine negative addiert und ist das Ergebnis nicht mehr selbst negativ, so ist sicher etwas schiefgegangen – das ist der "Überlauf nach unten". Addiert man entsprechend zu einer positiven Zahl eine weitere positive Zahl und ist dann das Ergebnis negativ, so hat der Überlauf nach oben stattgefunden. In beiden Fällen kann man direkt NEIN ausgeben, da durch die Sortierung so ein Fall nur genau dann auftritt, wenn die endgültige Summe auch außerhalb des Bereiches liegt.

#include <cstdlib>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

// C99 defines int64_t in #include <stdint.h>, however, C++ does not
typedef long long int int64_t;


// copy_n is not part of the STL but defined by the commonly used
// SGI STL in #include <ext/algorithm>. For the sake of completeness
// it's repeated here
template <typename InputIterator, typename Size, typename OutputIterator>
pair<InputIterator, OutputIterator>
copy_n(InputIterator first, Size count, OutputIterator result) {
  for (; count > 0; count--) {
    *result = *first;
    ++first;
    ++result;
  }
  return pair<InputIterator, OutputIterator>(first, result);
}

int main() {
  ifstream fin("summe.in");
  ofstream fout("summe.out");

  std::vector<int64_t> numbers;
  int count;

  fin >> count;
  copy_n(istream_iterator<int64_t>(fin), count,
	 back_inserter(numbers));

  sort(numbers.begin(), numbers.end());

  std::vector<int64_t>::iterator begin, end;

  begin = numbers.begin();
  end = numbers.end();

  int64_t sum = 0;

  while (begin != end) {

    int64_t number = (sum >= 0 ? *begin++ : *--end);
    int64_t next_sum = sum + number;

    if ((number > 0 ? next_sum < sum : next_sum > sum)) {
      fout << "NEIN\n";
      return EXIT_SUCCESS;
    }
    sum = next_sum;
  }

  fout << sum << "\n";
  return EXIT_SUCCESS;
}

Das Programm hat wegen der Sortierung eine Laufzeit von O(N log N) und einen Speicherverbrauch von O(N).

Lösung 2: Überläufe erkennen und mitzählen

Ein anderer Ansatz geht von folgender Tatsache aus: Läuft das Zwischenergebnis beim Summieren von Zahlen genau so oft "nach oben" über wie "nach unten", so ist die normale Interpretation des Ergebnisses (also genau der Wert) wieder richtig.

Das kann man sich an folgendem 8-Bit-Beispiel klar machen:

(127 + 1) - 1 = 127.

Intuitiv ist das sofort klar. Der Computer jedoch wird zunächst

(127 + 1) - 1 = -128 - 1

rechnen und dann

-128 - 1 = 127.

Das Endergebnis ist genau dann "richtig", wenn die Anzahl der Überläufe nach oben genau die der Überläufe nach unten ist.

Daher zählt man diese einfach mit. Die Erkennung der Überläufe funktioniert genau gleich wie in der ersten Lösung:

#include <cstdlib>
#include <fstream>

using namespace std;

// C99 defines int64_t in #include <stdint.h>, however, C++ does not
typedef long long int int64_t;

int main() {
  ifstream fin("summe.in");
  ofstream fout("summe.out");

  int64_t sum = 0;
  int count;

  fin >> count;

  int overflow = 0, underflow = 0;

  while (count--) {
    int64_t number;

    fin >> number;

    int64_t next_sum = sum + number;

    if (number > 0 && next_sum < sum)
      overflow++;
    if (number < 0 && next_sum > sum)
      underflow++;

    sum = next_sum;
  }

  if (overflow == underflow)
    fout << sum << "\n";
  else
    fout << "NEIN\n";

  return EXIT_SUCCESS;
}

Das Programm hat eine Laufzeit von O(N) und eine Speicherverbrauch von O(1).

Lösung 3: Gleitkommazahlen

Eine weiter Möglichkeit ist die Verwendung von Gleitkommazahlen mit einer Mantisse von mindestens 64 Bits. Allerdings ist es generell bei dem Umgang mit Gleitkommazahlen recht schwierig und trickreich, immer alle Details zu beachten.

Eine Gleitkommazahl f wird im Rechner normalerweise als

f=p m 2^e

dargestellt, wobei

Die Größe der Mantisse und des Exponenten hängt nun von der verwendeten Architektur und vom Compiler ab. Auf dem Auswertungsrechner liefert ein long double genau eine 64-Bit Mantisse mit einem 15-Bit Exponenten. Zusammen mit dem Vorzeichen (1 Bit) kommt man also auf 80 Bits, also 10 Bytes.

Die 64 Bit der Mantisse mit dem 1-Bit-Vorzeichen erlauben nun die exakte Darstellung von ganzen Zahlen, wie es ein 65-Bit singed Integer tun würde. Die in der Eingabedatei vorkommenden Zahlen lassen sich also alle so darstellen.

Allerdings gibt es noch eine weitere Hürde: Summiert man die Zahlen einfach in der Reihenfolge auf, wie sie in der Eingabedatei vorkommen, so kann es zu Rundungsfehlern kommen (und wird es bei den Testdaten auch): Statt dem Überlauf, wo die führenden Bits verloren gehen, gehen hier einfach die letzten Bits verloren.

Das kann man vermeiden, indem man, sobald die Summe den Bereich [-2⁶³;2⁶³-1] verläßt, manuell einen Overflow nachprogrammiert und wie in Lösung 2 speichert, wie oft man diesen nach oben bzw. unten durchgeführt hat.

#include <cstdlib>
#include <fstream>

using namespace std;

// C99 defines int64_t in #include <stdint.h>, however, C++ does not
typedef long long int int64_t;

// C99 defines LLONG_MAX and LLONG_MIN in #include <limits.h>
#define LLONG_MAX    9223372036854775807ll
#define LLONG_MIN    (-LLONG_MAX - 1ll) 


int main()
{
  int count;

  ifstream fin("summe.in");
  ofstream fout("summe.out");

  fin >> count;

  long double sum = 0.0;
  int overflow = 0;

  while (count--) {
    int64_t value;
    fin >> value;
    sum += (long double)value;
    if (sum > (long double)LLONG_MAX) {
      sum -= (long double)LLONG_MAX;
      overflow++;
    } else if (sum < (long double)LLONG_MIN) {
      sum += (long double)LLONG_MAX;
      overflow--;
    }
  }

  switch (overflow) {

    case -1:
      sum -= (long double)LLONG_MAX;
      break;

    case 1:
      sum += (long double)LLONG_MAX;
      break;

    case 0:
      break;

    default:
      fout << "NEIN\n";
      return 0;
  }

  if (sum > (long double)LLONG_MAX || 
      sum < (long double)LLONG_MIN) {
    fout << "NEIN\n";
    return 0;
  }

  fout << (int64_t)sum << "\n";

  return EXIT_SUCCESS;
}

Manhattan

Nach einer langen Reise durch ganz Amerika ist Elmo endlich wieder in NewYork angekommen. Bevor er wieder nach Europa fliegen wird, möchte er sich noch den schönen Stadtteil Manhattan anschauen. Da er jedoch ein wenig kriminell aussieht, wird er inzwischen von Jack Bauer vom Geheimdienst verfolgt. Der würde gerne Elmo fangen, noch bevor er den Flughafen erreicht. Um seine Fangstrategie zu planen wüsste Jack gerne auf wie vielen Wegen Elmo Manhattan durchqueren kann. Dazu braucht er deine Hilfe.

• Manhattan ist eine rechteckige Stadt in der alle Straßen paralell oder rechtwinklig zueinander verlaufen. Alle Häuserblöcke zwischen diesen Straßen sind exakt gleich groß und quadratisch.
• Es gibt n Straßen in Ost-West-Richtung und m Straßen in Nord-Süd-Richtung. Man kann also für jede Straßenkreuzung Koordinaten angeben. Die Nordwestlichste Kreuzung hat die Koordinaten (0, 0) (hier ist Elmo angekommen). Die Südöstlichste Kreuzung hat die Koordinaten (n-1, m-1) (dort ist der Flughafen).
• Auf der Straße die um die Stadt herumführt ( (0,0) bis (0,m-1), (0,m-1) bis (n-1,m-1), (n-1,m-1) bis (n-1,0) und (n-1,0) bis (0,0) ) ist sehr viel Verkehr. Elmo kann zwar den Gehweg entlanglaufen, aber ein Überqueren dieser Straße wäre viel zu gefährlich.
• Von einer Kreuzung zur nächsten braucht Elmo genau eine Minute. In der gleichen Zeit könnte er auch eine diagonale Abkürzung zwischen den Häuserblöcken verwenden. Also zum Beispiel von Kreuzung (2,3) nach (3,4). Allerdings ist sich Jack Bauer noch nicht sicher, ob Elmo vielleicht lieber nur die interessanteren Wege die Hauptstraßen entlang verwendet.
• Alle Ergebnisse passen in ein 32 Bit signed Integer, sind also kleiner gleich 2147483647.

Dein Programm soll also die folgenden vier Fragen für Jack Bauer beantworten:

1. Wie lang braucht Elmo für den schnellsten Weg, wenn er nicht diagonal geht?
2. Wieviele verschiedene schnellste Wege kann Elmo gehen, wenn er nicht diagonal geht?
3. Wie lang braucht Elmo für den schnellsten Weg, wenn er auch diagonal geht?
4. Wieviele verschiedene schnellste Wege kann Elmo gehen, wenn er auch diagonale Abkürzungen verwendet?

Eingabe (manhattan.in)

Ausgabe (manhattan.out)

Beispiel

Eingabe (manhattan.in)

Ausgabe (manhattan.out)

Limits

Inkrementelle Punktevergabe

Für jede richtige Zahl gibt es 20% der Punkte. Falls ihr alles richtig habt, gibt es nochmals 20%. Damit ihr nicht unter einem Timeout leidet, solltet ihr sobald wie möglich die Zahlen in die Ausgabedatei schreiben und die dann flushen. Dies geht wie folgt:

In C:

#include <cstdio>
int main() {
        FILE* f = fopen("tim.out", "w");
        fprintf(f, "bar\n");
        fflush(f);
        for (int i = 0; i < 2 ; i=1-i) ;
}

In C++:

#include <fstream>

using namespace std;

int main() {
        ofstream tim("tim.out", ios::out);
        tim << "bar\n";
        tim.flush();
        for (int i = 0; i < 2 ; i=1-i) ;
}

In Pascal:

program ti;
var tim:textfile;
    i:integer;
begin
  assign(tim, 'tim.out');
  rewrite(tim);
  writeln(tim, 'bar');
  flush(tim);
  i := 0;
  while (i < 3) do
    i := 1 - i;
end.

Lösung zu: Elmo in Manhattan

Für jede Frage muss eine Antwort gefunden werden, also beantworten wir die Fragen einfach der Reihe nach:

Frage 1

Mit einer kleinen Skizze kann man recht schnell erkennen, dass Elmo immer n-1 Straßenstücke nach unten und m-1 Straßenstücke nach rechts gehen muss. Die Antwort ist also n+m-2.

Frage 2

Hier wird es etwas komplizierter. Zuerst eine anschauliche Lösung mit dynamischer Programmierung, später dann die deutlich bessere kombinatorische Lösung.

Dynamische Programmierung

Wenn Elmo an einer Straßenkreuzung ankommt, so kommt er immer von Norden oder von Westen her. Ansonsten wäre er nämlich ein Stück zurück gelaufen und nicht mehr auf dem kürzesten Weg. Die Anzahl der möglichen Wege durch den Straßenknoten (i,j) ist also genau die Summe der Wege durch (i-1,j) plus der Summe der Wege durch (i,j-1). Es gibt nur eine Möglichkeit zu einer Kreuzung am Nord- oder Ostrand zu kommen. Man kann also eine Tabelle aufstellen, in der diese Werte nacheinander berechnet werden. Die Antwort steht am Ende an der Stelle (n-1,m-1) in der Tabelle. Ein Programm, dass diese Tabelle berechnet sieht zum Beispiel so aus:

#include <iostream>
#include <fstream>

using namespace std;

int main() {
int n,m; // Größe von Manhattan

ifstream infile("elmo.in");
infile >> n;
infile >> m;
int table[n][m];
// Anfangswerte:
for(int i=0; i<n; i++) table[i][0] = 1;

for(int i=1; i<m; i++) table[0][i] = 1;
// Rest der Tabelle füllen:
for(int i=1; i<n; i++) {
	for(int j=1; j<m; j++) {
		table[i][j] = table[i-1][j] + table[i][j-1];
	}
}
cout <<"Antwort auf Frage 2: "<< table[n-1][m-1]<<endl;
}

Dieses Programm lässt sich noch ein wenig optimieren, insbesondere der Speicherverbrauch ist quadratisch und könnte durch 'vergessen' der bereits berechneten Werte linear werden. Außerdem ist die berechnete Tabelle symmetrisch, es werden also viele Werte doppelt berechnet.

Eine weit bessere Lösung ist jedoch der folgende kombinatorische Ansatz.

Kombinatorik

Aus der ersten Antwort wissen wir, dass Elmo n-1 Straßenstücke in südlicher Richtung und m-1 Straßenstücke in östlicher Richtung entlanggeht. Da Manhattan ein vollständiges Gitter (Grid) ist, ist es egal in welcher Reihenfolge er diese Straßenstücke benutzt.

Gesucht ist also die Anzahl der möglichen Anordnungen mit Beachtung der Reihenfolge von insgesamt n+m-2 Dingen, von denen n-1 zu einer Sorte und m-1 zu einer anderen Sorte gehören.

Die Kombinatorik kennt für dieses Problem eine Lösungsformel: (n+m-2)!/((n-1)!*(m-1)!)

Diese könnte direkt implementiert werden, was aber zu Problemen mit größeren Zahlen führt. Ab n+m = 11 würde im Zähler eine Zahl stehen, die zu groß für den 32-Bit Integerbereich ist. Auch die Verwendung von 64-Bit-Zahlen bringt relativ wenig, damit würde man bis n+m = 20 kommen. Die Aufgabenstellung sichert jedoch nur zu, dass das Ergebnis in eine 32-Bit-Zahl passt. Da jedoch auch der Nenner sehr groß werden kann, ist es trotzdem möglich, dass der Zähler nicht mehr in eine 64-Bit-Zahl passt.

Es würde sich also anbieten Funktionen zum Rechnen mit beliebig langen Ganzzahlen zu verwenden. Da solche jedoch leider nicht in jeder Programmiersprache enthalten sind und die Verwendung von externen Bibliotheken beim OWINF nicht erlaubt ist, Werden wir eine andere Lösung suchen.

Die eine Fakultät im Nenner kann sofort mit dem Zähler gekürzt werden. Bei der anderen Fakultät ist das kürzen etwas komplizierter, aber nicht wirklich schwierig. Daher wird der Bruch zuerst vollständig gekürzt und dann die Reste des Zählers multipliziert. So ist sichergestellt, dass nie mit Zahl, die größer als das Ergebnis sind, gerechnet werden muss.

Da wir wissen, dass das Ergebnis eine Ganzzahl ist, lassen sich alle Faktoren des Nenners kürzen. Für jeden Faktor im Nenner kann der größte gemeinsame Teiler mit einem Faktor im Zähler mit dem Euklidischen Algorithmus berechnet werden. Durch diesen werden beide geteilt. Falls ein Rest im Nenner verbleibt, kann dieser mit einem anderen Faktor im Zähler gekürzt werden.

Frage 3

Immer wenn Elmo ein Stück diagonal geht, kommt er ein Stück nach Süden und eines nach Osten weiter. Er spart also eine Minute. Der kürzeste Weg ist also der, der möglichst viele diagonale Wege enthält. Wenn n≥m ist, geht er also diagonal durch m-1 Häuserblöcke. Dann bleiben noch n-m Stücke in östlicher Richtung. Insgesamt also n-1. Im anderen Fall analog m-1.

Frage 4

Diese Frage ist sehr ähnlich zur zweiten und kann auch kombinatorisch gelöst werden. Wieder ist es egal in welcher Reihenfolge die Teilstücke gegangen werden. Wenn n≥m ist, gibt es n-m gerade und m-1 diagonale Straßenstücke. Das macht insgesamt (n-1)!/((n-m)!*(m-1)!) Möglichkeiten, die analog zu Frage 2 berechnet werden.

Quelltext

Dateiname: manhattan.cpp

#include <iostream>

#include <fstream>

using namespace std;

inline int euklid(int, int);

inline int facfrac(int, int, int);

int main() 
{
// Eingabe

	int n,m; // Größe von Manhattan
	ifstream infile("manhattan.in");
	infile >> n;
	infile >> m;
	if(m>n) {
		int t = m;
		m = n;
		n = t;
	}


// Ausgabe
	ofstream outfile("manhattan.out");
// erste Antwort:
	outfile<<m+n-2<<endl;

// zweite Antwort:
	outfile<<facfrac(n+m-2, n-1, m-1)<<endl;
// dritte Antwort:
	outfile<<n-1<<endl;

// vierte Antwort:
	outfile<<facfrac(n-1, n-m, m-1)<<endl;;

// Fertig:
        outfile.close();
        exit(0);
}


/*

 Berechnet x!/(a!*b!)

*/
inline int facfrac(int x, int a, int b)
{
// Alle Faktoren im Zähler berechnen, dabei kann

// a! schon gekürzt werden
	int numerator[x-a];
	for(int i=(a+1); i<=x; i++)
	{
		numerator[i-(a+1)] = i;
	}

// Die übrigenFaktoren im Zähler 
// werdem mit jedem Faktor aus b! gekürzt:

	for(int denom=2; denom<=b; denom++)
	{
		int thisDenom = denom;
		for(int num=0; thisDenom>1; num++)
		{
			if(num == x-a) cout<<"ERROR!!!!!!!!!!!!"<<endl;

// Kürzen mit dem ggT
			int gcd = euklid(thisDenom, numerator[num]);
			thisDenom/=gcd;
			numerator[num]/=gcd;
		}
	}

// Alle übrigen Faktoren im Zähler miteinander

// multiplizieren:

	int res = 1;
	for(int i=0; i<(x-a); i++) res*=numerator[i];
	return res;
}


/*
 Berechnen des größten gemeinsamen
 Teilers von a und b mit dem 
 euklidischen Algorithmus
*/
inline int euklid(int a, int b)
{
    while( 1 )
    {
	a = a % b;
	if(a == 0)
		return b;
	b = b % a;
	if(b == 0)
		return a;
    }
}

Das Mobile Problem

Heinrich hat für sein Spielwarengeschäft „Auerbachs Spielkeller“ eine Lieferung Mobiles erhalten. Sie bestehen aus runden Figuren, die durch Schnüre miteinander verbunden sind. Die Lieferung erhält unterschiedliche Typen von Mobiles, die jeweils mit einem oder mehreren Exemplaren vertreten sind. Leider ist die Lieferung unsortiert. Um die Mobiles in seinen Verkaufsräumen anbieten zu können, muss Heinrich sie also erst noch nach gleichen Typen sortieren. Kannst du ein Programm schreiben, dass ihm dabei hilft?

Mobile Repräsentation

Heinrich hat eine ASCII Darstellung der Mobiles vorbereitet, damit dein Programm sie leichter analysieren kann. Die Figuren stellt er dabei als O (das ist der Buchstabe O, nicht die Zahl 0) dar und die Verbindungsschnüre als waagerechte, senkrechte oder diagonale ASCII Linien durch die Zeichen - (Bindestrich), | (senkrechter Strich), / (slash) und \ (backslash). Dabei gehört ein Bindestrich zu der selben Line, wie der Bindestrich links und der Bindestrich rechts von ihm. Ein senkrechter Strich gehört zur selben Line, wie der senkrechte Strich über und unter ihm. ein Slash Gehört zur selben Linie, wie der slash links unter ihm und der slash rechts über ihm. Beim Backslash verhält es sich analog. Eine Linie „knickt“ niemals ab. Sie besteht immer nur aus einer Sequenz ein und desselben Zeichens. Außerdem endet eine Linie immer in einer Figur (O). Eine Figur gilt nur dann als verbunden mit einer Linie (und damit die Figur als verbunden mit der Schnur), wenn die Linie aus Bindestrichen besteht und von links bzw. von rechts an sie grenzt oder aus senkrechten Strichen besteht und von oben bzw. unten an sie grenzt, etc.

Dies sind korrekte Darstellungen von Mobiles:

O---O O \ / O-O O O | O

Dies sind fehlerhafte Darstellungen von Mobiles:

O / O O-- O-- O/ OO ---

Bei der Überprüfung auf Gleichheit zweier Mobiles, ist die Länge der Schnüre zu ignorieren. Auch sind alle Figuren gleich. Allerdings hat Heinrich die Mobiles so „abgezeichnet“, wie sie im Karton lagen. Zwei gleiche identische Mobiles können also auf den ersten Blick durchaus unterschiedlich aussehen. Die folgenden beiden Mobiles sind beispielsweise identisch:

O---O | / | / |/ O O / \ O---O

Eingabe

Die Eingabedatei mobiles.in enthält die ASCII Darstellungen der gelieferten Mobiles. In der ersten Zeile der Datei steht die Anzahl 1 ≤ n ≤ 1000 der gelieferten Mobiles. In der zweiten Zeile stehen 1 ≤ w, h ≤ 30.

Es folgen n Blöcke von jeweils h Zeilen Länge, die jeweils w Zeichen breit sind (plus das anschließende Newline Zeichen). Jeder dieser Blöcke enthält die ASCII Repräsentation eines der gelieferten Mobiles. Er besteht also ausschließlich aus den Zeichen - | / \ und dem Leerzeichen (plus die Newlines am Zeilenende). Beachte: Jede Zeile ist exakt w Zeichen lang. Gegebenenfalls sind die Zeilen mit Leerzeichen aufgefüllt oder bestehen gänzlich aus Leerzeichen.

Es wird garantiert, dass nie mehr als 20 Figuren am Mobile hängen.

Ausgabe

Schreibe in die erste Zeile der Datei mobiles.out die Anzahl m von unterschiedlichen Mobile-Typen, die du gefunden hast. Für jeden der m Typen soll eine Zeile folgen, die durch Leerzeichen separiert die Nummer der Eingabe-Blöcke enthält, die ein Mobile vom jeweiligen Typ beschrieben haben.

Limits

Memory: 10 MB
Laufzeit: 1 Sekunde

Beispiel

Lösung zu: Mobiles

Bei diesem Problem handelt es sich "einfach" um das der Graphen-Isomorphie.

Zwei Graphen (bestehend aus Knoten und Kanten) heißen isomorph, wenn es eine Eins-zu-Eins-Zuordnung zwischen ihren Knoten und Kanten gibt, so daß entsprechende Kanten genau ihre entsprechenden Knoten verbinden. Anders formuliert: Wenn die beiden Mobiles wie in der Aufgabe beschrieben genau "gleich" sind.

Die Komplexität des Tests auf Graphen-Isomorphie ist unbekannt, es wird im allgemeinen zwischen P und NP angesiedelt. Der übliche Ansatz ist ein optimiertes Backtracking über alle möglichen Eins-zu-Eins-Zuordnungen der Knoten, von denen es bei N Knoten N! gibt.

Stadt

In Süd-Berlin soll ein neues Stadtviertel entstehen. Im Gegensatz zu normalen Stadtvierteln soll dieses neue Stadtviertel jedoch von vorne bis hinten druchgeplant werden, damit ein vollständiges und konsistentes Design entsteht, um Süd-Berlin zu repräsentieren.

Unter anderem müssen auch die Glasfaserkabel für die Standleitungen, die serienmäßig in jeder Wohnung vorzufinden sind, verlegt werden. Nun ist es allerdings so, dass eine Glasfaserleitung nicht nur von einem Haus verwendet wird, sondern direkt zu anderen Häusern weiterverlegt werden kann. Da natürlich die finanziellen Mittel knapp sind, wird nun ein Netzwerk gesucht, welches alle Häuser irgendwie (evtl. indirekt) miteinander verbindet, und dabei so wenig Glasfaserkabel wie möglich verwendet. Die Koordinaten aller geplanten Häuser sind bekannt und liegen als ganzzahlige Werte zwischen 0 und 1000 (inklusive) vor. Die Leitungen können auf jeden Fall auf direktem Weg zwischen jedem beliebigen Häuserpaar verlegt werden und alle Verbindungen sind bidirektional.

Nun wurde Elmo beauftragt, ein entsprechendes Netzwerk zu finden. Leider hat er jedoch einen wichtigen Fernsehauftritt bei Viva und deshalb musst du ihm helfen! Schreibe ein Programm, welches die Koordinaten von bis zu 1000 Häusern einliest und ein Netzwerk ausgibt, welches so wenig Glasfaserkabel wie möglich verbraucht, ausgibt.

Eingabe (stadt.in)

Ausgabe (stadt.out)

Beispiel

Eingabe (stadt.in)

Ausgabe (stadt.out)

Details

Jede der Verbindungen hat eine Länge von 2.00 Längeneinheiten. Da es vier Verbindungen gibt, werden insgesamt 8.00 Längeneinheiten Glasfaserkabel benötigt.

Limits

Lösungsidee