Олимпиаданая задача " Игра Стрельба-1"

Question

Олимпиаданая задача " Игра Стрельба-1"

sadsawd Ученик (60), на голосовании 6 дней назад

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

В игре есть возможность убрать одно любое препятствие, чтобы персонаж дошёл как можно дальше. Таким образом требуется помочь Пете определить, какое препятствие выгоднее всего убрать, чтобы персонаж прошёл как можно дальше.

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

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

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

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

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

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

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

Примечание:

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

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

3) Когда персонаж не доходит до конца (упирается в препятствие, которое не успел уничтожить), то считается, что он прошёл ровно такое расстояние, на координате которой стояло препятствие (если персонаж закончил игру на препятствии по координате 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 ОЗ, значит оно не может быть уничтожено, но может быть убрано в самом начале игры (есть возможность убрать одно препятствие), таким образом, персонаж сможет дойти по оси до самого конца.

Answer 1

Для решения этой задачи, давайте разобьем процесс на шаги.

1. **Чтение входных данных**: Получим длину оси, количество препятствий и их координаты с очками здоровья.

2. **Моделирование движения персонажа**:
- Персонаж начинается с координаты 0 и движется с постоянной скоростью 1 клетка в секунду.
- Он может стрелять на расстоянии 4 клетки и наносить 2 единицы урона в секунду.

3. **Определение максимального расстояния**:
- Персонаж будет двигаться до ближайшего препятствия и атаковать его.
- Если он сможет уничтожить препятствие, он продолжает движение.
- Если препятствие не может быть уничтожено, проверяем, можем ли мы убрать это препятствие и тем самым пройти дальше.

4. **Сравнение**:
- Для каждого препятствия проверяем, что произойдет, если его убрать.
- Сравниваем максимальные расстояния, которые можно пройти, и запоминаем координату препятствия, которое выгоднее всего убрать.

5. **Вывод результата**:
- Если персонаж сможет пройти всю длину оси без удаления препятствий, выводим `0` и длину оси.
- В противном случае, выводим координату удаляемого препятствия и максимальное расстояние, которое можно пройти.

Вот пример кода на Python, который реализует описанный алгоритм:

```python
def max_distance(L, N, obstacles):
# Сначала сортируем препятствия по координатам
obstacles.sort()

def can_destroy(obstacle_index):
position = 0
while position = L:
return L # Дошли до конца
return position # Упёрлись в препятствие

max_dist = 0
best_obstacle = 0

# Сначала проверим, можем ли пройти без удаления
max_dist = can_destroy(0)

for i in range(N):
# Проверяем, если удалить препятствие i
new_max_dist = can_destroy(i + 1) # Пропускаем i-ое препятствие
if new_max_dist > max_dist or (new_max_dist == max_dist and obstacles[i][0] > best_obstacle):
max_dist = new_max_dist
best_obstacle = obstacles[i][0]

return best_obstacle, max_dist

# Чтение входных данных
L = int(input())
N = int(input())
obstacles = [tuple(map(int, input().split())) for _ in range(N)]

# Получаем результат
best_obstacle, max_distance = max_distance(L, N, obstacles)

# Вывод результата
print(best_obstacle)
print(max_distance)
```

### Пояснение к коду:
- Функция `max_distance` принимает длину оси `L`, количество препятствий `N` и список `obstacles`, содержащий координаты и здоровье препятствий.
- Внутренняя функция `can_destroy` моделирует движение персонажа, учитывая возможность уничтожения препятствий.
- Основной цикл проверяет, как далеко может зайти персонаж, если убрать каждое препятствие, и обновляет максимальное расстояние и координату удаляемого препятствия, если это выгодно.
- В конце, выводим результаты.

Answer 2

 def solve(): 
    l = int(input()) 
    n = int(input()) 
    obstacles = [] 
    for _ in range(n): 
        obstacles.append(list(map(int, input().split()))) 
 
    max_distance = 0 
    best_obstacle_to_remove = 0 
 
    for obstacle_to_remove_index in range(-1, n): 
         
        current_obstacles = [] 
        for i, obs in enumerate(obstacles): 
             if i != obstacle_to_remove_index: 
                 current_obstacles.append(obs) 
                 
        current_obstacles.sort(key = lambda x: x[0]) 
         
        position = 0 
         
         
         
         
         
         
         
         
        while position < l: 
             
           
            
             
             
             
             
             
             
            obstacle_hit = None 
             
            for obs in current_obstacles: 
                if obs[0] > position and obs[0] <= position +4 : 
                    
                    obstacle_hit = obs 
                    break 
             
             
            if obstacle_hit != None: 
                 
                 
                 
                if obstacle_hit[0] in [x[0] for x in current_obstacles]: 
                     
                   
                     
                     
                    
                     
                     
                     
                   
                     
                     
                    break 
             
                 
             
             
             
             
            position+= 1 
                 
         
        if position > max_distance: 
             max_distance = position 
             if obstacle_to_remove_index != -1: 
                 best_obstacle_to_remove = obstacles[obstacle_to_remove_