Bot para Tetris y animación de ingeniería inversa. Análisis de la pista móvil del segundo campeonato de programación.


Ganadores de la pista móvil

El año pasado, Yandex celebró dos campeonatos de programación en línea. Continuamos publicando análisis de las tareas del segundo campeonato. Le recordamos que a los participantes se les ofrecieron cuatro pistas: aprendizaje automático, frontend, desarrollo móvil y backend. Aquí hay una discusión sobre la ronda de calificación para desarrolladores móviles: 121 de los que aprobaron las calificaciones y luego participaron en la final. Las tareas fueron inventadas por especialistas de Yandex.Browser y otros equipos del portal de búsqueda. En este centro, tocaremos el tema de los algoritmos genéticos, escribiremos un bot para Tetris y realizaremos la búsqueda con diferentes métodos para Android e iOS.

A. cables

Publicado por: Sergey Myasnikov
Todos los idiomasPython 3.7.3 y Python 2.7
Límite de tiempo4 s20 s
Límite de memoria256 MB
Entrarentrada estándar o input.txt
Conclusiónsalida estándar o salida.txt
Se trajeron N computadoras a la nueva oficina. El radiotelescopio cercano no permite el uso de Wi-Fi para la comunicación, y el servicio de asistencia tendrá que organizar una red con cables LAN. Después de haber recogido todos los cables en las esquinas, los administradores lograron conectar K pares de computadoras. Cansado después de un largo día de trabajo, el personal del servicio de asistencia recurrió a usted para obtener ayuda, para calcular el presupuesto necesario para completar la tarea. Entonces tiene una lista de M pares de computadoras que pueden conectar administradores, y el costo de cada cable. Al comenzar a trabajar, encontró un error en el sistema de cálculo de costos, en lugar de sumar los costos, se multiplican, por lo que un cable con un valor de 4 y un cable con un valor de 3 juntos no son 7, como sugiere la lógica, sino 12.

Para completar la tarea, debe calcular el costo de los cables suficientes para la organización de una red conectada, de modo que cada computadora esté conectada a cada una directa o indirectamente.

Formatos de E / S, ejemplos y notas

Formato de entrada


La primera línea contiene los números 0 <N <10 6 , 0 ≤ K <10 6 , 0 ≤ M <10 6 .

Las siguientes líneas K contienen pares de números 0 <u, v ≤ N: los números de computadoras ya conectadas por el servicio de asistencia.

Las siguientes líneas M contienen triples de números 0 <u, v ≤ N y 0 <p ≤ 10 9 - el número de computadoras que los administradores pueden conectar usando un cable de costo p.

Formato de salida


Imprima el costo mínimo de cables suficiente para construir una red conectada, o –1 si es imposible construir una red completa.

La respuesta puede ser muy grande, por lo que debe generar el módulo 2 31-1.

Ejemplo 1

EntrarConclusión
2 0 1
2 1 9
9

Ejemplo 2

EntrarConclusión
5 0 6
1 3 1
2 4 8
1 4 1
1 2 10
4 1 10
5 3 4
32

Ejemplo 3

EntrarConclusión
6 0 3
4 3 2
2 6 9
1 4 8
–1

Notas


La cantidad de datos de entrada puede alcanzar los 30 MB; preste atención a la velocidad de lectura.

Solución


La red completa que debe construirse para resolver el problema no es más que un árbol de expansión mínimo. (Dado que los bordes K ya se han agregado al comienzo de la construcción, el gráfico resultante no es necesariamente un árbol, pero se garantiza que lo contendrá).

En el entorno clásico, el problema de encontrar el árbol de expansión mínimo implica minimizar la suma de los bordes, pero aquí es necesario minimizar el producto. Afortunadamente, estos dos árboles coinciden. Esto es fácil de probar al reemplazar los pesos de los bordes con sus logaritmos.

Los algoritmos más famosos para construir un árbol de expansión mínima son los algoritmos Prima y Kraskal.

En el caso de gráficos densos, el algoritmo Prym tiene los asintóticos O (N 2 ), que, dada la restricción N <10 6 , no permite usarlo para una solución completa del problema. (Pero tenga en cuenta que los datos de la prueba se compilaron para que la solución con los asintóticos indicados obtuviera exactamente la mitad del punto)

Una implementación ingenua del algoritmo de Kruskal que utiliza una matriz para mantener información sobre la composición actual de los componentes conectados a gráficos tiene los asintóticos O (M log M + N 2 ). Aquí es equivalente a O (N 2 ). Para obtener una solución completa, debe usar una estructura de datos conocida como sistema de unión de conjunto disjunto (DSU).

DSU le permite realizar dos operaciones: find (x) encuentra el "líder" del conjunto al que pertenece x (el líder se traduce inyectivamente al número del conjunto); union (x, y) combina los conjuntos a los que pertenecen x e y.

Las heurísticas de compresión de trayectoria y las heurísticas de combinación de rango, generalmente utilizadas en la implementación de una estructura, permiten lograr un comportamiento asintótico, en casos prácticos equivalentes a O (1).

Supongamos que usamos DSU para mantener información sobre los componentes de conectividad gráfica durante la ejecución del algoritmo de Kraskal. Entonces el comportamiento asintótico del algoritmo será O (M log M + N) = O (M log M).

Código de decisión
 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]; // (4 + 4 + 8) * 2M = 32M for (int i = 0; i < m; i++) { int u = in.readInt(); int v = in.readInt(); long p = in.readLong(); edges[i] = new Edge(u, v, p); } Arrays.sort(edges); long res = 1; boolean addedEdge = false; for (Edge edge : edges) { if (!dsu.check(edge.getU(), edge.getV())) { dsu.union(edge.getU(), edge.getV()); res = (res * edge.getP()) % MODULLO; addedEdge = true; } } if (!dsu.isJoint()) { res = -1; } else if (!addedEdge) { res = 0; } pw.println(res); pw.flush(); pw.close(); } public static class DisjointUnionSets { private int[] rank; // 4M private int[] parent; // 4M DisjointUnionSets(int size) { rank = new int[size]; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } int find(int target) { if (parent[target] != target) { parent[target] = find(parent[target]); } return parent[target]; } boolean check(int x, int y) { return find(x) == find(y); } void union(int x, int y) { int xRoot = find(x); int yRoot = find(y); if (xRoot == yRoot) { return; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = yRoot; } else if (rank[yRoot] < rank[xRoot]) { parent[yRoot] = xRoot; } else { parent[yRoot] = xRoot; rank[xRoot] = rank[xRoot] + 1; } } boolean isJoint() { int parent = -1; for (int i = 1; i < rank.length; i++) { if (parent == -1) { parent = find(i); } else { if (parent != find(i)) { return false; } } } return true; } } private static class Edge implements Comparable<Edge> { private int u; private int v; private long p; Edge(int u, int v, long p) { this.u = u; this.v = v; this.p = p; } int getU() { return u; } int getV() { return v; } long getP() { return p; } @Override public int compareTo(Edge edge) { return Long.compare(p, edge.p); } } } 

B. Frases perdidas

Publicado por: Dmitry Fisko

Al observar las métricas de la aplicación, el gerente Vasily planteó la hipótesis de que la interfaz carece de entusiasmo que frenaría a los usuarios. Por lo tanto, Vasily solicitó diversificar la interfaz de la aplicación a la diseñadora Maria. Después de varios bocetos, ¡se dio cuenta de Mary! La idea desde el principio estaba en la superficie: resultó que era necesario agregar animaciones para el texto. Seleccionamos varios textos e hicimos animaciones. Desafortunadamente, después de completar el trabajo, las animaciones se mezclaron y el texto fuente de cada una de ellas se perdió. Ayude al equipo a comprender qué texto está animado en cada caso.

Formatos de E / S, ejemplo y notas

Formato de entrada


Tiene varios archivos de texto con las animaciones dadas, para cada uno debe seleccionar el texto apropiado.

Enlace al archivo con archivos de animación .

Cada animación está definida por parámetros:
- canvasWidth canvasHeight : el ancho y la altura del contenedor para la animación se especifican en la primera línea de entrada,
- FiguresCount : el número de figuras a animar se establece en la segunda línea de entrada,
- rectángulo centerX centerY ancho altura ángulo color - declaración de un rectángulo centrado en un punto (centerX, centerY), ancho × altura, ángulo de ángulo de grado de rotación y color especificado,
- círculo centerX color del radio centerY - declaración de un círculo con el centro en el punto (centerX, centerY), radio del radio y color especificado.

El parámetro de color puede tener los valores {negro, rojo, blanco, amarillo}. El parámetro de ángulo toma valores en el rango (-359 °, 359 °).

Para cada figura, se pueden especificar varios tipos de animación a la vez, que se aplican en paralelo. Además, cada tipo de animación se puede aplicar no más de una vez a una figura. El número de animaciones aplicadas a la figura se establece mediante el número 0 ⩽ figureAnimationsCount ⩽ 3 inmediatamente después de la declaración de la figura.

Tipos de animaciones:
- mover destX destY time [ciclo] - mueve una figura a un punto (destX, destY) en milisegundos de tiempo.
- tiempo de rotación del ángulo [ciclo] - rotación de la figura por grados de ángulo en milisegundos de tiempo.
- scale destScale time [cycle] - aumenta la cifra por destScale en milisegundos de tiempo.

Si se especifica el parámetro del ciclo, al final de la animación, su movimiento continúa en la dirección opuesta.

Formato de salida


El texto que se muestra al reproducir la animación. Para cada archivo de animación, la respuesta debe indicarse en una nueva línea. El caso de los caracteres en la respuesta puede ser arbitrario. Cada texto encontrado en la animación tiene una calificación de 10 puntos.

Ejemplo

EntrarConclusión
400 400
10
rectangle 69.000 280.000 24.000 24.000 0.000 black
1
move 251.000 72.000 10000 cycle
rectangle 256.000 188.000 24.000 48.000 0.000 black
0
rectangle 232.000 152.000 72.000 24.000 0.000 black
0
rectangle 35.000 400.000 24.000 24.000 0.000 black
1
move 285.000 -96.000 10000 cycle
rectangle 244.000 248.000 48.000 24.000 0.000 black
0
rectangle 300.000 117.000 24.000 48.000 0.000 black
1
move 112.000 164.000 5000
rectangle 136.000 200.000 72.000 24.000 0.000 black
0
rectangle 160.000 236.000 24.000 48.000 0.000 black
0
rectangle 208.000 224.000 24.000 72.000 44.797 black
1
rotate -44.797 5000
rectangle 232.000 200.000 24.000 24.000 0.000 black
0
42

Notas


Visualización de la animación del ejemplo:


Solución


La tarea consistía en implementar la animación. Si la animación se implementa correctamente, cuando se reproduce, se agregan muchas primitivas al texto legible. La animación se puede hacer utilizando cualquier medio, integrado en plataformas móviles o soluciones de nivel inferior.

Ejemplo de animación ( enlace al archivo .mov ):



Una implementación de ejemplo usando la biblioteca Tkinter de 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

Autor: Dmitry Nevedomsky
Límite de tiempo1 s
Límite de memoria256 MB
Entrarentrada estándar o input.txt
Conclusiónsalida estándar o salida.txt
A Ocupado Arkady le gusta pasar su tiempo libre participando en varias subastas de retrocomputadoras. En uno de ellos, vio al Commodoro que había visto la vida, y Arkady se apresuró a comprar. Y esta vez adquirió no solo hardware, sino también software, una sorpresa lo estaba esperando en la computadora: Tetris estaba inacabado por el dueño anterior. Empíricamente, Arkady descifró sus reglas.

Al jugador se le ofrece un campo Tetris de 10 celdas de ancho y una altura ilimitada. Una lista de todos los tetramino que se deben colocar en el campo. Tetramino "cae" inmediatamente, es decir, su posición se establece una vez para el movimiento correspondiente, y durante la caída, la posición y la rotación no se pueden cambiar.

El tetramino cae hasta que tropieza en el fondo o en otra figura. Si al mismo tiempo se llena una fila completa del campo, esta fila desaparece y todo lo que está arriba cae una celda debajo.

El número de puntos obtenidos está determinado por el número de filas destruidas. El juego termina cuando se han colocado todas las piezas propuestas. El autor del juego dejó una tabla de registros en la que él mismo ocupó todos los lugares.

Como se mencionó anteriormente, Arkady es una persona muy ocupada. Pero también es muy apostador. Ayúdale a convertirse en el mejor en este juego.

Tabla de figuras y sus posibles giros.

Formatos de E / S, ejemplo y notas

Formato de entrada


Los datos de entrada están en los archivos input1.txt, input2.txt, ..., input10.txt. Archivo con archivos .

La primera línea contiene un número positivo de cifras N (N ≤ 100).

En cada línea subsiguiente, se transmite un único carácter latino del conjunto {'O', 'S', 'Z', 'L', 'J', 'T', 'I'} .

Cada símbolo representa una figura tetramino.

Formato de salida


Para la verificación, debe enviar un archivo zip con los archivos de salida ubicados en su raíz con los nombres output1.txt, output2.txt, ..., output10.txt, donde el archivo de salida outputX.txt debe corresponder con el archivo de entrada inputX.txt.
El archivo de respuesta consta de N líneas, cada una de las cuales corresponde a un tetramino de los datos de entrada y consta de dos números A i y B i , que indican el movimiento del jugador con la figura propuesta:

1. A i indica la columna del elemento tetramino más a la izquierda (1 ≤ A i ≤ 10).
2. B i indica la dirección de rotación del tetramino (1 ≤ B i ≤ 4).

Si el archivo requerido no está en el archivo o se formó incorrectamente, se otorgarán 0 puntos para la prueba correspondiente.

Ejemplo

EntrarConclusión
15
Z
O
L
O
J
S
T
J
Z
J
Z
S
Z
I
O
1 2
9 1
6 4
9 1
3 2
6 1
1 2
4 1
6 2
3 1
8 2
2 2
4 1
10 1
6 1

Notas


En este ejemplo, se destruirán 4 filas.

El estado final del campo:



Información sobre códigos de error:

1. PE: se cometió un error de salida (por ejemplo, no existe tal rotación de la figura)
2. WA: la información sobre la rotación y la posición de la figura se proporcionó correctamente, pero esta disposición está más allá de los límites del campo.
3. TL, ML, OK, RE: estos códigos tienen el mismo significado que en las reglas del sistema Yandex.Contest.

Dado que el problema es NP-completo, la solución no tiene que ser óptima desde un punto de vista matemático. La efectividad de la decisión está determinada por el número de puntos anotados.

Solución


Esta es una tarea de prueba abierta. Veamos qué significa esto.

El participante recibe a su disposición un archivo zip, en cuya raíz se encuentran los archivos de texto input1.txt, input2.txt, ..., input10.txt. Un archivo es un conjunto de figuras de tetramino que se organizarán. Como respuesta del participante, se espera un archivo zip generado, en cuya raíz se encuentran los archivos output1.txt, output2.txt, ..., output10.txt. Cada archivo debe contener movimientos por piezas en el mismo orden en que se especifican en el archivo del conjunto correspondiente.

La tarea es NP-complete y la solución al cien por cien es solo una búsqueda exhaustiva. Por lo tanto, la complejidad crece exponencialmente con el aumento en el número de figuras. Como no es necesario entregar el código de la solución, no hay restricciones en la memoria y el tiempo de ejecución.

Se obtuvo un punto completo para la tarea cuando se logró una calidad "satisfactoria": la solución debería haber obtenido el 60% de los puntos. La solución del autor al problema obtuvo la misma puntuación, que se basó en un algoritmo genético entrenado en un aleatorizador estándar de Tetris. Este aleatorizador se describe en el artículo .

El resto de la tarea no es muy diferente de escribir un bot regular para tetris, excepto que el "vaso" del campo de juego es ilimitado en altura. Por lo tanto, el éxito de la decisión está determinado no por cuánto tiempo puede jugar el bot sin ir más allá del "cristal", sino por qué tan exitosamente organizará un conjunto limitado de figuras.

El participante era libre de elegir una estrategia de solución. Estos son algunos de ellos en orden de complejidad creciente y aumento del número de puntos anotados:

1. Jugamos "manos" sin usar el código, escribiendo movimientos en la solución.
2. Escribimos un visualizador y jugamos "manos", escribiendo movimientos en la solución.
3. El algoritmo codicioso. En cada turno, tratamos de colocar la pieza para que el número de filas destruidas sea máximo. Si hay varias de estas opciones, seleccione cualquiera de ellas al azar.
4. El mismo algoritmo codicioso que en el párrafo 3, solo que se verifica no el éxito de establecer una figura, sino el éxito de la búsqueda exhaustiva de un grupo de figuras (por ejemplo, un grupo de cinco figuras).
5. El algoritmo genético. Tenemos en cuenta en la función de aptitud no solo el número de filas rotas, como en el algoritmo codicioso, sino también la suavidad del "relieve" del campo y, por ejemplo, el número de espacios libres formados entre las figuras.

D y E. Quest

Autores: Ilimdar Ablyaev e Ilya Kuteev

Misha hace un juego móvil en el género de búsqueda. Encontró en Internet una biblioteca preparada con un motor para el juego e hizo una interfaz basada en él. Misha tiene prisa por lanzar el juego y cometió varios errores durante el proceso de desarrollo. Para terminar el proyecto a tiempo, Misha te pidió ayuda. Descargue el proyecto, corrija errores de compilación, bloqueos y errores lógicos en el mismo. Completa la búsqueda y ve a la pantalla de Bingo, en la que aparecerá la frase secreta. Ella será la respuesta al problema.

Descargue el archivo con el proyecto: Android , iOS . El formato de salida es una frase secreta (cadena de hasta 255 caracteres).

Solución de Android


1) Elimine la línea con el tema o agregue cualquier tema.

2) Revisamos el texto de la tarea y corregimos todos los errores que resalta el IDE.

  1. Eliminamos modificadores finales de mBackButton y mTitleTextView, ya que su inicialización requiere recursos.
  2. Si transfiere la inicialización de mTitleTextView y mBackButton al lugar de la declaración, la aplicación se bloqueará al principio, ya que aún no tiene un contexto.
  3. Solucionamos el error con el valor de retorno de los métodos: reemplazamos Layout con ViewGroup.
  4. Inicializamos la variable okButton en el método getTextTaskControlsLayout.
  5. Además, el IDE puede resaltar un error lógico que los mismos oyentes están asignados a los botones izquierdo y derecho.

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 .

Source: https://habr.com/ru/post/482210/


All Articles