Стрельба 1 Максимизация дистанции

Question

Петя играет в одну простую игру под названием «Стрельба 1». Игра заключается в следующем – есть персонаж, который передвигается в плоском мире со скоростью 1 клетка в секунду и умеет стрелять из пистолета. Первоначально персонаж начинает движение с координаты 0 (двигаясь по одномерной оси) и имеет пистолет, который может достигать цели при стрельбе с расстояния 4 клетки, притом нанося препятствию 2 единицы урона в секунду. Также заранее известны координаты всех препятствий и их очки здоровья (ОЗ).

В игре есть возможность понизить здоровье одного любого препятствия до начала игры в два раза нацело (если было 5, станет 2; если 6, станет 3; если 1, станет 0), чтобы персонаж дошёл как можно дальше. Таким образом требуется помочь Пете определить, какому препятствию выгоднее всего убрать половину здоровья, чтобы персонаж прошёл как можно дальше.

Входные данные:

На вход на первой строке подаётся целое число L (1 <= L <= 100000) – длина оси, по которой будет передвигаться персонаж.

На второй строке подаётся целое число N (1 <= N <= 1000) – количество препятствий на оси.

Далее на N строках подаются целые координаты препятствий (целое число от 1 до L-1) и их ОЗ (целое число от 1 до 100) через пробел (например, 5 2, на координате 5 стоит препятствие с 2 ОЗ).

Выходные данные:

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

На второй строке вывести количество единиц, которое при этом пройдёт персонаж.

Примечание:

Если персонаж проходит весь маршрут и понижать здоровье никакому препятствию не требуется, вывести на первой строке 0, а на второй L.

Если персонаж может пройти одинаковое максимальное расстояние при понижении здоровья различным препятствям, то в выводе указать препятствие с самой большой координатой.

Когда персонаж не доходит до конца (упирается в препятствие, которое не успел уничтожить), то считается, что он прошёл ровно такое расстояние, на координате которой стояло препятствие (если персонаж закончил игру на препятствии по координате 9, то считается, что он прошёл 9 клеток).

Пример:

Входные данные

Выходные данные

15
3
3 6
5 4
9 10

9
15

Рассмотрим пример №1

Персонаж начинает с координаты 0, на расстоянии 3 есть препятствие с 6 ОЗ.

Персонаж сразу же может начать стрелять, так как расстояние меньше 4.

Придя на координату 3 – это препятствие будет уничтожено (нанося урон по 2 ОЗ).

Сразу же можно начать уничтожать препятствие по координате 5 (4 ОЗ). Как раз расстояние 2, потому оно будет уничтожено (выстрелом с координаты 3 и 4).

Препятствие по координате 9 имеет 10 ОЗ, значит оно не может быть уничтожено, но может быть понижено его здоровье в 2 раза в самом начале игры (есть возможность понизить ОЗ одного препятствия), таким образом, персонаж сможет дойти по оси до самого конца.

Answer 1

Чтобы решить задачу, необходимо определить, какое препятствие выгоднее всего понизить вдвое, чтобы персонаж мог пройти максимально возможное расстояние.

Шаги решения:

Понимание проблемы:
- Персонаж движется со скоростью 1 клетка в секунду по оси от 0 до L.
- Есть N препятствий с координатами и здоровьем (ОЗ).
- Персонаж может стрелять по препятствиям, находящимся в пределах 4 клеток, нанося 2 единицы урона в секунду.
- Перед началом игры можно выбрать одно препятствие и уменьшить его здоровье вдвое (округление вниз).
- Необходимо определить, какое препятствие выбрать для уменьшения здоровья, чтобы персонаж прошёл как можно дальше.
Алгоритм:
- Инициализация: Для каждого препятствия вычисляем время, когда оно входит в зону стрельбы (t_start = max(x - 4, 0)) и время, когда персонаж достигает его позиции (t_end = x). Также рассчитываем необходимое время для уничтожения препятствия (D_i = ceil(H_i / 2)).
- Проверка начальной возможности:
  - Сортируем препятствия по времени t_end.
  - Проверяем, можно ли уничтожить все препятствия без понижения здоровья какого-либо из них. Если да, выводим 0 и L.
- Оптимизация:
  - Если невозможно пройти весь маршрут без понижения здоровья, проверяем для каждого препятствия, как повлияет его понижение на возможность прохождения.
  - Для каждого препятствия уменьшаем его здоровье вдвое, пересчитываем необходимое время D_i и проверяем, можно ли пройти весь маршрут с этим изменением.
  - Выбираем препятствие, при понижении которого достигается максимальное расстояние. Если таких препятствий несколько, выбираем то, которое находится дальше по оси.
Реализация:
- Используем функцию max_reachable, которая проверяет, насколько далеко может пройти персонаж при заданных условиях.
- Перебираем все препятствия, понижаем их здоровье по очереди и определяем максимальное расстояние, которое можно пройти.
- Выбираем препятствие с наибольшим вкладом в достижение максимального расстояния.

Реализация на Python:

python
import math

def ceil_div(a, b):
    return (a + b - 1) // b

def max_reachable(obstacles_sorted, L):
    total_time = 0
    for obs in obstacles_sorted:
        total_time += obs['D_i']
        if total_time > obs['t_end']:
            return obs['x']
    return L

def main():
    import sys
    import copy
    L = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    obstacles = []
    for _ in range(N):
        x, H = map(int, sys.stdin.readline().split())
        t_start = max(x - 4, 0)
        t_end = x
        D_i = ceil_div(H, 2)
        obstacles.append({'x': x, 'H': H, 't_start': t_start, 't_end': t_end, 'D_i': D_i})
    
    # Sort obstacles by t_end
    obstacles_sorted = sorted(obstacles, key=lambda obs: obs['t_end'])
    
    # Compute initial max_reachable
    initial_reachable = max_reachable(obstacles_sorted, L)
    
    if initial_reachable >= L:
        print(0)
        print(L)
        return
    
    best_distance = initial_reachable
    best_x = 0
    
    for i in range(N):
        obs = obstacles[i]
        H_halved = obs['H'] // 2
        D_i_halved = ceil_div(H_halved, 2)
        if D_i_halved < obs['D_i']:
            # Create a deep copy of obstacles
            modified_obstacles = copy.deepcopy(obstacles)
            # Update the halved obstacle
            modified_obstacles[i]['H'] = H_halved
            modified_obstacles[i]['D_i'] = D_i_halved
            # Sort the modified obstacles by t_end
            modified_sorted = sorted(modified_obstacles, key=lambda o: o['t_end'])
            # Compute max_reachable
            reachable = max_reachable(modified_sorted, L)
            # Update best_x and best_distance
            if reachable > best_distance or (reachable == best_distance and obs['x'] > best_x):
                best_distance = reachable
                best_x = obs['x']
    
    print(best_x)
    print(best_distance)

if __name__ == "__main__":
    main()

Пояснение:

Функция ceil_div(a, b): Вычисляет деление с округлением вверх.
Функция max_reachable: Проверяет, можно ли пройти все препятствия до конца маршрута L, и возвращает максимальное достижимое расстояние.
Основная логика:
- Читаем входные данные и инициализируем список препятствий.
- Проверяем, можно ли пройти весь маршрут без понижения здоровья.
- Если нет, для каждого препятствия уменьшаем его здоровье и проверяем, как это влияет на достижимое расстояние.
- Выбираем наиболее выгодное препятствие для понижения здоровья.

Пример:

Входные данные:

Выходные данные:

text
9
15

Заключение:

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

Answer 2

Чтобы помочь Коле определить максимальное расстояние, которое его персонаж сможет пройти в игре «Стрельба 2», необходимо тщательно проанализировать взаимодействие движения персонажа, стрельбы по препятствиям и влияния туманных областей на эффективность выстрелов. Ниже представлено пошаговое решение задачи с объяснением и реализацией на языке Python.

Понимание задачи

Основные компоненты игры:

Движение:
- Персонаж движется по оси со скоростью M клеток в секунду.
- Начальная позиция персонажа — координата 0.
- Цель — достичь координаты L.
Стрельба:
- Пистолет может поражать цели на расстоянии K клеток.
- Каждую секунду персонаж может совершить U выстрелов.
- Каждый выстрел наносит 1 единицу урона, если путь не пересекает туманные области.
Препятствия:
- На оси расположено N препятствий с заданными координатами и здоровьем (ОЗ).
- Персонаж должен уничтожить препятствие до того, как достигнет его координаты.
Туманные области:
- На оси расположено D туманных областей.
- При стрельбе через туман эффективность выстрела снижается: floor(damage / 2).
- Если выстрел проходит через несколько туманов, снижается только один раз (первым туманом).

Цель:

Определить максимальное расстояние, которое персонаж сможет пройти, уничтожив препятствия до их координат. Если невозможно уничтожить препятствие до его координаты, персонаж останавливается на его позиции.

Подход к решению

Для эффективного решения задачи необходимо:

Предобработка данных:
- Отсортировать препятствия по координатам.
- Отсортировать позиции туманных областей для быстрого поиска.
Определение возможности уничтожения препятствий:
- Для каждого препятствия определить, существует ли позиция y в диапазоне [x - K, x - 1], откуда можно выстрелить по препятствию x без прохождения через туман.
- Если такая позиция существует, препятствие можно уничтожить.
Расчет необходимого количества выстрелов:
- Для уничтожения препятствия с ОЗ = H требуется ceil(H / U) выстрелов.
- Эти выстрелы необходимо распределить во времени, находясь в допустимом диапазоне времени перед достижением препятствия.
Назначение времени выстрелов:
- Использовать жадный алгоритм: назначать выстрелы как можно позже в допустимом диапазоне времени для каждого препятствия.
- Проверять, не конфликтуют ли выстрелы с другими препятствиями.
Определение максимального расстояния:
- Если все препятствия можно уничтожить до их координат, персонаж достигает L.
- В противном случае, персонаж останавливается на координате первого неразрушенного препятствия.

Детальный алгоритм

Сортировка данных:
- Отсортировать список туманных областей для быстрого поиска.
- Отсортировать препятствия по координатам.
Проверка возможности уничтожения препятствий:
- Для каждого препятствия x:
  - Проверить диапазон позиций y = x - K до y = x - 1.
  - Для каждой позиции y проверить, есть ли туман между y и x.
  - Если существует позиция y, откуда можно выстрелить по x без прохождения через туман, пометить препятствие как уничтожаемое.
Назначение времени выстрелов:
- Для каждого уничтожаемого препятствия:
  - Определить допустимый диапазон времени [t_start, t_end], когда можно выстрелить по нему.
    - t_start = ceil((x - K) / M)
    - t_end = ceil(x / M) - 1
  - Вычислить необходимое количество выстрелов: shots_needed = ceil(H / U)
  - Назначить shots_needed секунд для выстрелов в пределах [t_start, t_end], начиная с t_end и двигаясь назад.
  - Если невозможно назначить все необходимые выстрелы, персонаж останавливается на координате x.
Вывод результата:
- Если все препятствия можно уничтожить, вывести L.
- Иначе, вывести координату первого неразрушенного препятствия.

Реализация на Python

Ниже представлена реализация описанного алгоритма на языке Python:

python
import sys
import math
import bisect

def main():
    import sys
    import math

    # Чтение входных данных
    L_K_U_M = sys.stdin.readline().split()
    while len(L_K_U_M) < 4:
        L_K_U_M += sys.stdin.readline().split()
    L, K, U, M = map(int, L_K_U_M)

    N = int(sys.stdin.readline())
    obstacles = []
    for _ in range(N):
        parts = sys.stdin.readline().split()
        while len(parts) < 2:
            parts += sys.stdin.readline().split()
        x, H = map(int, parts)
        obstacles.append({'x': x, 'H': H})

    D = int(sys.stdin.readline())
    fog_positions = []
    for _ in range(D):
        p = int(sys.stdin.readline())
        fog_positions.append(p)
    fog_positions.sort()

    # Сортировка препятствий по координате
    obstacles.sort(key=lambda obs: obs['x'])

    # Определение максимально возможного времени
    T_max = (L + M - 1) // M + 1  # Добавляем 1 для безопасного индекса
    assigned = [False] * (T_max + 1)

    for obs in obstacles:
        x = obs['x']
        H = obs['H']

        # Проверка возможности уничтожения препятствия
        shooting_possible = False
        # Проверка всех возможных позиций y
        y_min = max(x - K, 0)
        y_max = x - 1
        for y in range(y_max, y_min -1, -1):
            left = y + 1
            right = x - 1
            if left > right:
                # Нет позиций между y и x, значит тумана нет
                shooting_possible = True
                break
            # Проверка наличия тумана в диапазоне [left, right]
            idx = bisect.bisect_left(fog_positions, left)
            if idx < len(fog_positions) and fog_positions[idx] <= right:
                continue  # Есть туман в пути
            else:
                # Нет тумана в пути от y до x
                shooting_possible = True
                break

        if not shooting_possible:
            # Невозможно уничтожить препятствие, остановиться на его координате
            print(x)
            return

        # Вычисление допустимого диапазона времени для стрельбы
        # t_start = ceil((x - K) / M)
        # t_end = ceil(x / M) -1
        t_start = (x - K + M -1) // M
        t_start = max(t_start, 0)
        t_end = (x + M -1) // M -1
        t_end = max(t_end, t_start)  # Обеспечиваем, что t_end >= t_start

        # Количество необходимых выстрелов
        shots_needed = (H + U -1) // U

        # Назначение выстрелов как можно позже
        current_time = t_end
        for _ in range(shots_needed):
            while current_time >= t_start and assigned[current_time]:
                current_time -=1
            if current_time < t_start:
                # Невозможно назначить все необходимые выстрелы
                print(x)
                return
            else:
                assigned[current_time] = True
                current_time -=1

    # Если все препятствия уничтожены, персонаж достиг конечной точки
    print(L)

if __name__ == "__main__":
    main()

Пояснения к коду:

Чтение входных данных:
- Считываем значения L, K, U, M.
- Считываем N препятствий с их координатами и здоровьем.
- Считываем D позиций туманных областей и сортируем их для быстрого поиска.
Сортировка препятствий:
- Препятствия сортируются по координате x для последовательной обработки.
Назначение времени выстрелов:
- Определяем максимально возможное время T_max, исходя из L и M.
- Инициализируем массив assigned, где assigned[t] = True означает, что в момент времени t уже назначен выстрел.
- Для каждого препятствия:
  - Проверяем, существует ли позиция y в диапазоне [x - K, x - 1], откуда можно выстрелить без прохождения через туман.
  - Если можно, вычисляем допустимый диапазон времени для стрельбы [t_start, t_end].
  - Вычисляем необходимое количество выстрелов shots_needed.
  - Назначаем выстрелы, начиная с t_end и двигаясь назад, проверяя доступность времени.
  - Если невозможно назначить все выстрелы, выводим координату препятствия и завершаем программу.
Вывод результата:
- Если все препятствия можно уничтожить, выводим L.

Пример работы алгоритма

Входные данные:

Объяснение:

Препятствия:
- 3: ОЗ = 3
- 5: ОЗ = 2
- 9: ОЗ = 6
Туманные области: 4 и 5
Параметры движения и стрельбы:
- L = 15
- K = 3
- U = 1
- M = 1

Процесс:

Препятствие 3:
- Возможные позиции y: 0,1,2
- Проверяем от y = 2:
  - Путь от 2 до 3: нет тумана.
  - Можно выстрелить из y = 2.
- t_start = ceil((3 - 3)/1) = 0
- t_end = ceil(3/1) -1 = 2
- shots_needed = ceil(3/1) = 3
- Назначаем выстрелы на времена 2,1,0.
Препятствие 5:
- Возможные позиции y: 2,3,4
- Проверяем от y = 4:
  - Путь от 4 до 5: туман на 4.
  - Наносимый урон = floor(1/2) = 0 → выстрел не наносит урона.
- Проверяем от y = 3:
  - Путь от 3 до 5: туман на 4.
  - Наносимый урон = 0.
- Проверяем от y = 2:
  - Путь от 2 до 5: туман на 4.
  - Наносимый урон = 0.
- Препятствие 5 нельзя уничтожить.
- Персонаж останавливается на координате 5.

Вывод:

Заключение

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

Стрельба 1 Максимизация дистанции

問題

思考

回答

Шаги решения:

Реализация на Python:

Пояснение:

Пример:

Заключение:

問題

思考

回答

Понимание задачи

Подход к решению

Детальный алгоритм

Реализация на Python

Пояснения к коду:

Пример работы алгоритма

Заключение

分享這個問答