Mobile Track Gewinner
Im vergangenen Jahr veranstaltete Yandex zwei Online-Programmiermeisterschaften. Wir veröffentlichen weiterhin Analysen der Aufgaben der zweiten Meisterschaft. Wir erinnern Sie daran, dass den Teilnehmern vier Tracks angeboten wurden: Maschinelles Lernen, Frontend, Mobile Development und Backend. Hier ist eine Diskussion ĂŒber die Qualifikationsrunde fĂŒr mobile Entwickler - 121 derjenigen, die die Qualifikation bestanden haben, nahmen dann am Finale teil. Aufgaben wurden von Spezialisten von Yandex.Browser und anderen Teams des Suchportals erfunden. In diesem Hub werden wir das Thema genetische Algorithmen ansprechen, einen Bot fĂŒr Tetris schreiben und die Suche mit verschiedenen Methoden fĂŒr Android und iOS durchfĂŒhren.
A. Kabel
Gepostet von: Sergey MyasnikovN Computer wurden in das neue BĂŒro gebracht. Das nahe gelegene Radioteleskop ermöglicht keine Wi-Fi-Kommunikation, und der Helpdesk muss ein Netzwerk mithilfe von LAN-Kabeln organisieren. Nachdem die Administratoren alle in den Ecken herumliegenden Kabel gesammelt hatten, gelang es ihnen, K Computerpaare miteinander zu verbinden. Nach einem langen Arbeitstag mĂŒde, wandten sich die Helpdesk-Mitarbeiter an Sie, um Hilfe zu erhalten - um das Budget zu berechnen, das zur Erledigung der Aufgabe erforderlich ist. Sie haben also eine Liste von M Computerpaaren, die Administratoren verbinden können, und die Kosten fĂŒr jedes Kabel. Als Sie mit der Arbeit begannen, fanden Sie einen Fehler im Kostenberechnungssystem - anstatt die Kosten zu addieren, multiplizieren sie sich -, sodass ein Kabel mit einem Wert von 4 und ein Kabel mit einem Wert von 3 zusammen nicht 7 sind, wie die Logik vorschlĂ€gt, sondern 12.
Um die Aufgabe abzuschlieĂen, mĂŒssen Sie die Kosten fĂŒr Kabel berechnen, die fĂŒr die Organisation eines verbundenen Netzwerks ausreichen, sodass jeder Computer direkt oder indirekt mit jedem verbunden ist.
E / A-Formate, Beispiele und HinweiseEingabeformat
Die erste Zeile enthÀlt die Zahlen 0 <N <10
6 , 0 †K <10
6 , 0 †M <10
6 .
Die nÀchsten K Zeilen enthalten Zahlenpaare 0 <u, v †N - die Anzahl der Computer, die bereits vom Helpdesk verbunden wurden.
Die nÀchsten M Zeilen enthalten Dreifache der Zahlen 0 <u, v †N und 0 <p †10
9 - die Anzahl der Computer, die Administratoren mit einem Kabel verbinden können, kosten p.
Ausgabeformat
Drucken Sie die Mindestkosten fĂŒr Kabel aus, die zum Aufbau eines verbundenen Netzwerks ausreichen, oder â1, wenn kein vollstĂ€ndiges Netzwerk aufgebaut werden kann.
Die Antwort kann sehr groĂ sein, Sie mĂŒssen sie also modulo 2
31 - 1 ausgeben.
Beispiel 1
Beispiel 2
Beispiel 3
Hinweise
Die Menge der Eingabedaten kann 30 MB erreichen - achten Sie auf die Lesegeschwindigkeit.
Lösung
Das gesamte Netzwerk, das aufgebaut werden muss, um das Problem zu lösen, ist nichts anderes als ein minimaler Spanning Tree. (Da zu Beginn der Konstruktion bereits K Kanten hinzugefĂŒgt wurden, ist das resultierende Diagramm nicht unbedingt ein Baum, aber es wird garantiert, dass es ihn enthĂ€lt.)
In der klassischen Umgebung besteht das Problem des Findens des minimalen Spannbaums darin, die Summe der Kanten zu minimieren, aber hier ist es notwendig, das Produkt zu minimieren. Zum GlĂŒck fallen diese beiden BĂ€ume zusammen. Dies lĂ€sst sich leicht beweisen, indem die Gewichte der Kanten durch ihre Logarithmen ersetzt werden.
Die bekanntesten Algorithmen zur Erstellung eines Minimum Spanning Tree sind die Prima- und Kraskal-Algorithmen.
Bei dichten Graphen hat der Prym-Algorithmus die Asymptotik O (N
2 ), die es angesichts der Bedingung N <10
6 nicht erlaubt, das Problem vollstÀndig zu lösen. (Beachten Sie jedoch, dass die Testdaten so zusammengestellt wurden, dass die Lösung mit den angegebenen Asymptoten genau die HÀlfte des Punktes erzielte.)
Eine naive Implementierung des Kruskal-Algorithmus, die ein Array verwendet, um Informationen ĂŒber die aktuelle Zusammensetzung von graphisch verbundenen Komponenten zu erhalten, weist die Asymptotik O (M log M + N
2 ) auf. Hier ist es Àquivalent zu O (N
2 ). FĂŒr eine vollstĂ€ndige Lösung mĂŒssen Sie eine Datenstruktur verwenden, die als Disjoint-Set-Union-System (DSU) bezeichnet wird.
Mit DSU können Sie zwei Operationen ausfĂŒhren: find (x) findet den "AnfĂŒhrer" der Menge, zu der x gehört (wir ĂŒbersetzen den AnfĂŒhrer in die Nummer der Menge); union (x, y) kombiniert die Mengen, zu denen x und y gehören.
Die bei der Implementierung der Struktur ĂŒblicherweise verwendete heuristische Pfadkomprimierungs- und Rangkombinations-Heuristik ermöglicht es uns, in praktischen FĂ€llen, die O (1) entsprechen, ein asymptotisches Verhalten zu erzielen.
Angenommen, wir haben DSU verwendet, um Informationen zu Graph-KonnektivitĂ€tskomponenten wĂ€hrend der AusfĂŒhrung des Kraskal-Algorithmus zu verwalten. Dann ist das asymptotische Verhalten des Algorithmus O (M log M + N) = O (M log M).
Entscheidungscode public class CablesSolution { private static final long MODULLO = 2147483647L; public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter pw = new PrintWriter(System.out); int n = in.readInt(); int k = in.readInt(); int m = in.readInt(); DisjointUnionSets dsu = new DisjointUnionSets(n + 1); for (int i = 0; i < k; i++) { int u = in.readInt(); int v = in.readInt(); dsu.union(u, v); } Edge[] edges = new Edge[m];
B. Verlorene SĂ€tze
Gepostet von: Dmitry FiskoBei der Betrachtung der Messdaten der Anwendung stellte der Manager Vasily die Hypothese auf, dass der BenutzeroberflĂ€che ein gewisser Schwung fehlt, der die Benutzer zurĂŒckhalten wĂŒrde. Deshalb forderte Vasily, die Anwendungsschnittstelle an die Designerin Maria zu diversifizieren. Nach ein paar Skizzen dĂ€mmerte Maria! Die Idee lag von Anfang an auf der OberflĂ€che - es stellte sich heraus, dass Sie Animationen fĂŒr den Text hinzufĂŒgen mĂŒssen. Wir haben verschiedene Texte ausgewĂ€hlt und Animationen gemacht. Leider wurden die Animationen nach Abschluss der Arbeiten vertauscht, und der Ausgangstext fĂŒr jeden von ihnen ging verloren. Helfen Sie dem Team zu verstehen, welcher Text jeweils animiert ist.
E / A-Formate, Beispiele und HinweiseEingabeformat
Sie haben mehrere Textdateien mit den angegebenen Animationen, fĂŒr die Sie jeweils den entsprechenden Text auswĂ€hlen mĂŒssen.
Link zum Archiv mit Animationsdateien .
Jede Animation wird durch Parameter definiert:
-
canvasWidth canvasHeight - Die Breite und Höhe des Containers fĂŒr die Animation werden in der ersten Eingabezeile angegeben.
-
figuresCount - Die Anzahl der zu animierenden Figuren wird in der zweiten Eingabezeile eingestellt.
-
Rechteck centerX centerY Breite Höhe Winkel Farbe - Angabe eines Rechtecks ââzentriert an einem Punkt (centerX, centerY), Breite Ă Höhe, Drehwinkelwinkel und festgelegte Farbe,
-
Kreismittelpunkt X Mittelpunkt Y Radiusfarbe - Deklaration eines Kreises mit Mittelpunkt am Punkt (Mittelpunkt X, Mittelpunkt Y), Radiusradius und festgelegter Farbe.
Der Farbparameter kann die Werte {schwarz, rot, weiĂ, gelb} annehmen. Der Winkelparameter nimmt Werte im Bereich (-359 °, 359 °) an.
FĂŒr jede Figur können mehrere Arten von Animationen gleichzeitig angegeben werden, die parallel angewendet werden. DarĂŒber hinaus kann jede Art von Animation nur einmal auf eine Figur angewendet werden. Die Anzahl der auf die Figur angewendeten Animationen wird durch die Zahl 0 (figureAnimationsCount) 3 unmittelbar nach der Deklaration der Figur festgelegt.
Arten von Animationen:
-
move destX destY time [cycle] - verschiebe eine Zahl in Millisekunden an einen Punkt (destX, destY).
-
Winkelzeit drehen [Zyklus] - Drehung der Figur um Winkelgrad in Zeitmillisekunden.
-
destScale time [cycle] skalieren -
Erhöht die Zahl in Millisekunden um destScale.
Wenn der Zyklusparameter angegeben ist, wird seine Bewegung am Ende der Animation in die entgegengesetzte Richtung fortgesetzt.
Ausgabeformat
Der angezeigte Text beim Abspielen der Animation. FĂŒr jede Animationsdatei muss die Antwort in einer neuen Zeile angegeben werden. Der Fall von Zeichen in der Antwort kann beliebig sein. Jeder in der Animation gefundene Text wird mit 10 Punkten bewertet.
Beispiel
Hinweise
Visualisierung der Animation aus dem Beispiel:
Lösung
Die Aufgabe bestand darin, die Animation umzusetzen. Wenn die Animation korrekt implementiert ist, werden beim Abspielen viele Grundelemente in lesbaren Text eingefĂŒgt. Die Animation kann mit allen Mitteln erfolgen - integriert in mobile Plattformen oder Lösungen auf niedrigerer Ebene.
Animationsbeispiel (
Link zur .mov-Datei ):
Eine Beispielimplementierung mit der Tkinter-Bibliothek von Python import copy import math import time import tkinter from enum import Enum FRAMES_PER_SECOND = 60 TIME_BETWEEN_FRAMES = int(1000 / FRAMES_PER_SECOND) class Rectangle(object): def __init__(self, left_x, left_y, width, height, color, angle=0.0): self.center_x = left_x + width / 2 self.center_y = left_y + height / 2 self.width = width self.height = height self.color = color self.angle = angle def get_left_x(self): return self.center_x - self.width / 2 def set_left_x(self, left_x): self.center_x = left_x + self.width / 2 def get_left_y(self): return self.center_y - self.height / 2 def set_left_y(self, left_y): self.center_y = left_y + self.height / 2 left_x = property(get_left_x, set_left_x) left_y = property(get_left_y, set_left_y) class Circle(object): def __init__(self, left_x, left_y, radius, color): self.center_x = left_x + radius self.center_y = left_y + radius self.radius = radius self.color = color self.angle = 0 def get_left_x(self): return self.center_x - self.radius def set_left_x(self, left_x): self.center_x = left_x + self.radius def get_left_y(self): return self.center_y - self.radius def set_left_y(self, left_y): self.center_y = left_y + self.radius left_x = property(get_left_x, set_left_x) left_y = property(get_left_y, set_left_y) class AnimationType(Enum): MOVE = 1 ROTATE = 2 SCALE = 3 class Animation(object): def __init__(self, time, cycle): self.time = time self.cycle = cycle def scale(self, time_spent): return 1 def move(self, time_spent): return 0, 0 def angle(self, time_spent): return 0 def _cycle_progress(self, time_spent): if self.cycle: cycle_time = time_spent % (self.time * 2) if cycle_time > self.time: return 1 - (cycle_time - self.time) / self.time else: return cycle_time / self.time else: if time_spent < self.time: cycle_time = time_spent % self.time return cycle_time / self.time else: return 1 class MoveAnimation(Animation): def __init__(self, figure, to_x, to_y, time, cycle): super().__init__(time, cycle) self.from_x = figure.center_x self.from_y = figure.center_y self.to_x = to_x self.to_y = to_y def move(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) diff_x = self.to_x - self.from_x diff_y = self.to_y - self.from_y return diff_x * cycle_progress, diff_y * cycle_progress class ScaleAnimation(Animation): def __init__(self, destination_scale, time, cycle): super().__init__(time, cycle) self.destination_scale = destination_scale def scale(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) return 1 + (self.destination_scale - 1) * cycle_progress class RotateAnimation(Animation): def __init__(self, rotate_angle, time, cycle): super().__init__(time, cycle) self.rotate_angle = rotate_angle def angle(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) return self.rotate_angle * cycle_progress class Transformer(object): def scale(self, scale): pass def move(self, diff_x, diff_y): pass def rotate(self, angle): pass class RectangleTransformer(Transformer): def __init__(self, rectangle): self.rectangle = rectangle def scale(self, scale): self.rectangle.width = self.rectangle.width * scale self.rectangle.height = self.rectangle.height * scale def move(self, diff_x, diff_y): self.rectangle.center_x = self.rectangle.center_x + diff_x self.rectangle.center_y = self.rectangle.center_y + diff_y def rotate(self, angle): self.rectangle.angle = (self.rectangle.angle + angle) % 360 class CircleTransformer(Transformer): def __init__(self, circle): self.circle = circle def scale(self, scale): self.circle.radius = self.circle.radius * scale def move(self, diff_x, diff_y): self.circle.center_x = self.circle.center_x + diff_x self.circle.center_y = self.circle.center_y + diff_y def rotate(self, angle): pass class Drawer(object): def draw(self, canvas, spent_time): pass class AnimationApplier(object): @staticmethod def apply_animations(spent_time, transformer, animations): for animation in animations: transformer.scale(animation.scale(spent_time)) diff_x, diff_y = animation.move(spent_time) transformer.move(diff_x, diff_y) transformer.rotate(animation.angle(spent_time)) class RectangleDrawer(Drawer): def __init__(self, rectangle, animations): self.rectangle = rectangle self.animations = animations def draw(self, canvas, spent_time): rect = self._transform_rect_with_animations(spent_time) rect_points = self._get_rectangle_points(rect) rotated_points = self._rotate(rect_points, rect.angle, [rect.center_x, rect.center_y]) canvas.create_polygon(rotated_points, fill=rect.color) def _transform_rect_with_animations(self, spent_time): rect = copy.copy(self.rectangle) transformer = RectangleTransformer(rect) AnimationApplier.apply_animations(spent_time, transformer, self.animations) return transformer.rectangle @staticmethod def _get_rectangle_points(rect): half_width = rect.width / 2 half_height = rect.height / 2 return [ [rect.center_x - half_width, rect.center_y - half_height], [rect.center_x - half_width, rect.center_y + half_height], [rect.center_x + half_width, rect.center_y + half_height], [rect.center_x + half_width, rect.center_y - half_height] ] @staticmethod def _rotate(points, angle, center): angle = math.radians(angle) cos_val = math.cos(angle) sin_val = math.sin(angle) cx, cy = center new_points = [] for x_old, y_old in points: x_old -= cx y_old -= cy x_new = x_old * cos_val - y_old * sin_val y_new = x_old * sin_val + y_old * cos_val new_points.append([x_new + cx, y_new + cy]) return new_points class CircleDrawer(Drawer): def __init__(self, circle, animations): self.circle = circle self.animations = animations def draw(self, canvas, spent_time): circle = self._transform_rect_with_animations(spent_time) size = circle.radius * 2 canvas.create_oval(circle.left_x, circle.left_y, circle.left_x + size, circle.left_y + size, fill=circle.color) def _transform_rect_with_animations(self, spent_time): circle = copy.copy(self.circle) transformer = CircleTransformer(circle) AnimationApplier.apply_animations(spent_time, transformer, self.animations) return transformer.circle class Scene(object): def __init__(self, canvas, animated_symbols): self.canvas = canvas self.drawers = self._get_generated_drawers(animated_symbols) @staticmethod def _get_generated_drawers(animated_symbols): drawers = [] for animated_symbol in animated_symbols: figure = animated_symbol.figure animations = animated_symbol.animations if isinstance(figure, Rectangle): drawer = RectangleDrawer(figure, animations) elif isinstance(figure, Circle): drawer = CircleDrawer(figure, animations) else: raise Exception() drawers.append(drawer) return drawers def draw(self, time_spent): self.canvas.delete("all") for drawer in self.drawers: drawer.draw(self.canvas, time_spent) self.canvas.pack() class Timer(object): def __init__(self): self.started_time = None def start(self): self.started_time = self._current_time() def time_spent(self): current_time = self._current_time() return current_time - self.started_time @staticmethod def _current_time(): return int(round(time.time() * 1000)) def scene_loop(window, scene, timer): time_spent = timer.time_spent() scene.draw(time_spent) window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer) def configure_window_location(window, canvas_width, canvas_height): screen_width = window.winfo_screenwidth() screen_height = window.winfo_screenheight() x = (screen_width / 2) - (canvas_width / 2) y = (screen_height / 2) - (canvas_height / 2) window.geometry('%dx%d+%d+%d' % (canvas_width, canvas_height, x, y)) class AnimatedSymbol(object): def __init__(self, figure, animations): self.figure = figure self.animations = animations class AnimationsParser(object): def parse_animated_symbols(self, file_path): with open(file_path) as f: lines = f.readlines() canvas_width, canvas_height = self._parse_size(lines[0]) symbols_count = int(lines[1]) animated_symbols = [] current = 2 for i in range(symbols_count): figure = self._parse_figure(lines[current]) current += 1 symbol_animations = self._parse_animations(figure, current, lines) current += 1 + len(symbol_animations) animated_symbol = AnimatedSymbol(figure, symbol_animations) animated_symbols.append(animated_symbol) return canvas_width, canvas_height, animated_symbols def _parse_size(self, line): parts = line.split(" ") return int(parts[0]), int(parts[1]) def _parse_animations(self, figure, current, lines): animations = [] animations_count = int(lines[current]) for i in range(animations_count): parts = lines[current + i + 1].split(" ") animation = self._parse_animation(figure, parts) animations.append(animation) return animations def _parse_figure(self, line): parts = line.split(" ") if parts[0] == 'rectangle': center_x = float(parts[1]) center_y = float(parts[2]) width = float(parts[3]) height = float(parts[4]) angle = float(parts[5]) color = parts[6].replace('\n', '') figure = Rectangle(center_x - width / 2, center_y - height / 2, width, height, color, angle) elif parts[0] == 'circle': center_x = float(parts[1]) center_y = float(parts[2]) radius = float(parts[3]) color = parts[4].replace('\n', '') figure = Circle(center_x - radius, center_y - radius, radius, color) else: raise Exception() return figure def _parse_animation(self, figure, parts): if parts[0] == "move": animation = self._parse_move_animation(figure, parts) elif parts[0] == "scale": animation = self._parse_scale_animation(parts) elif parts[0] == "rotate": animation = self._parse_rotate_animation(parts) else: raise Exception() return animation @staticmethod def _parse_move_animation(figure, parts): to_x = float(parts[1]) to_y = float(parts[2]) time = float(parts[3]) cycle = len(parts) >= 5 return MoveAnimation(figure, to_x, to_y, time, cycle) @staticmethod def _parse_scale_animation(parts): destination_scale = float(parts[1]) time = float(parts[2]) cycle = len(parts) >= 4 return ScaleAnimation(destination_scale, time, cycle) @staticmethod def _parse_rotate_animation(parts): rotate_angle = float(parts[1]) time = float(parts[2]) cycle = len(parts) >= 4 return RotateAnimation(rotate_angle, time, cycle) def main(): canvas_width, canvas_height, animated_symbols = \ AnimationsParser().parse_animated_symbols('animation_path.txt') window = tkinter.Tk() configure_window_location(window, canvas_width, canvas_height) canvas = tkinter.Canvas(window, width=canvas_width, height=canvas_height) scene = Scene(canvas, animated_symbols) timer = Timer() timer.start() window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer) window.mainloop() if __name__ == "__main__": main()
C. Tetris-Bot
Urheber: Dmitry NevedomskyDas geschĂ€ftige Arkady verbringt seine Freizeit gerne mit der Teilnahme an verschiedenen Auktionen von Retrocomputern. Auf einem von ihnen sah er den Commodoro, der das Leben gesehen hatte, und Arkady beeilte sich, es zu kaufen. Und diesmal kaufte er nicht nur Hardware, sondern auch Software, eine Ăberraschung wartete auf ihn am Computer - da war Tetris vom Vorbesitzer unvollendet. Empirisch entrĂ€tselte Arkady seine Regeln.
Dem Spieler wird ein Tetris-Feld mit 10 Zellen Breite und unbegrenzter Höhe angeboten. Eine Liste aller Tetramino, die auf dem Feld platziert werden mĂŒssen. Tetramino "fallen" sofort, dh ihre Position wird einmal fĂŒr die entsprechende Bewegung festgelegt, und wĂ€hrend des Fallens können die Position und die Drehung nicht geĂ€ndert werden.
Tetramino fĂ€llt, bis er auf den Boden oder auf eine andere Figur stöĂt. Wird gleichzeitig eine ganze Zeile des Feldes gefĂŒllt, verschwindet diese Zeile und alles, was darĂŒber liegt, fĂ€llt eine Zelle darunter.
Die Anzahl der erhaltenen Punkte wird durch die Anzahl der zerstörten Reihen bestimmt. Das Spiel endet, wenn alle vorgeschlagenen Teile platziert wurden. Der Autor des Spiels hinterlieà eine Tabelle mit Aufzeichnungen, in der er selbst alle PlÀtze einnahm.
Wie bereits erwÀhnt, ist Arkady sehr beschÀftigt. Aber er spielt auch sehr viel. Hilf ihm, der Beste in diesem Spiel zu werden.
Figurentabelle und ihre möglichen Wendungen
E / A-Formate, Beispiele und HinweiseEingabeformat
Die Eingabedaten befinden sich in den Dateien input1.txt, input2.txt, ..., input10.txt.
Mit Dateien archivieren .
Die erste Zeile enthÀlt eine positive Anzahl von Ziffern N (N †100).
In jeder folgenden Zeile wird ein einzelnes lateinisches Zeichen aus der Menge
{'O', 'S', 'Z', 'L', 'J', 'T', 'I'} ĂŒbertragen.
Jedes Symbol steht fĂŒr eine Tetramino-Figur.
Ausgabeformat
Zur ĂberprĂŒfung mĂŒssen Sie ein ZIP-Archiv mit den Ausgabedateien im Stammverzeichnis mit den Namen output1.txt, output2.txt, ..., output10.txt einreichen, wobei die Ausgabedatei outputX.txt der Eingabedatei inputX.txt entsprechen sollte.
Die Antwortdatei besteht aus N Zeilen, von denen jede einem Tetramino aus den Eingabedaten entspricht und aus zwei Zahlen A
i und B
i besteht , die den Zug des Spielers mit der vorgeschlagenen Figur angeben:
1. A
i gibt die Spalte des Tetramino-Elements ganz links an (1 †A
i †10).
2. B
i gibt die Drehrichtung des Tetraminos an (1 †B
i †4).
Befindet sich die gewĂŒnschte Datei nicht im Archiv oder wurde sie falsch zusammengestellt, werden fĂŒr den entsprechenden Test 0 Punkte vergeben.
Beispiel
Hinweise
In diesem Beispiel werden 4 Zeilen zerstört.
Der Endzustand des Feldes:
Informationen zu Fehlercodes:
1. PE - ein Ausgabefehler wurde gemacht (zum Beispiel gibt es keine solche Drehung der Figur)
2. WA - Informationen ĂŒber die Drehung und Position der Figur wurden korrekt angegeben, diese Anordnung liegt jedoch auĂerhalb der Feldgrenzen.
3. TL, ML, OK, RE - diese Codes haben die gleiche Bedeutung wie in den Regeln des Yandex.Contest-Systems.
Da das Problem NP-vollstÀndig ist, sollte die Lösung aus mathematischer Sicht nicht optimal sein. Die Wirksamkeit der Entscheidung wird durch die Anzahl der erzielten Punkte bestimmt.
Lösung
Dies ist eine offene Testaufgabe. Lassen Sie uns herausfinden, was dies bedeutet.
Der Teilnehmer erhĂ€lt ein Zip-Archiv, in dessen Stammverzeichnis sich die Textdateien input1.txt, input2.txt, ..., input10.txt befinden. Eine Datei besteht aus einer Reihe von Tetramino-Figuren, die angeordnet werden mĂŒssen. Als Antwort des Teilnehmers wird ein generiertes Zip-Archiv erwartet, in dessen Stammverzeichnis sich die Dateien output1.txt, output2.txt, ..., output10.txt befinden. Jede Datei muss ZĂŒge von Teilen in derselben Reihenfolge enthalten, in der sie in der Datei des entsprechenden Satzes angegeben sind.
Die Aufgabe ist NP-vollstĂ€ndig und eine hundertprozentige Lösung ist nur eine erschöpfende Suche. Daher wĂ€chst die KomplexitĂ€t exponentiell mit der Zunahme der Anzahl von Figuren. Da es nicht erforderlich ist, den Lösungscode zu ĂŒbergeben, gibt es keine EinschrĂ€nkungen in Bezug auf Speicher und AusfĂŒhrungszeit.
Ein voller Punkt fĂŒr die Aufgabe wurde vergeben, wenn eine âzufriedenstellendeâ QualitĂ€t erreicht wurde - die Lösung sollte 60% der Punkte erreicht haben. Die Lösung des Autors fĂŒr das Problem, die auf einem genetischen Algorithmus basierte, der auf einem Standard-Tetris-Randomizer trainiert wurde, erzielte ebenso viele Punkte. Dieser Randomizer ist
im Artikel beschrieben .
Der Rest der Aufgabe unterscheidet sich nicht wesentlich vom Schreiben eines regulĂ€ren Bots fĂŒr Tetris, mit der Ausnahme, dass das "Glas" des Spielfelds eine unbegrenzte Höhe hat. Daher hĂ€ngt der Erfolg der Entscheidung nicht davon ab, wie lange der Bot spielen kann, ohne ĂŒber das âGlasâ hinauszugehen, sondern davon, wie erfolgreich er eine begrenzte Anzahl von Zahlen arrangiert.
Dem Teilnehmer stand es frei, eine Lösungsstrategie zu wÀhlen. Hier sind einige davon in der Reihenfolge zunehmender KomplexitÀt und zunehmender Anzahl erzielter Punkte:
1. Wir spielen âHĂ€ndeâ, ohne den Code zu verwenden, und schreiben ZĂŒge in die Lösung.
2. Wir schreiben einen Visualizer und spielen "HĂ€nde", wobei wir die ZĂŒge in der Lösung aufschreiben.
3. Der gierige Algorithmus. Bei jedem Spielzug versuchen wir, das Teil so zu platzieren, dass die Anzahl der zerstörten Reihen maximal ist. Wenn es mehrere solcher Optionen gibt, wÀhlen Sie sie nach dem Zufallsprinzip aus.
4. Derselbe Greedy-Algorithmus wie in Absatz 3, nur wird nicht der Erfolg der Einstellung einer Ziffer ĂŒberprĂŒft, sondern der Erfolg der erschöpfenden Suche in einer Gruppe von Ziffern (beispielsweise einer Gruppe von fĂŒnf Ziffern).
5. Der genetische Algorithmus. Wir berĂŒcksichtigen in der Fitnessfunktion nicht nur die Anzahl der gebrochenen Reihen, wie im Greedy-Algorithmus, sondern auch die GlĂ€tte des "Reliefs" des Feldes und beispielsweise die Anzahl der zwischen den Figuren gebildeten FreirĂ€ume.
D und E. Quest
Autoren: Ilimdar Ablyaev und Ilya KuteevMischa macht ein Handyspiel im Genre der Suche. Er fand im Internet eine fertige Bibliothek mit einer Engine fĂŒr das Spiel und erstellte eine darauf basierende BenutzeroberflĂ€che. Mischa hat es eilig, das Spiel zu veröffentlichen, und hat wĂ€hrend des Entwicklungsprozesses mehrere Fehler gemacht. Um das Projekt rechtzeitig abzuschlieĂen, bat Mischa Sie um Hilfe. Laden Sie das Projekt herunter, korrigieren Sie Ăbersetzungsfehler, AbstĂŒrze und logische Fehler. SchlieĂen Sie die Quest ab und gehen Sie zum Bingo-Bildschirm, auf dem die geheime Phrase erscheint. Sie wird die Antwort auf das Problem sein.
:
Android ,
iOS . â ( 255 ).
Android
1) .
2) , IDE.
- final mBackButton mTitleTextView, .
- mTitleTextView mBackButton , , .
- â Layout ViewGroup.
- okButton getTextTaskControlsLayout.
- IDE , «» «» .
3) . ds , «java.lang.IllegalStateException: You need to use a Theme.AppCompat theme (or descendant) with this activity». .
4) .
- â java.lang.IndexOutOfBoundsException.
- : Layout Layout. .
- 1.1 ( ).
5) .
- , .
- ( , , ).
- . :
â Layout.
â . - .
6) . â .
7) «».
- android.content.res.Resources$NotFoundException.
- . , ID .
- .
! .
iOS
. :
, Optional<Optional<Step>>. guard let Optional . Optional, flatMap({ $0 }), .
, .
, QuestCore . :
, â goLeft, goRight . , goRight .
, : TestView, firstResponder . , TestView firstResponder. , UIKit.
«». IBOutlet, , . .
, 2018 .