Райтап на задачу «Беги, Баг, беги!»

Автор:

lol

8 ноября 2026

Misc

#Hard

#Python

#Имитация отжига

08.11.2026

Первая кровь:

Huobase

Сложность:

Hard

Дата публикации:

28.03.2026

Решений:

Рейтинг:

3.6/5

Ссылка:

Решать

Итак, всеми нелюбимый PPC. Что ж, придётся повозиться. Наша цель — 250к шагов. Заходим на сайт и пытаемся набрать такое количество:

Ага, даже если сильно постараться (как я), у вас ничего не выйдет, значит, нужно искать обходные пути:

Идём на разведку и смотрим код страницы через Ctrl + U и наблюдаем такую картину:

Кликаем сюда и понимаем: перед нами полностью ПУБЛИЧНЫЙ движок этой игры. Теперь давайте разберёмся, как работает данная игрушка и как в неё выиграть и набрать 250 000.

Карта, где мы играем, — это, по факту, строка длиной 31 × 21 = 651 символ. 0 — пустая клетка, а 1 — стена. Стены имеют вес в миллиард, именно по этой причине баг не выйдет за границы дозволенного. Старт происходит в клетке 1, 1, финиш — 29, 19. Ну а самое главное — это как ходит сам баг. У каждой клетки есть счётчик. Когда он покидает клетку, её счётчик увеличивается на 1. Но на каждом шаге баг смотрит на соседние клетки и выбирает клетку с самым минимальным весом. В его приоритете он ходит: вниз, вправо, вверх, влево. То есть, упрощённо, его алгоритм такой:

Если вес клетки в его текущем направлении минимальный — он продолжает двигаться в этом направлении.
Если нет, то он выбирает соседнюю клетку с минимальным весом.
При равенстве весов у соседних клеток он двигается по своему приоритетному маршруту, который я описал выше.

Из-за первого пункта у бага есть что-то наподобие «инерции»: пока впереди непосещённая клетка с весом 0, он не сворачивает в боковые проходы, даже если они свободны и быстрее ведут к выходу. Баг идёт ровно прямо, пока не упрётся в стену или пока клетка впереди не станет более посещённой, чем соседняя по его приоритету.

Теперь нам нужно подобрать самый оптимальный вариант карты, чтобы набрать заветные 250 000. Руками это заняло бы уйму времени, поэтому у нас есть верный «жадный» путь. Чтобы мы впустую не тратили время и случайно не пытались угадать лучшую комбинацию стен, мы поступим умнее:

Пишем алгоритм, который меняет статус случайной стены с 0 на 1. То есть фактически делает стену.
Далее мы проверяем, может ли баг добраться до финиша. Если нет — стираем нашу стену и делаем новую.
Если результат улучшился после нашего изменения — оставляем. Если нет — тоже иногда оставляем, но с вероятностью P = exp(delta/T), где T — это температура, которая постепенно уменьшается. Это позволяет выйти из локального максимума. Такой алгоритм называется имитацией отжига.

Теперь наш эксплоит мысленно готов, осталось только написать его):

Находим нужную map:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <math.h>

#define WIDTH 31
#define HEIGHT 21
#define START_X 1
#define START_Y 1
#define EXIT_X 29
#define EXIT_Y 19

#define WALL_WEIGHT 1000000000
#define MAX_STEPS 5000000
#define RANDOM_MAX_STEPS 1000000
#define TARGET 260000

static unsigned char map[WIDTH * HEIGHT];
static unsigned char best_map[WIDTH * HEIGHT];

static uint64_t rng_state = 88172645463325252ULL;

static uint64_t rng_next(void) {
    rng_state ^= rng_state << 13;
    rng_state ^= rng_state >> 7;
    rng_state ^= rng_state << 17;
    return rng_state;
}

static double rng_double(void) {
    return (rng_next() >> 11) * (1.0 / 9007199254740992.0);
}

static int index_of(int x, int y) {
    return x * HEIGHT + y;
}

static int is_border(int x, int y) {
    return x == 0 || y == 0 || x == WIDTH - 1 || y == HEIGHT - 1;
}

static void make_random_map(double wall_chance) {
    for (int x = 0; x < WIDTH; x++) {
        for (int y = 0; y < HEIGHT; y++) {
            int is_wall = is_border(x, y) || rng_double() < wall_chance;
            map[index_of(x, y)] = (unsigned char)is_wall;
        }
    }

    map[index_of(START_X, START_Y)] = 0;
    map[index_of(EXIT_X, EXIT_Y)] = 0;
}

static int exit_reachable(void) {
    static int visited[HEIGHT][WIDTH];
    static int queue_x[WIDTH * HEIGHT];
    static int queue_y[WIDTH * HEIGHT];

    memset(visited, 0, sizeof visited);

    int head = 0;
    int tail = 0;

    queue_x[tail] = START_X;
    queue_y[tail] = START_Y;
    tail++;
    visited[START_Y][START_X] = 1;

    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};

    while (head < tail) {
        int x = queue_x[head];
        int y = queue_y[head];
        head++;

        if (x == EXIT_X && y == EXIT_Y) {
            return 1;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= WIDTH || ny >= HEIGHT) continue;
            if (visited[ny][nx]) continue;
            if (map[index_of(nx, ny)] != 0) continue;

            visited[ny][nx] = 1;
            queue_x[tail] = nx;
            queue_y[tail] = ny;
            tail++;
        }
    }

    return 0;
}

static long long simulate(long long max_steps) {
    int weight[HEIGHT][WIDTH];

    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            weight[y][x] = map[index_of(x, y)] ? WALL_WEIGHT : 0;
        }
    }

    int x = START_X;
    int y = START_Y;
    int direction = 0;
    long long steps = 0;

    while (1) {
        if (x == EXIT_X && y == EXIT_Y) {
            return steps;
        }

        if (steps >= max_steps) {
            return -1;
        }

        int down = weight[y + 1][x];
        int right = weight[y][x + 1];
        int up = weight[y - 1][x];
        int left = weight[y][x - 1];

        int neighbours[4] = {down, right, up, left};
        int forward = neighbours[direction];

        int next_x = x;
        int next_y = y;
        int next_direction = direction;

        if (forward <= down && forward <= right &&
            forward <= up && forward <= left) {
            if (direction == 0) next_y++;
            else if (direction == 1) next_x++;
            else if (direction == 2) next_y--;
            else next_x--;
        } else if (down <= right && down <= up && down <= left) {
            next_y++;
            next_direction = 0;
        } else if (right <= down && right <= up && right <= left) {
            next_x++;
            next_direction = 1;
        } else if (up <= right && up <= down && up <= left) {
            next_y--;
            next_direction = 2;
        } else {
            next_x--;
            next_direction = 3;
        }

        weight[y][x] += 1;
        x = next_x;
        y = next_y;
        direction = next_direction;
        steps++;
    }
}

static void save_map(const char *filename) {
    FILE *file = fopen(filename, "w");

    if (!file) {
        perror(filename);
        return;
    }

    for (int x = 0; x < WIDTH; x++) {
        for (int y = 0; y < HEIGHT; y++) {
            fputc(best_map[index_of(x, y)] ? '1' : '0', file);
        }
    }

    fputc('\n', file);
    fclose(file);
}

static long long random_search(int attempts) {
    long long best_score = 0;

    for (int attempt = 0; attempt < attempts; attempt++) {
        double wall_chance = 0.15 + rng_double() * 0.30;
        make_random_map(wall_chance);

        if (!exit_reachable()) continue;

        long long score = simulate(RANDOM_MAX_STEPS);
        if (score < 0) continue;

        if (score > best_score) {
            best_score = score;
            memcpy(best_map, map, sizeof map);
            printf("random %d: new best %lld\n", attempt, best_score);
            fflush(stdout);
        }

        if ((attempt + 1) % 500000 == 0) {
            printf("random: %d / %d, best: %lld\n",
                   attempt + 1, attempts, best_score);
            fflush(stdout);
        }
    }

    return best_score;
}

static long long annealing(long long current_score, int iterations) {
    long long best_score = current_score;
    double start_temperature = 500.0;
    double end_temperature = 0.5;

    for (int iteration = 0; iteration < iterations; iteration++) {
        double temperature = start_temperature *
            pow(end_temperature / start_temperature,
                (double)iteration / iterations);

        int x = 1 + (int)(rng_double() * (WIDTH - 2));
        int y = 1 + (int)(rng_double() * (HEIGHT - 2));

        if ((x == START_X && y == START_Y) ||
            (x == EXIT_X && y == EXIT_Y)) {
            continue;
        }

        int cell = index_of(x, y);
        unsigned char old_value = map[cell];
        map[cell] = !old_value;

        if (!exit_reachable()) {
            map[cell] = old_value;
            continue;
        }

        long long score = simulate(MAX_STEPS);
        if (score < 0) {
            map[cell] = old_value;
            continue;
        }

        long long delta = score - current_score;
        int accept = delta >= 0 ||
            rng_double() < exp((double)delta / temperature);

        if (accept) {
            current_score = score;
        } else {
            map[cell] = old_value;
        }

        if (current_score > best_score) {
            best_score = current_score;
            memcpy(best_map, map, sizeof map);
            printf("anneal %d: new best %lld, T: %.2f\n",
                   iteration, best_score, temperature);
            fflush(stdout);
        }

        if (best_score >= TARGET) {
            break;
        }
    }

    return best_score;
}

int main(int argc, char **argv) {
    if (argc > 1) {
        rng_state = strtoull(argv[1], NULL, 10);
    }

    if (rng_state == 0) {
        rng_state = 88172645463325252ULL;
    }

    int random_attempts = argc > 2 ? atoi(argv[2]) : 3000000;
    int anneal_iterations = argc > 3 ? atoi(argv[3]) : 2000000;
    const char *output_file = argc > 4 ? argv[4] : "map.txt";

    printf("random search...\n");
    long long seed_score = random_search(random_attempts);
    printf("seed score: %lld\n", seed_score);

    if (seed_score <= 0) {
        puts("no seed found");
        return 1;
    }

    memcpy(map, best_map, sizeof map);

    printf("annealing...\n");
    long long final_score = annealing(seed_score, anneal_iterations);
    printf("final score: %lld\n", final_score);

    save_map(output_file);
    printf("map saved to %s\n", output_file);
    return 0;
}

Далее берём параметры map и подставляем в наш финальный эксплоит:

import random
import string
import sys

import requests

BASE = "https://bug-run.t1.bug-makers.ru"

MAP = (
    "111111111111111111111100100000010010000011100000100010011110001100100000010100011011101010001100000"
    "000001101100000010100101001110010101000010110101100000011101101111001110110100010000000101100011001"
    "101001010101110100000001000000101100001010100101000101101010011100000101001101000000110000110001110"
    "010101000111010101110111010111100000011100100000000000111101101001111010101010101101000010101010000"
    "001100111000000101011101101000110110000011101101100001001110101101100011000001011100001101000101010"
    "001000101101011001100001100111101010100010010100001100000101001000100011111010010101000010101100010"
    "000001000110001100100010100000001101111111111111111111111"
)


def main():
    nickname = "exploit_" + "".join(random.choices(string.ascii_lowercase, k=6))

    session = requests.Session()
    session.headers["User-Agent"] = "Mozilla/5.0"

    response = session.post(
        f"{BASE}/api/session/start",
        json={"nickname": nickname},
        timeout=30,
    )
    response.raise_for_status()
    print("session:", response.json())

    response = session.post(
        f"{BASE}/api/submit",
        json={"map": MAP},
        timeout=120,
    )
    print("HTTP:", response.status_code)

    data = response.json()
    print("response:", data)

    if not data.get("qualified") or not data.get("flag"):
        print("Сервер не засчитал карту")
        return 1

    print("FLAG:", data["flag"])
    return 0


if __name__ == "__main__":
    sys.exit(main())

Ну и результат нашей работы: