Die als Alex A bekannten Gänse sind dafür bekannt, dass sie in dreieckigen Gittern mit 64 Zellen leben:
(Bild aus diesem nicht verwandten Project Euler-Problem .)
Wir beschriften jede Zelle mit den Nummern 0
, 63
die in der obersten Zeile beginnen und dann in jeder Zeile darunter von links nach rechts gehen. So ist die obere Zelle 0
und die untere rechte Zelle 63
.
Jede Zelle hat drei Ränder. Wir können jede Grenze in der Form etikettieren , a,b
wo a
und b
sind die Zahlen der Zellen dieser Anteil die Grenze. Zum Beispiel die Grenze zwischen Zelle 0
und 2
würde 0,2
oder heißen 2,0
(es ist egal, in welcher Reihenfolge Sie sie eingeben).
Das Beschriftungssystem für Ränder am Rand des Rasters unterscheidet sich, da die Zellen am Rand des Rasters einen Rand haben, den sie nicht mit anderen Zellen gemeinsam haben. Wenn ein Rand nur ein Teil einer Zelle ist, verwenden wir den Buchstaben X
. Zum Beispiel können die drei Ränder der Zelle 0
sind 0,2
, 0,X
und 0,X
.
Einige der Zellen enthalten Gänse . Diese Gänse werden jedoch von bösen Füchsen (die von außerhalb des Gitters kommen) getötet, wenn Sie sie nicht schützen. Und wenn alle Gänse sterben, wird BrainSteel traurig sein. Deshalb werden wir ein Programm schreiben, das die Gänse umzäunt, um sie vor den Füchsen zu schützen. Die Gänse sollten in einem einzigen vollständig umschlossenen Polygon von Zäunen existieren. Unser Zaunbudget ist ziemlich niedrig, verwenden Sie also die geringstmögliche Anzahl von Zäunen.
Eingabebeschreibung
Eine Liste von Zahlen, die durch Kommas von 0
bis getrennt sind 63
und die Zellen darstellen, die Gänse enthalten. Beispiel:
6,12
Ausgabebeschreibung
Eine Liste von Grenzen, auf denen Zäune gebaut werden müssen, um die Gänse erfolgreich zu schützen. Dies sollte die kleinstmögliche Anzahl von Zäunen sein. Beispiel:
5,6 6,7 11,12 12,13
quelle
Antworten:
C #, 530 Bytes
Vollständiges C # -Programm, Eingabe als einzelne Zeile von STDIN und Ausgabe einer einzelnen Zeile an STDOUT mit einem abschließenden "".
Das ist ziemlich lang ... und hat viel zu viele x / y / z-Wiederholungen, aber ich konnte es bisher nicht auf irgendetwas Sinnvolles reduzieren und habe eine Prüfung in 2 Stunden, könnte morgen darauf zurückkommen.
Dieses Diagramm erklärt die meisten Vorgänge.
Erkennen Sie, dass ein "Sechseck" immer die billigste Form ist, da wir keine 0-breiten Abschnitte haben können (und den Gänsen den größtmöglichen Bewegungsspielraum bieten kann).
Das Programm übersetzt zunächst alle eingegebenen Zellenindizes in x / y / z-Koordinaten und ermittelt die Min / Max-Werte für x / y / z.
Als nächstes durchläuft es jeden Zellenindex und prüft, ob er in die von uns beschriebene 'Sechseck'-Grenze passt. Wenn dies der Fall ist, prüft es, ob es sich an einer der äußersten Kanten der Grenzen befindet (dh x = xmin oder y = ymax) und fügt entsprechende Kanten hinzu, wenn dies der Fall ist. Es muss den Index der Kante ermitteln, an der es sich befindet. Für x und z erhöhen / verringern wir sie nur nach Belieben und verwenden dann die folgende Formel:
Beachten Sie, dass sich die "Parität" immer ändert und dass y nicht beteiligt ist. Für y müssen wir nichts ändern, aber der Code ist ein bisschen chaotisch, weil er "Dreieck" -Begrenzungen durchführen muss, um festzustellen, ob die Zelle nebenan ein "X" sein sollte oder nicht.
Beispiellösung (Zellen mit Gänsen aus den drei Ecken):
Ordentlicher Code mit Kommentaren:
quelle
using System;
.using Q=System.Console;Q.Write();Q.ReadLine()
(45 Bytes) im Vergleich zu Ihrem Vorschlagusing System;Console.Write();Console.ReadLine()
(47 Bytes).i
,x
,y
,z
, undp
auf 0