Leono 27 дек 2019 в 12:21

Бот для тетриса и реверс-инжиниринг анимации. Разбор мобильного трека второго чемпионата по программированию

18 мин

5.5K

Блог компании ЯндексСпортивное программирование*Занимательные задачкиРазработка мобильных приложений*Алгоритмы*

^{_{Победители мобильного трека}}

В уходящем году Яндекс провел два онлайн-чемпионата по программированию. Мы продолжаем публиковать разборы задач второго чемпионата. Напоминаем, что участникам было предложено четыре трека: машинное обучение, фронтенд, мобильная разработка и бэкенд. Перед вами разбор квалификационного раунда для мобильных разработчиков — 121 человек из числа прошедших квалификацию затем приняли участие в финале. Задачи придумали специалисты из Яндекс.Браузера и других команд поискового портала. В этом хабрапосте мы коснемся темы генетических алгоритмов, напишем бота для тетриса и пройдем квест разными для Android и iOS методами.

А. Кабели

^{Автор: Сергей Мясников}

	Все языки	Python 3.7.3 и Python 2.7
Ограничение времени	4 с	20 c
Ограничение памяти	256 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

В новый офис привезли N компьютеров. Расположенный рядом радиотелескоп не позволяет использовать Wi-Fi для связи, и хелпдеску придется организовывать сеть с помощью LAN-кабелей. Собрав все завалявшиеся по углам кабели, админы сумели соединить K пар компьютеров. Утомившись после длинного рабочего дня, сотрудники хелпдеска обратились к вам за помощью — рассчитать бюджет, необходимый для завершения задачи. Так у вас появился список из M пар компьютеров, которые могут соединить админы, и стоимость каждого кабеля. Начав работу, вы обнаружили баг в системе расчета стоимости — вместо сложения стоимостей, они умножаются — так кабель стоимостью 4 и кабель стоимостью 3 вместе стоят не 7, как подсказывает логика, а 12.

Для выполнения задачи вам необходимо рассчитать стоимость кабелей, достаточных для организации связной сети — такой, что каждый компьютер соединен с каждым прямо или опосредованно.

Форматы ввода/вывода, примеры и примечания

Формат ввода

Первая строка содержит числа 0 < N < 10⁶, 0 ≤ K < 10⁶, 0 ≤ M < 10⁶.

Следующие K строк содержат пары чисел 0 < u, v ≤ N — номера компьютеров, уже соединенных хэлпдеском.

Следующие M строк содержат тройки чисел 0 < u, v ≤ N и 0 < p ≤ 10⁹ — номера компьютеров, которые админы могут соединить при помощи кабеля стоимостью p.

Формат вывода

Выведите минимальную стоимость кабелей, достаточных для построения связанной сети, или –1 если построить полную сеть невозможно.

Ответ может быть очень большим, поэтому вывести его необходимо по модулю 2³¹ – 1.

Пример 1

Ввод	Вывод
`2 0 1 2 1 9`	`9`

Пример 2

Ввод	Вывод
`5 0 6 1 3 1 2 4 8 1 4 1 1 2 10 4 1 10 5 3 4`	`32`

Пример 3

Ввод	Вывод
`6 0 3 4 3 2 2 6 9 1 4 8`	`–1`

Примечания

Объем входных данных может достигать 30 МБ — обратите внимание на скорость чтения.

Решение

Полная сеть, которую необходимо построить для решения задачи, — это не что иное, как минимальное остовное дерево. (Учитывая, что на момент начала построения уже добавлено K ребер, результирующий граф не обязательно является деревом, однако гарантированно содержит его.)

В классической постановке задача о нахождении минимального остовного дерева предполагает минимизацию суммы ребер, но здесь необходимо минимизировать произведение. К счастью, эти два дерева совпадают. Это несложно доказать, заменив веса ребер на их логарифмы.

Самые известные алгоритмы для построения минимального остовного дерева — это алгоритмы Прима и Краскала.

В случае плотных графов алгоритм Прима имеет асимптотику O(N²), что, учитывая ограничение N < 10⁶, не позволяет использовать его для полного решения задачи. (Но отметим, что тестовые данные были составлены так, чтобы решение с указанной асимптотикой набирало ровно половину балловю)

Наивная реализация алгоритма Краскала, использующая массив для поддержания информации о текущей композиции компонент связности графа, имеет ассимптотику O(M log M + N²). Здесь это равнозначно O(N²). Для полного решения нужно использовать структуру данных, известную как cистема непересекающихся множеств (disjoint-set union, DSU).

DSU позволяет выполнять две операции: find(x) находит «лидера» множества, которому принадлежит x (лидер инъективно переводим в номер множества); union(x, y) объединяет множества, которым принадлежат x и y.

Эвристика сжатия путей и эвристика объединения по рангу, обычно применяемые при реализации структуры, позволяют добиться асимптотик, в практических случаях эквивалентных O(1).

Предположим, мы воспользовались DSU для поддержания информации о компонентах связности графа в процессе выполнения алгоритма Краскала. Тогда асимптотика алгоритма будет равна O(M log M + N) = O(M log M).

Код решения

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. Утерянные фразы

^{Автор: Дмитрий Фисько}

Взглянув на метрики приложения, менеджер Василий выдвинул гипотезу, что в интерфейсе не хватает некоей изюминки, которая удерживала бы пользователей. Поэтому Василий обратился с просьбой разнообразить интерфейс приложения к дизайнеру Марии. После нескольких скетчей Марию осенило! Идея с самого начала лежала на поверхности — оказалось, нужно добавить анимации для текста. Выбрали несколько текстов и сделали анимации. К сожалению, после завершения работы анимации перемешались, а исходный текст для каждой из них потерялся. Помогите команде понять, какой текст анимировался в каждом случае.

Форматы ввода/вывода, пример и примечания

Формат ввода

У вас есть несколько текстовых файлов с заданными анимациями, для каждой нужно подобрать подходящий текст.

Ссылка на архив с файлами анимации.

Каждая анимация определена параметрами:
— canvasWidth canvasHeight — ширина и высота контейнера для анимации, задаются в первой строке ввода,
— figuresCount — количество фигур, которые предстоит анимировать, задается во второй строке ввода,
— rectangle centerX centerY width height angle color — объявление прямоугольника с центром в точке (centerX, centerY), размером width × height, градусом угла поворота angle и указанным цветом,
— circle centerX centerY radius color — объявление круга с центром в точке (centerX, centerY), радиусом radius и указанным цветом.

Параметр color может иметь значения {black, red, white, yellow}. Параметр angle принимает значения в диапазоне (-359°, 359°).

Для каждой фигуры может быть задано сразу несколько типов анимации, которые применяются параллельно. При этом каждый тип анимации может применяться не более одного раза к фигуре. Количество анимаций, применяющихся к фигуре, задается числом 0 ⩽ figureAnimationsCount ⩽ 3 сразу после объявления фигуры.

Типы анимаций:
— move destX destY time [cycle] — движение фигуры в точку (destX, destY) за time миллисекунд.
— rotate angle time [cycle] — поворот фигуры на angle градусов за time миллисекунд.
— scale destScale time [cycle] — увеличение фигуры на destScale за time миллисекунд.

Если указан параметр cycle, то по завершении анимации ее движение продолжается в обратную сторону.

Формат вывода

Отображаемый текст при воспроизведении анимации. Для каждого файла анимации ответ нужно указывать на новой строке. Регистр символов в ответе может быть произвольным. Каждый найденный в анимации текст оценивается в 10 баллов.

Пример

Ввод Вывод

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

Примечания

Визуализация анимации из примера:

Решение

Задача сводилась к реализации анимации. Если анимация реализована корректно, то при воспроизведении множество примитивов складывается в читаемый текст. Анимацию можно было сделать с использованием любых средств — интегрированных в мобильные платформы или более низкоуровневых решений.

Пример анимации (ссылка на файл .mov):

Пример реализации с иcпользованием библиотеки Tkinter из 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. Бот для тетриса

^{Автор: Дмитрий Неведомский}

Ограничение времени	1 с
Ограничение памяти	256 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Занятой Аркадий любит проводить свободное время, участвуя в разных аукционах ретрокомпьютеров. На одном из них ему попался повидавший жизнь Commodoro, который Аркадий поспешил купить. И в этот раз он приобрел не только железо, но и софт, на компьютере его ждал сюрприз — там нашелся недописанный предыдущим владельцем Тетрис. Опытным путем Аркадий разгадал его правила.

Игроку предлагается поле для игры в тетрис на 10 клеток в ширину и неограниченной высоты. Задан список всех тетрамино, которые необходимо разместить на поле. Тетрамино «падают» сразу, то есть их позиция устанавливается единожды для соответствующего хода, и во время падения положение и поворот изменять нельзя.

Тетрамино падает, пока не наткнется на дно или на другую фигуру. Если при этом заполнился целый ряд поля, этот ряд пропадает, и всё, что находится выше него, опускается на одну клетку ниже.

Количество полученных баллов определяется количеством разрушенных рядов. Игра заканчивается, когда все предложенные фигуры были расставлены. Автор игры оставил после себя таблицу рекордов, в которой сам и занял все места.

Как было сказано ранее, Аркадий — очень занятой человек. Но еще он очень азартный. Помогите ему стать лучшим в этой игре.

Таблица фигур и их возможных поворотов

Форматы ввода/вывода, пример и примечания

Формат ввода

Входные данные находятся в файлах input1.txt, input2.txt, ..., input10.txt. Архив с файлами.

В первой строке задано положительное число фигур N (N ≤ 100).

В каждой последующей строке передается единственный символ латинского алфавита из множества {’O’, ’S’, ’Z’, ’L’, ’J’, ’T’, ’I’}.

Каждый символ обозначает фигуру тетрамино.

Формат вывода

На проверку необходимо сдать zip-архив c размещенными в его корне выходными файлами с названиями output1.txt, output2.txt,..., output10.txt, где выходной файл outputX.txt должен соответствовать входному файлу inputX.txt.
Файл ответа состоит из N строк, каждая из которых соответствует тетрамино из входных данных и состоит из двух чисел A_i и B_i, обозначающих ход игрока предложенной фигурой:

1. A_i указывает столбец крайнего левого элемента тетрамино (1 ≤ A_i ≤ 10).
2. B_i указывает направление поворота тетрамино (1 ≤ B_i ≤ 4).

Если необходимый файл отсутствует в архиве или был сформирован неправильно, то за соответствующий тест будет начислено 0 баллов.

Пример

Ввод	Вывод
`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`

Примечания

В этом примере будет разрушено 4 ряда.

Конечное состояние поля:

Информация по кодам ошибок:

1. PE — была допущена ошибка вывода (например, не существует такого поворота фигуры)
2. WA — информация о повороте и положении фигуры была предоставлена верно, однако такое расположение выходит за границы поля.
3. TL, ML, OK, RE — эти коды имеют то же значение, что и в правилах системы Яндекс.Контест.

Так как задача NP-полная, решение не должно быть оптимальным с математической точки зрения. Эффективность решения определяется числом набранных баллов.

Решение

Это задача с открытыми тестами. Разберемся, что это означает.

Участник получает в свое распоряжение zip-архив, в корне которого находятся текстовые файлы input1.txt, input2.txt, ..., input10.txt. Один файл представляет собой один набор фигур тетрамино, которые предстоит расставить. В качестве ответа от участника ожидается сформированный zip-архив, в корне которого находятся файлы output1.txt, output2.txt, ..., output10.txt. Каждый файл должен содержать ходы фигурами в том же порядке, в котором они заданы в файле соответствующего набора.

Задача NP-полна и стопроцентным решением является только полный перебор. Значит, сложность растет экспоненциально с увеличением количества фигур. Так как не требуется сдавать код решения, то на него не накладываются ограничения по памяти и времени исполнения.

Полный балл за задачу давался при достижении «удовлитворительного» качества — решение должно было набрать 60% очков. Столько же набрало решение автора задачи, которое было основано на генетическом алгоритме, натренированном на стандартном рандомизаторе тетриса. Этот рандомизатор описан в статье.

В остальном задача мало чем отличается от написания обычного бота для тетриса, за исключением того, что «стакан» игрового поля неограничен по высоте. Поэтому успешность решения определяется не тем, как долго бот может играть, не выходя за рамки «стакана», а тем, как успешно он расставит ограниченный набор фигур.

Участник был волен сам выбирать стратегию решения. Вот некоторые из них в порядке усложнения и увеличения числа набираемых очков:

1. Играем «руками» без использования кода, записывая ходы в решение.
2. Пишем визуализатор и играем «руками», записывая ходы в решение.
3. Жадный алгоритм. На каждом ходу пробуем поставить фигуру так, чтобы число разрушенных рядов было максимальным. Если таких вариантов несколько, случайно выбираем любой из них.
4. Такой же жадный алгоритм, как в пункте 3, только проверяется не успешность постановки одной фигуры, а успешность полного перебора группы фигур (например, группы из пяти фигур).
5. Генетический алгоритм. Учитываем в функции приспособленности (fitness function) не только количество разрушенных рядов, как в жадном алгоритме, но и гладкость «рельефа» поля и, например, количество образовавшихся свободных мест между фигурами.

D и E. Квест

^{Авторы: Илимдар Абляев и Илья Кутеев}

Миша делает мобильную игру в жанре квест. Он нашел в интернете готовую библиотеку с движком для игры и сделал на его основе интерфейс. Миша очень торопится выпустить игру и в процессе разработки допустил несколько ошибок. Чтобы закончить проект вовремя, Миша попросил у вас помощи. Скачайте проект, поправьте в нем ошибки компиляции, падения и логические ошибки. Пройдите квест и дойдите до экрана «Бинго», на котором появится секретная фраза. Она и будет ответом к задаче.

Скачайте архив с проектом: 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 году.

Теги:

Хабы: