Bot para Tetris e animação de engenharia reversa. Análise da pista móvel do segundo campeonato de programação


Vencedores do Mobile Track

No ano passado, a Yandex realizou dois campeonatos de programação online. Continuamos a publicar análises das tarefas do segundo campeonato. Lembramos que os participantes receberam quatro faixas: aprendizado de máquina, front-end, desenvolvimento móvel e back-end. Aqui está uma discussão sobre a rodada de qualificação para desenvolvedores de dispositivos móveis - 121 dos que passaram nas qualificações participaram da final. As tarefas foram inventadas por especialistas da Yandex.Browser e outras equipes do portal de pesquisa. Neste hub, abordaremos o tópico de algoritmos genéticos, escreveremos um bot para o Tetris e faremos a busca com diferentes métodos para Android e iOS.

A. Cabos

Publicado por: Sergey Myasnikov
Todas as línguasPython 3.7.3 e Python 2.7
Prazo4 s20 s
Limite de memória256 MB
Entrarentrada padrão ou input.txt
Conclusãosaída padrão ou output.txt
N computadores foram trazidos para o novo escritório. O radiotelescópio nas proximidades não permite o uso de Wi-Fi para comunicação e o suporte técnico precisará organizar uma rede usando cabos LAN. Depois de coletar todos os cabos nos cantos, os administradores conseguiram conectar K pares de computadores. Cansados ​​após um longo dia de trabalho, a equipe de assistência técnica procurou por você para obter ajuda - para calcular o orçamento necessário para concluir a tarefa. Portanto, você tem uma lista de M pares de computadores que podem conectar administradores e o custo de cada cabo. Ao iniciar o trabalho, você encontrou um erro no sistema de cálculo de custos - em vez de somar os custos, eles se multiplicam -, portanto, um cabo com o valor 4 e um cabo com o valor 3 juntos não são 7, como sugere a lógica, mas 12.

Para concluir a tarefa, você precisa calcular o custo dos cabos suficientes para a organização de uma rede conectada - de modo que cada computador esteja conectado a cada um, direta ou indiretamente.

Formatos de E / S, exemplos e notas

Formato de entrada


A primeira linha contém os números 0 <N <10 6 , 0 ≤ K <10 6 , 0 ≤ M <10 6 .

As próximas linhas K contêm pares de números 0 <u, v ≤ N - número de computadores já conectados pelo suporte técnico.

As próximas linhas M contêm triplos de números 0 <u, v ≤ N e 0 <p ≤ 10 9 - o número de computadores que os administradores podem conectar usando um custo de cabo p.

Formato de saída


Imprima o custo mínimo de cabos suficiente para construir uma rede conectada ou –1 se for impossível construir uma rede completa.

A resposta pode ser muito grande, então você precisa produzi-lo no módulo 2 31 - 1.

Exemplo 1

EntrarConclusão
2 0 1
2 1 9
9

Exemplo 2

EntrarConclusão
5 0 6
1 3 1
2 4 8
1 4 1
1 2 10
4 1 10
5 3 4
32

Exemplo 3

EntrarConclusão
6 0 3
4 3 2
2 6 9
1 4 8
–1

Anotações


A quantidade de dados de entrada pode atingir 30 MB - preste atenção na velocidade de leitura.

Solução


A rede completa que deve ser construída para resolver o problema nada mais é do que uma árvore de abrangência mínima. (Como as arestas K já foram adicionadas no início da construção, o gráfico resultante não é necessariamente uma árvore, mas é garantido que a contém.)

No cenário clássico, o problema de encontrar a árvore de abrangência mínima envolve minimizar a soma das arestas, mas aqui é necessário minimizar o produto. Felizmente, essas duas árvores coincidem. É fácil provar isso, substituindo os pesos das arestas pelos logaritmos.

Os algoritmos mais famosos para a construção de uma árvore de abrangência mínima são os algoritmos Prima e Kraskal.

No caso de gráficos densos, o algoritmo Prym possui os assintóticos O (N 2 ), que, dada a restrição N <10 6 , não permitem utilizá-lo para uma solução completa do problema. (Mas observe que os dados do teste foram compilados para que a solução com os assintóticos indicados tivesse exatamente metade do ponto)

Uma implementação ingênua do algoritmo de Kruskal que usa uma matriz para manter informações sobre a composição atual dos componentes conectados a gráficos possui os assintóticos O (M log M + N 2 ). Aqui é equivalente a O (N 2 ). Para uma solução completa, você precisa usar uma estrutura de dados conhecida como sistema de união disjunta de conjunto (DSU).

O DSU permite executar duas operações: find (x) localiza o "líder" do conjunto ao qual x pertence (o líder é injetado traduzido injetivamente no número do conjunto); union (x, y) combina os conjuntos aos quais x e y pertencem.

As heurísticas de compressão de caminho e as heurísticas combinadas de classificação, geralmente usadas na implementação de uma estrutura, permitem obter comportamento assintótico, em casos práticos equivalentes a O (1).

Suponha que usamos o DSU para manter informações sobre os componentes de conectividade do gráfico durante a execução do algoritmo Kraskal. Então o comportamento assintótico do algoritmo será O (M log M + N) = O (M log M).

Código de decisão
 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

Observando as métricas do aplicativo, o gerente Vasily levantou a hipótese de que a interface carece de algum entusiasmo que impediria os usuários. Portanto, Vasily solicitou a diversificação da interface do aplicativo para a designer Maria. Depois de vários esboços, Mary apareceu! A idéia, desde o início, estava na superfície - acabou sendo necessário adicionar animações para o texto. Selecionamos vários textos e fizemos animações. Infelizmente, após a conclusão do trabalho, as animações foram misturadas e o texto de origem de cada uma delas foi perdido. Ajude a equipe a entender qual texto é animado em cada caso.

Formatos de E / S, exemplo e anotações

Formato de entrada


Você tem vários arquivos de texto com as animações fornecidas, para cada um você precisa selecionar o texto apropriado.

Link para o arquivo morto com arquivos de animação .

Cada animação é definida por parâmetros:
- canvasWidth canvasHeight - a largura e a altura do contêiner para animação são especificadas na primeira linha de entrada,
- figuresCount - o número de figuras a serem animadas é definido na segunda linha de entrada,
- retângulo centerX centerY largura altura ângulo cor - declaração de um retângulo centrado em um ponto (centerX, centerY), largura × altura, grau de ângulo do ângulo de rotação e cor especificada,
- círculo centerX cor do raio centerY - declaração de um círculo com o centro no ponto (centerX, centerY), raio do raio e cor especificada.

O parâmetro color pode ter os valores {preto, vermelho, branco, amarelo}. O parâmetro angle assume valores no intervalo (-359 °, 359 °).

Para cada figura, vários tipos de animação podem ser especificados ao mesmo tempo, aplicados em paralelo. Além disso, cada tipo de animação pode ser aplicado não mais que uma vez a uma figura. O número de animações aplicadas à figura é definido pelo número 0 ⩽ figureAnimationsCount ⩽ 3 imediatamente após a declaração da figura.

Tipos de animações:
- move destX destY time [cycle] - move uma figura para um ponto (destX, destY) em milissegundos de tempo.
- rodar ângulo tempo [ciclo] - rotação da figura em graus angulares em milissegundos de tempo.
- scale destScale time [cycle] - aumente o número em destScale em milissegundos de tempo.

Se o parâmetro de ciclo for especificado, no final da animação, seu movimento continuará na direção oposta.

Formato de saída


O texto exibido ao reproduzir a animação. Para cada arquivo de animação, a resposta deve ser indicada em uma nova linha. O caso dos caracteres na resposta pode ser arbitrário. Cada texto encontrado na animação é avaliado em 10 pontos.

Exemplo

EntrarConclusão
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

Anotações


Visualização da animação do exemplo:


Solução


A tarefa era implementar a animação. Se a animação for implementada corretamente, ao reproduzir, muitas primitivas serão adicionadas ao texto legível. A animação pode ser feita usando qualquer meio - integrado a plataformas móveis ou soluções de nível inferior.

Exemplo de animação ( link para o arquivo .mov ):



Um exemplo de implementação usando a biblioteca Tkinter do 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
Prazo1 s
Limite de memória256 MB
Entrarentrada padrão ou input.txt
Conclusãosaída padrão ou output.txt
Ocupado Arkady gosta de gastar seu tempo livre participando de vários leilões de retrocomputadores. Em um deles, ele viu o Commodoro que havia visto a vida, que Arkady se apressou em comprar. E desta vez ele adquiriu não apenas hardware, mas também software, uma surpresa o esperava no computador - havia Tetris inacabado pelo proprietário anterior. Empiricamente, Arkady desvendou suas regras.

É oferecido ao jogador um campo Tetris com 10 células de largura e altura ilimitada. Uma lista de todos os tetraminos que devem ser colocados no campo. O Tetramino “cai” imediatamente, ou seja, sua posição é definida uma vez para o movimento correspondente e, durante o outono, a posição e a rotação não podem ser alteradas.

Tetramino cai até tropeçar no fundo ou em outra figura. Se ao mesmo tempo uma linha inteira do campo for preenchida, essa linha desaparecerá e tudo o que estiver acima dela ficará uma célula abaixo.

O número de pontos obtidos é determinado pelo número de linhas destruídas. O jogo termina quando todas as peças propostas foram colocadas. O autor do jogo deixou para trás uma tabela de registros, na qual ele ocupou todos os lugares.

Como mencionado anteriormente, Arkady é uma pessoa muito ocupada. Mas ele também é muito apostador. Ajude-o a se tornar o melhor neste jogo.

Tabela de figuras e suas possíveis curvas

Formatos de E / S, exemplo e anotações

Formato de entrada


Os dados de entrada estão nos arquivos input1.txt, input2.txt, ..., input10.txt. Arquivar com arquivos .

A primeira linha contém um número positivo de figuras N (N ≤ 100).

Em cada linha subseqüente, um único caractere latino do conjunto {'O', 'S', 'Z', 'L', 'J', 'T', 'I'} é transmitido.

Cada símbolo representa uma figura tetramino.

Formato de saída


Para verificação, você deve enviar um arquivo zip com os arquivos de saída localizados em sua raiz com os nomes output1.txt, output2.txt, ..., output10.txt, em que o arquivo de saída outputX.txt deve corresponder ao arquivo de entrada inputX.txt.
O arquivo de resposta consiste em N linhas, cada uma das quais corresponde a um tetramino a partir dos dados de entrada e consiste em dois números A i e B i , indicando o movimento do jogador com a figura proposta:

1. A i indica a coluna do elemento tetramino mais à esquerda (1 ≤ A i ≤ 10).
2. B i indica o sentido de rotação do tetramino (1 ≤ B i ≤ 4).

Se o arquivo necessário não estiver no arquivo morto ou for formado incorretamente, serão atribuídos 0 pontos ao teste correspondente.

Exemplo

EntrarConclusão
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

Anotações


Neste exemplo, 4 linhas serão destruídas.

O estado final do campo:



Informações sobre códigos de erro:

1. PE - um erro de saída foi cometido (por exemplo, não existe essa rotação da figura)
2. WA - informações sobre a rotação e posição da figura foram fornecidas corretamente, mas esse arranjo está além dos limites do campo.
3. TL, ML, OK, RE - esses códigos têm o mesmo significado que nas regras do sistema Yandex.Contest.

Como o problema é NP-completo, a solução não precisa ser ideal do ponto de vista matemático. A eficácia da decisão é determinada pelo número de pontos marcados.

Solução


Esta é uma tarefa de teste aberta. Vamos descobrir o que isso significa.

O participante recebe à sua disposição um arquivo zip, na raiz dos quais estão os arquivos de texto input1.txt, input2.txt, ..., input10.txt. Um arquivo é um conjunto de figuras do tetramino a serem organizadas. Como resposta do participante, é esperado um arquivo zip gerado, na raiz dos quais estão os arquivos output1.txt, output2.txt, ..., output10.txt. Cada arquivo deve conter movimentos por partes na mesma ordem em que são especificados no arquivo do conjunto correspondente.

A tarefa é NP-completa e a solução de cem por cento é apenas uma pesquisa exaustiva. Portanto, a complexidade cresce exponencialmente com o aumento do número de figuras. Como não é necessário entregar o código da solução, não há restrições na memória e no tempo de execução.

Um ponto completo da tarefa foi dado quando uma qualidade "satisfatória" foi alcançada - a solução deveria ter marcado 60% dos pontos. A solução do autor para o problema teve a mesma pontuação, que foi baseada em um algoritmo genético treinado em um randomizador Tetris padrão. Este randomizador é descrito no artigo .

O restante da tarefa não é muito diferente de escrever um bot regular para o tetris, exceto que o "copo" do campo de jogo é ilimitado em altura. Portanto, o sucesso de uma decisão é determinado não por quanto tempo o bot pode tocar sem ir além do “copo”, mas pelo quão bem-sucedido ele organizará um conjunto limitado de figuras.

O participante ficou livre para escolher uma estratégia de solução. Aqui estão alguns deles em ordem crescente de complexidade e aumento do número de pontos marcados:

1. Jogamos "mãos" sem usar o código, anotando movimentos na solução.
2. Escrevemos um visualizador e tocamos "mãos", anotando movimentos na solução.
3. O algoritmo ganancioso. A cada turno, tentamos colocar a peça para que o número de linhas destruídas seja máximo. Se houver várias opções, selecione qualquer uma delas aleatoriamente.
4. O mesmo algoritmo ganancioso do parágrafo 3, apenas é verificado não o sucesso de definir uma figura, mas o sucesso da pesquisa exaustiva de um grupo de figuras (por exemplo, um grupo de cinco figuras).
5. O algoritmo genético. Levamos em conta na função de adequação não apenas o número de linhas quebradas, como no algoritmo ganancioso, mas também a suavidade do "relevo" do campo e, por exemplo, o número de espaços livres formados entre as figuras.

D e E. Quest

Autores: Ilimdar Ablyaev e Ilya Kuteev

Misha faz um jogo para celular no gênero de missões. Ele encontrou na Internet uma biblioteca pronta com um mecanismo para o jogo e criou uma interface baseada nele. Misha está com pressa de lançar o jogo e cometeu vários erros durante o processo de desenvolvimento. Para finalizar o projeto no prazo, Misha pediu ajuda. Faça o download do projeto, corrija erros de compilação, falhas e erros lógicos nele.Complete a missão e vá para a tela do Bingo, na qual a frase secreta aparecerá. Ela será a resposta para o problema.

Baixe o arquivo com o projeto: Android , iOS . O formato de saída é uma frase secreta (string com até 255 caracteres).

Solução Android


1) Exclua a linha com o tema ou adicione qualquer tema.

2) Analisamos o texto da tarefa e corrigimos todos os erros que o IDE destaca.

  1. Removemos os modificadores finais do mBackButton e do mTitleTextView, pois a inicialização requer recursos.
  2. Se você transferir a inicialização do mTitleTextView e mBackButton para o local da declaração, o aplicativo falhará no início, pois ainda não possui um contexto.
  3. Corrigimos o erro com o valor de retorno dos métodos - substituímos Layout por ViewGroup.
  4. okButton getTextTaskControlsLayout.
  5. 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 .

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


All Articles