Бэтмен | C++ для приматов

Задача

Речь пойдёт о первой задаче уровня Medium на сайте codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа W и H — соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x и y — координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка DIR, задающая направление, в котором следует искать бобму:

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

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

Обозначим координаты бобмы через BX и BY и введём четыре вспомогательных параметра: l, r, u, b — «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства [latex] l \leq BX \leq r [/latex] и [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex], [latex] r = W — 1 [/latex], [latex] u = 0 [/latex] и [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения Bx и By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

[latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство [latex] l \leq BX \leq x — 1 [/latex]. Положим [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.
[latex] BX = x [/latex] (если DIR — одна из строк «U» и «B»). В этом случае всё хорошо.
[latex] BX > x [/latex] (если DIR — одна из строк «R», «DR», «UR»). В этом случае справедливо неравенство [latex] x + 1 \leq BX \leq r [/latex]. Положим [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.

Если [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число, ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int W, H;   // Количество окон по горизонтали и вертикали соответственно
    cin >> W >> H; cin.ignore();
    int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ
    int N;
    cin >> N; cin.ignore();
    int x, y;
    cin >> x >> y; cin.ignore();

    // Игровой цикл
    while (1) {
        string DIR; // Направление, в котором находится бомба
        cin >> DIR;
        if ((DIR[0] == 'L')  ||  (DIR[1] == 'L'))
            r = x - 1;
        if ((DIR[0] == 'R')  ||  (DIR[1] == 'R'))
            l = x + 1;
        if (DIR[0] == 'U')
            d = y - 1;
        if (DIR[0] == 'D')
            u = y + 1;
        
        x = (l + r)/2;  // Абсцисса нового окна
        y = (u + d)/2;  // Ордината нового окна
        
        cout << x << " " << y << endl;
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int W, H; // Количество окон по горизонтали и вертикали соответственно

cin >> W >> H; cin.ignore();

int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ

int N;

cin >> N; cin.ignore();

int x, y;

cin >> x >> y; cin.ignore();

// Игровой цикл

while (1) {

string DIR; // Направление, в котором находится бомба

cin >> DIR;

if ((DIR[0] == 'L') || (DIR[1] == 'L'))

r = x - 1;

if ((DIR[0] == 'R') || (DIR[1] == 'R'))

l = x + 1;

if (DIR[0] == 'U')

d = y - 1;

if (DIR[0] == 'D')

u = y + 1;

x = (l + r)/2; // Абсцисса нового окна

y = (u + d)/2; // Ордината нового окна

cout << x << " " << y << endl;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt(), h = in.nextInt();
        int l = 0, r = w-1, u = 0, d = h-1;
        int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        
        while (true) {
            char dir = in.next().charAt(0);
            if ((dir == 'L') || (dir == 'L'))
                r = x-1;
            if ((dir == 'R') || (dir == 'R'))
                l = x+1;
            if (dir == 'U')
                d = y-1;
            if (dir == 'D')
                u = y+1;
            x = (l + r) / 2;
            y = (u + d) / 2;
            System.out.println(x + " " + y);
        }
    }
}