Round 2H

Was ist ein Graph?

Als Graphen bezeichnen wir eine Menge von Punkten und Verbindungen zwischen diesen Punkten. Die Punkte werden meist Knoten und die Verbindungen zwischen Punktepaaren meist Kanten genannt. Im Bild 1 siehst du ein Beispiel eines solchen Graphen. Jeder Kreis ist ein Knoten und jede Linie, die zwei solche Knoten verbindet, ist also eine Kante.

Bild 1: Ein Beispiel für einen Graphen mit 6 Knoten und 5 Kanten.

Dieser Graph besteht also aus 6 Knoten und 5 Kanten. Eine der fünf Kanten verläuft zwischen Knoten $2$ und $3$, daher sagen wir, dass Knoten $2$ mit Knoten $3$ benachbart ist. Die beiden Knoten sind auch indirekt benachbart, nämlich über den gemeinsamen Nachbarn $4$. Häufig sprechen wir von der Nachbarschaft eines Knotens, was einfach die Menge aller Nachbarn bezeichnet. Die Nachbarschaft von $3$ sind die Knoten $1$, $2$ und $4$ und die Nachbarschaft von $2$ sind die Knoten $3$ und $4$.

Einen Graphen so aufzuzeichnen ist eine Art ihn darzustellen. Auf die genaue Zeichnungsart kommt es uns aber gar nicht an. Wenn wir die Knoten ein wenig verschieben und die Kanten entsprechend mitbewegen, sagen wir immer noch, dass dies derselbe Graph ist. Es muss auch gar nicht unbedingt eine solche Zeichnung sein, wir können einen Graphen auch einfach als abstrakte Liste von Knoten und Kanten beschreiben. Dazu benennen wir oft die Knotenmenge mit $V$ (Englisch vertices) und die Kantenmenge mit $E$ (Englisch edges). Das Beispiel im Bild 1 wäre dann $V = \{1,2,3,4,5,6\}$ und $E=\{ \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}, \{5,6\} \}$. Die Anzahl Knoten bezeichnen wir meist mit $n$ (im Beispiel ist $n=6$) und die Anzahl Kanten mit $m$ (im Beispiel ist $m=5$).

Wie sieht ein Graph im Computer aus?

Wenn wir nun in einer Aufgabe der SOI einem solchen Graphen begegnen, so ist dieser meist nicht als Bild gegeben, sondern als solch eine abstrakte Auflistung der Knoten und Kanten. Die Knoten sind dann meist einfach von $1$ bis $n$ nummeriert und so enthält die Eingabe nur eine Zeile mit $n$ und $m$ und dann $m$ Zeilen mit den Punktepaaren der $m$ Kanten. Etwa so (für das Beispiel in Bild 1):

6 5
1 3
2 3
2 4
3 4
5 6

Und was machen wir jetzt damit? Wie repräsentieren wir diesen Graphen nun in unserem Programm, sodass wir nützliche Dinge damit anstellen können? Wir könnten einfach diese Kantenliste so einlesen und abspeichern. In C++ sähe das vielleicht etwa so aus:

int n = 6;
int m = 5;
vector<pair<int,int>> E = {{1,3}, {2,3}, {2,4}, {3,4}, {5,6}};

Eine solche Kantenliste ist manchmal gut genug und kann alles was wir brauchen. Häufig aber wollen wir auf den Nachbarschaften von Knoten operieren, d.h. wir wollen alle Nachbarn eines Knotens $x$ abfragen, was mit einer Kantenliste nur möglich ist, indem wir alle Kanten durchgehen und schauen ob $x$ irgendwo vorkommt.

SOI-typische Graphenaufgaben haben oft bis zu $100\,000$ Kanten, und da kann eine solche lineare Suche durch die Kantenliste schon mal etwas länger dauern. Deshalb ist die nützlichste Speicherart für Graphen eine andere, nämlich die sogenannte Adjazenzliste. Die Idee ist simpel: Statt einer grossen langen Liste mit allen Kanten merken wir uns für jeden Knoten eine separate Liste mit all seinen Nachbarn. Die Datenstruktur besteht also aus $n$ Listen, und wenn wir die Nachbarschaft des Knotens $x$ wissen wollen, schauen wir einfach die $x$-te dieser Listen an.

Implementieren lässt sich das in C++ ganz leicht mittels Vektoren, den Arrays dynamischer Grösse (hat nicht viel mit den Vektoren aus der Mathe zu tun). Wir verschachteln dazu $n$ Vektoren in einen grossen Vektor - die inneren Vektoren sind die Nachbarschaftslisten und der äussere Vektor hält sie alle zusammen. Ein wenig müssen wir noch wegen der nullbasierten Indexierung aufpassen: entweder wir wandeln alles in nullbasierte Indexierung um (was häufig einfacher geht), oder wir fügen einfach noch einen imaginären Knoten $0$ ohne Nachbarn hinzu:

int n = 6;
int m = 5;
// Erste Variante mit nullbasierte Knoten (von 0 bis n-1 nummeriert):
vector<vector<int>> E = {{2}, {2,3}, {0,2,3}, {1,2}, {5}, {4}};
// oder mit einem 0-ten Knoten ohne Nachbarn:
vector<vector<int>> E = {{}, {3}, {3,4}, {1,3,4}, {2,3}, {6}, {5}};
// Die Nachbarn von Knoten x sind dann in E[x] zu finden.

Was stellt ein Graph dar?

Ein solcher Graph kann nun für alles mögliche stehen - zum Beispiel für den Strassenplan einer Stadt. Die Knoten stehen dann für die Kreuzungen und Plätze der Stadt und die Kanten für die Strassen dazwischen. Was wir häufig wissen wollen ist zum Beispiel der kürzeste Weg zwischen zwei Knoten (Wie komme ich am schnellsten zum Bahnhof?) oder ob es überhaupt möglich ist, von jedem Ort an jeden anderen zu kommen (Gibt es eine Insel von der man nicht mehr wegkommt?).

Manchmal sind dafür noch Zusatzinformationen zu den Knoten und Kanten gegeben, zum Beispiel eine Fahrtzeit pro Kante (ein sogenanntes Kantengewicht) oder eine Richtung pro Kante (z.B. für Einbahnstrassen). In diesem Kapitel schauen wir uns aber vorerst nur mal ungewichtete, ungerichtete Graphen an.

Was ist nun diese ominöse DFS?

Nun wollen wir uns an den ersten Algorithmus für Graphen heranwagen. Es ist die sogenannte Tiefensuche, oft abgekürzt mit DFS, vom Englischen Depth First Search. Sie ist eine von zwei sogenannten Graphentraversierungsalgorithmen, die in den Rucksack eines jeden Informatik-Olympioniken gehören. Den anderen, die Breitensuche (BFS), schauen wir gleich nachher an. Bei beiden geht es darum, den Graphen systematisch zu erkunden und zu entdecken oder eben zu traversieren.

Stell dir vor du steckst mitten in einem Labyrinth. Das Labyrinth beschreiben wir als Graphen mit den Räumen als Knoten und den Gängen zwischen den Räumen als Kanten. Wir stecken nun völlig verloren im Raum/Knoten Nr. $1$ und suchen den Ausgang (sei dies Knoten $n$). Alle Räume sehen etwa gleich aus und wir haben keinen Lageplan, kein GPS, kein Wifi und auch sonst kaum Hilfsmittel. Alles was wir haben ist ein langer roter Faden und ein grosser Topf mit roter Farbe.

Wie finden wir nun den Ausgang aus dem Labyrinth? Unsere Strategie ist die folgende: Wir fixieren den Faden, den wir nachher während unserem Erkundungsgang abrollen werden, in unserem Startraum, sodass wir den Weg zurück zu diesem Startraum stets wieder finden können. Ausserdem malen wir einen roten Punkt auf den Boden, um zu markieren, dass wir den Startraum schon besucht haben. Wir starten in eine beliebige Richtung und machen in jedem neuen Raum folgendes: Wir malen einen roten Punkt auf den Boden, damit wir wissen, dass wir hier schon waren und klappern dann der Reihe nach von links nach rechts alle ausgehenden Gänge ab. Das heisst wir gehen zuerst dem linkesten Gang entlang und kommen so wieder in einen neuen Raum. Dort bringen wir eine Markierung an und gehen wieder dem linkesten Gang nach weiter. Irgendwann kommen wir so in eine Sackgasse oder in einen Raum in dem wir schon einmal waren (der also schon eine rote Markierung auf dem Boden hat). In einem solchen Fall kehren wir einfach um und gehen zurück zum Raum aus dem wir gekommen sind (der rote Faden sagt uns wo das war). Von dort probieren wir es mit dem nächsten Gang, den es noch zu erkunden gilt (den nächsten von links) und wiederholen das gleiche Verfahren. So probieren wir systematisch Gang für Gang durch. Haben wir auch den letzten, rechtesten Gang erkundet, so beenden wir die Suche in diesem Raum und gehen einen Gang zurück in Richtung Startraum (indem wir dem roten Faden folgen). Auf diese Weise finden wir früher oder später den Ausgang oder wissen, dass er vom Start aus unerreichbar ist.

Algorithmus: Tiefensuche

Genau so funktioniert nun auch die Tiefensuche. Den Farbtopf simulieren wir mit einem booleschen Array, also einem Bit pro Raum, mit dem wir uns merken, ob wir einen bestimmten Raum schon besucht haben oder nicht. Den Faden repräsentieren wir nur implizit, nämlich mit dem rekursiven Aufruf-Stack unserer DFS-Funktion. Das heisst in jedem Aufruf der DFS-Funktion besuchen wir einen neuen Knoten und rufen die Funktion rekursiv für alle von dort benachbarten, noch nicht besuchten Knoten auf. In C++ Code sieht das dann etwa so aus:

// Wir nehmen an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(!visited[w]) {
                        visited[w] = true;
                        dfs(w);
                }
        }
}

int main() {
        // Wir beginnen damit E einzulesen, z.B. so:
        int n, m;
        cin >> n >> m;
        E = vector<vector<int>>(n);
        for(int i = 0; i < m; i++) {
                int a, b;
                cin >> a >> b;
                E[a].push_back(b);
                E[b].push_back(a);
        }
        // Nun können wir unsere Tiefensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        dfs(start);
        // Ob der Ausgang erreicht werden kann, können wir nun ganz leicht ablesen.
        cout << "Kann der Ausgang erreicht werden?\n";
        if(visited[n-1]) {
                cout << "Ja!\n";
        } else {
                cout << "Nein!\n";
        }
}

Und wozu ist das gut?

Eine solche Tiefensuche kann uns also beantworten, ob zwei Knoten direkt oder indirekt verbunden sind oder nicht. Die Menge aller Knoten, die gegenseitig miteinander verbunden sind, nennt man auch Zusammenhangskomponente. Der Graph in Bild 1 besteht aus zwei solchen Zusammenhangskomponenten. Die Knoten $1$ bis $4$ bilden die eine, die Knoten $5$ und $6$ die andere Komponente. Um alle Zusammenhangskomponenten mittels Tiefensuche zu bestimmen, gehen wir einmal durch alle Knoten und starten bei jedem noch unbesuchten Knoten eine Tiefensuche. Jedesmal wenn wir eine neue Tiefensuche starten, entdecken wir eine neue Komponente.

Eine weitere nützliche Anwendung ist das Zweifärben von Graphen. Wir möchten dabei jeden Knoten eines Graphen entweder rot oder blau einfärben, sodass keine zwei benachbarten Knoten dieselbe Farbe bekommen. Ist das immer möglich? Nein. In einem Dreieck geht das beispielsweise nicht. Wenn du dir das ein wenig genauer überlegst, siehst du, dass eine gültige Zweifärbung genau dann möglich ist, wenn der Graph keinen Zyklus ungerader Länge enthält, es also keinen Weg gibt, der nach einer ungeraden Anzahl Schritte wieder bei seinem Startpunkt angelangt.

Der Graph in Bild 1 ist nicht zweifärbbar, da das Dreieck $2-3-4$ eine Zweifärbung verunmöglicht. Bild 2 zeigt dir einen zweifärbbaren Graphen.

Bild 2: Ein Beispiel eines zweifärbbaren Graphen, der aus zwei Zusammenhangskomponenten besteht.

Eine Art eine solche Färbung zu finden (oder herauszufinden, dass es gar keine solche gibt) ist mittels Tiefensuche. Wenn wir den Startknoten rot markieren, dann müssen alle seine Nachbarn blau sein und alle deren Nachbarn wieder rot und so weiter. Sobald wir also die Farbe des Startknotens wählen, ist die Färbung für die gesamte Zusammenhangskomponente fixiert. Die Tiefensuche erlaubt uns nun diese Färbung zu simulieren und gleichzeitig zu überprüfen, ob es irgendwo zu einem Konflikt kommt, also zu zwei gleichgefärbten, benachbarten Knoten. In der Implementierung ersetzen wir dazu einfach “visited” durch “color”, wobei wir 0 für ungefärbt, 1 für rot und 2 für blau stehen lassen. Innerhalb der DFS-Schleife prüfen wir dann:

bool dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(color[w]==0) {
                        // Setze w auf die andere Farbe als v.
                        color[w] = 3-color[v];
                        // Rekursiere und brich ab, sobald ein Fehler gefunden wurde:
                        if(!dfs(w)) {
                                return false;
                        }
                } else {
                        // Prüfe, dass v und w unterschiedliche Farbe haben.
                        if(color[v] == color[w]) {
                                // Der Graph ist in diesem Fall nicht zweifärbbar, was wir beispielsweise mit dem Rückgabewert mitteilen können.
                                return false;
                        }
                }
        }
        return true;
}

Eingabe

Auf der ersten Zeile steht die Zahl $T$, die Anzahl Testfälle. Es folgen $T$ Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht $n$ und $m$, die Anzahl Knoten und Kanten. Anschliessend folgen $m$ Zeilen, welche die $m$ Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit $a$ und $b$ bedeutet, dass der Knoten $a$ mit Knoten $b$ verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von $0$ bis $n-1$ nummeriert.

Ausgabe

Gib für den $t$-ten Testfall “Case #t:” aus, gefolgt von “YES” oder “NO”, je nachdem ob der $t$-te Graph zweifärbbar ist oder nicht.

Limits

• $T=100$
• $N \le 1\,000$
• $M \le 10\,000$

Beispiele

1
6 5
0 2
1 2
1 3
2 3
4 5

Case #1: NO

1
7 6
0 1
2 1
5 3
4 3
4 6
5 6

Case #1: YES

Bild 3: Der zweifärbbare Graph des zweiten Beispiels.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Anmerkung: Eine Anwendung dieses Zweifärbeproblems war die erste Hälfte der Aufgabe “River” der ersten Runde der SOI 2015. Du kannst die Aufgabe hier nachlesen und du findest hier die Lösungsbeschreibung.

Breitensuche - Woher kommt der Name?

In der Tiefensuche stürzten wir uns Hals über Kopf in die Tiefe des Graphen. Wir schlugen einfach mal eine willkürliche Richtung ein und gingen so lange weiter bis wir umkehren mussten, weil wir nichts Neues mehr entdecken konnten. Erst dann schauten wir uns nach möglichen alternativen Abzweigungen um.

Die Breitensuche geht nun - wie der Name suggeriert - zuerst in die Breite statt in die Tiefe. Wir wollen zuerst alles erkunden, was unmittelbar zum Startpunkt benachbart ist. Erst danach schauen wir uns Knoten mit Distanz $2$ an, also die Nachbarn der Nachbarn. Und erst wenn wir alle diese Nachbarn zweiten Grades besucht haben, dann erst beginnen wir mit den Nachbarn der Nachbarn der Nachbarn. Und so weiter.

Algorithmus: Breitensuche

Diese Idee lässt sich am einfachsten mit Hilfe einer Warteschlange (Englisch queue) implementieren. Darin merken wir uns alle Knoten, die wir entdeckt haben, deren Nachbarn wir uns aber noch anschauen wollen.

Bei der Tiefensuche erfolgten diese zwei Schritte jeweils unmittelbar hintereinander, also sobald wir einen Knoten entdeckt haben, haben wir auch gleich damit begonnen seine Nachbarn anzuschauen. Das hat uns erlaubt, die Tiefensuche mittels Rekursion zu implementieren. Nun wollen wir aber für die Breitensuche, dass wir zuerst alle Nachbarn ersten Grades anschauen, bevor wir den ersten Nachbarn zweiten Grades anschauen. Die Warteschlange simuliert nun dieses “Hinten-Anstellen-und-Warten” der neu entdeckten Knoten. In C++ kann das dann etwa so aussehen:

// Wir nehmen wieder an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void bfs(int start) {
        queue<int> Q; // Die Warteschlange für die neu entdeckten Knoten.
        Q.insert(start);
        while(!Q.empty()) {
                int v = Q.front();
                Q.pop();
                // Wir sind in Knoten v und erkunden die Nachbarschaft.
                for(int e = 0; e < E[v].size(); e++) {
                        int w = E[v][e];
                        // Nun prüfen wir, ob der Nachbar w noch unbesucht ist.
                        if(!visited[w]) {
                                visited[w] = true;
                                // Anstelle des rekursiven Aufruf der DFS,
                                // fügen wir w nun lediglich in die Schlange ein.
                                Q.insert(w);
                        }
                }
        }
}

int main() {
        // Graph einlesen, wie zuvor.
        ...
        // Nun können wir die Breitensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        bfs(start);
        // In visited[] können wir nun wiederum ablesen, ob
        // ein bestimmter Knoten erreicht werden kann.
}

Bild 1 zeigt dir an einem Beispiel wie sich die Besuchsreihenfolge der Knoten in einer Breitensuche und einer Tiefensuche unterscheiden können.

Bild 1: Die Breitensuche (links) und Tiefensuche (rechts) auf dem selben Graphen. Die Zahlen geben die Entdeckungsreihenfolge der Knoten an und die Pfeile bezeichnen die Kanten entlang welcher die Knoten entdeckt wurden.

Kürzeste Wege

Für ungerichtete, ungewichtete Graphen erlaubt uns die Breitensuche die Länge des kürzesten Weges zwischen dem Startpunkt und jedem beliebigen anderen Knoten zu bestimmen. Die Länge eines Pfades messen wir in der Anzahl Kanten, denen wir entlanggehen. Ungewichtet heisst hier also, dass jede Kante als gleich lang gezählt wird. Falls die Kanten unterschiedliche Länge haben, genügt die Breitensuche nicht mehr, um den kürzesten Weg zu berechnen. Der Algorithmus von Dijkstra, welcher dir in einer anderen Aufgabe erklärt wird, löst aber genau dieses Problem. Aber wie berechnen wir nun die ungewichtete Länge des kürzesten Weges von $a$ nach $b$ mit Hilfe der Breitensuche?

Die Erkundungsreihenfolge der BFS hat die schöne Eigenschaft, dass wir die Knoten in aufsteigender Distanz zum Startknoten besuchen. Das heisst, alle Knoten mit Distanz $5$ besuchen wir unmittelbar nach den Knoten mit Distanz $4$ und umittelbar vor den Knoten mit Distanz $6$. Wenn immer wir also einen neuen Knoten entdecken, können wir dessen Distanz zum Start direkt bestimmen, nämlich als die Distanz zum aktuellen Knoten plus $1$.

In der Implementierung von oben können wir dies einbauen, indem wir zum Beispiel einen Vektor dist hinzufügen, den wir für jeden Knoten mit unendlich initialisieren (oder einfach einer fixen, sehr grossen Zahl) und dann dist[start] auf Null setzen. Die Distanz der neu entdeckten Knoten setzen wir dann hier mit einer einzigen neuen Zeile:

...
if(!visited[w]) {
        visited[w] = true;
        // Anstelle des rekursiven Aufruf der DFS,
        // fügen wir w nun lediglich in die Schlange ein.
        Q.insert(w);
        dist[w] = dist[v] + 1; // Neue Zeile!
}
...

Bild 2 zeigt nochmals denselben Graphen aber jetzt mit den Distanzangaben zwischen den Knoten und dem Start.

Bild 2: Die Distanzen nach einer Breitensuche, die beim obersten Knoten begonnen hat.

Eingabe

Auf der ersten Zeile steht die Zahl $T$, die Anzahl Testfälle. Es folgen $T$ Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht $n$ und $m$, die Anzahl Knoten und Kanten. Anschliessend folgen $m$ Zeilen, welche die $m$ Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit $a$ und $b$ bedeutet, dass der Knoten $a$ mit Knoten $b$ verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von $0$ bis $n-1$ nummeriert.

Ausgabe

Gib für den $t$-ten Testfall “Case #t:” aus, gefolgt von einer Zahl, die Länge des kürzesten Weges von Knoten $0$ zu Knoten $n-1$ im $t$-ten Graphen. Die Eingaben sind so gewählt, dass es immer ein Weg zwischen diesen beiden Knoten gibt.

Limits

• $T=100$
• $N \le 1\,000$
• $M \le 10\,000$

Beispiel

2
7 8
0 1
2 0
0 3
1 4
2 4
5 3
4 6
6 5
7 7
0 1
2 1
2 0
4 0
4 3
5 3
5 6

Case #1: 3
Case #2: 4

Bild 3: Illustration des ersten Beispiels.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Zusatzaufgabe: Überlege dir, wie du nicht nur die Länge des Weges sondern auch einen kürzesten Weg (als Abfolge von Knoten) ausgeben kannst.

Eingabe

Auf der ersten Zeile steht die Zahl $T$, die Anzahl Testfälle. Es folgen $T$ Zeilen mit jeweils den ganzen Zahlen $N$, $M$, sowie $M$ Trippeln von ganzen Zahlen $u$ $v$ $w$ ($1\le u,v\le N,0\le w\le 1000$), welche Kanten von $u$ nach $v$ mit Gewicht $w$ beschreiben. Die Knoten sind von $1$ bis $N$ durchnummeriert.

Die Zahlen sind durch jeweils ein oder zwei Leerzeichen getrennt (siehe Beispiel).

Ausgabe

Gib für den $t$-ten Testfall “Case #t:” aus, gefolgt von der Länge des kürzesten Weges von Knoten $1$ zu Knoten $2$. Falls es von Knoten $1$ zu Knoten $2$ keinen Weg gibt, gib “Infinity” aus.

Limits

• $T=100$
• $2\le N\le 1\,000$
• $0\le M\le 10\,000$

Beispiel

3
3 2  1 3 5  3 2 7
3 3  1 2 7  1 3 4  3 2 1
3 1  1 3 4

Case #1: 12
Case #2: 5
Case #3: Infinity

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Werte von Funktionen berechnen

Wollen wir den Wert einer Funktion $P(x) = 2*x^{1/2} + 3*x + 2*x^{2}$ an einer bestimmten Stelle, z.B. $x = 4$ berechnen, so setzen wir einfach den Wert ($4$) für $x$ ein und rechnen aus:

$P(4) = 2*4^{1/2} + 3*4 + 2*4^{2}= 2*2 + 3*4 + 2*16 = 4 + 12 + 32 = 48$

Beachte dass $x^{1/n}$ die $n$-te Wurzel von $x$ ist: $x^{1/n} = \sqrt[n]{x}$.

In Computerprogrammen geht das ausrechnen sehr einfach. Wir schreiben einfach eine Funktion, die den Wert ausrechnet, in C++ z.B. so:

double P(double x) {
    return 2*pow(x, 1.0/2) + 3*x + 2*pow(x, 2);
}

Hinweis: die Funktion pow befindet sich in math.h. Beachte auch, dass du $1.0/2$ schreiben solltest und nicht $1/2$. $1/2$ ist $0$, denn die Division rundet bei Integern ab. Da $1.0$ ein Double ist, wird die Division mit Nachkommastellen durchgeführt.

Hinweis: die Funktion pow befindet sich in math.h.

Eingabe

Auf der ersten Zeile steht eine ganze Zahl $T$, die Anzahl Testfälle. Für jeden Testfall folgt eine Zeile mit jeweils den Zahlen $N$, $A$, $B$, $C$, $D$, $E$, $F$, $G$, $Y$. Hierbei stehen:

• $N$ (Ganzzahl) für die obere Schranke des zu betrachtenden Definitionsbereichs von $P$, die untere Schranke ist immer $1$,
• $A$, $B$, $C$, $D$, $E$, $F$, $G$ (Fliesskommazahlen) für die Koeffizienten der monotonen diskreten Funktion $P$,
• $Y$ (Ganzzahl) für den gesuchten Funktionswert.

Ausgabe

Für den $t$-ten Testfall gib eine Zeile “Case #t: X”, wobei $X$ ein zu $Y$ gehöriger x-Wert, oder $0$, falls die Funktion $P$ den Wert $Y$ im vorgegebenen Bereich nicht annimmt.

Limits

• $T = 100$
• $N \le 10000000$
• $0 \le A, B, C, D, E, F, G \le 1000$
• $Y \le P(N)$

Beispiel

2
10 0 0 0 0 1 0 0 4
10 0 0 0 0 1 0 0 6

Case #1: 2
Case #2: 0

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.