Требуется помощь в решении задачи

Question

Требуется помощь в решении задачи

Рейтинг: 1Ответов: 1Опубликовано: 22.04.2023

Сразу скажу: я понимаю, что тут платформа не для решения задач, но я прошу не решить её, а оптимизировать моё решение или привести своё, более логичное.

Ваня с детства мечтал создавать компьютерные игры. Когда он вырос, то смог устроиться в компанию "Игродел" на должность разработчика. Первой задачей было написание генератора уровней к игре "Линия".

Игровой уровень "Линии" предсталяет собой множество из N клеток, расположенных вдоль одной прямой и пронумерованных от 0 до N - 1. Каждая клетка может быть в одном из состояний:

в клетке стоит персонаж
в клетке находится препятствие: змеи, шипы или лава
клетка свободна

Цель главного героя - добраться до клетки с номером N - 1. Единственное, что он может делать - перепрыгивать через непустое множество препятствий (клетка, в которую прыгает персонаж, должна быть свободна). Каждый раз, когда персонаж совершает прыжок, в точке, откуда он прыгнул, равновероятно возникает одно из препятствий.

Сегодня Ваня доделал генератор уровней. И всё было бы хорошо, если не одно "но": Ваня не знает, возможно ли пройти уровень, который получится на выходе генератора. Справиться с этой задачей он не смог. Поэтому Ваня обратился к вам за помощью.

Формат ввода: В первой строке входных данных задано одно целое число: 2 ≤ N ≤ 100000. Во второй строке входных данных задана строка S, состоящая из N символов. Строка S описывает игровое поле и состоит из символов:

'X' - клетка, в которой находится главный герой;
'?' - клетка, в которой находятся змеи;
'#' - клетка, в которой находится шипы;
'*' - клетка, в которой находится лава;
'.' - свободная клетка

Гарантируется, что X всегда есть.

Формат вывода: На первой и единственной строке выведите одно слово:

YES, если существует последовательность прыжков после которой персонаж окажется в клетке с номером N - 1;
NO, иначе.

n = int(input())
s = input()
flag = True
if s[-1] == 'X':
    flag = True
elif s[-1] != '.':
    flag = False
else:
    person = s.find('X')
    pos = 0
    flag = True
    for x in range(person+1,len(s)):
        if s[x] == '.':
            if pos == 0:
                flag = False
                break
            pos = 0
        else:
            pos = 1
if flag:
    print("YES")
else:
    print("NO")

На сайте, на котором я решаю приведено только три примера примера ввода и вывода,на 19 тесте программа выдаёт неверный ответ: Я пробовал много разных вариантов "Линии", но все работает верно, но на 19 неверный ответ. Вот первые три теста:

3; X.. -> NO
4; X#?. -> YES
5; X?.?. -> YES

python олимпиада

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

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

Второе необходимое условие: рядом с X должно быть препятствие. Иначе невозможно сделать первый ход.

Если оба условия выполнены, продолжаем.

Клетку назовём болотом если она...

... рядом с X справа от него;
... справа от X и перед ней пустая клетка.

Пример:

..*X..*...
    --  --
    болотные клетки подчёркнуты

Если болот нет, X выиграл. Иначе из всех болот выберем самое левое. X или уже стоит рядом с болотом (случай 1) или может до него доскакать (потому что оно самое левое). Когда X оказался рядом с болотом, единственный ход - прыжок налево. Он возможен если слева от X где-то есть пустое место. После прыжка болот становится на одно меньше.

Пусть S - число болот, V - число пустых клеток слева от X.

Утверждение: если S ≤ V, то X выигрывает прыгая направо когда возможно и налево в противном случае (упёрся в болото).

Доказывается по индукции по S: оба числа S и V убывают на единицу одновременно. Когда S обнулилось, выигрыш обеспечен.

Утверждение: если S > V, то X проиграл.

Чтобы убрать одно болото (уменьшить S на единицу) нужно уменьшить V на единицу. Когда V обнулится, останется непреодолимое болото.

def win(s):
    if s[-1] == 'X':
        return True
    if s[-1] != '.':
        return False

    i = s.index('X')
    if (i == 0 or s[i - 1] == '.') and s[i + 1] == '.':
        return False

    b = 1 if s[i + 1] == '.' else 0
    for j in range(i + 2, len(s)):
        if s[j - 1] == '.' and s[j] == '.':
            b += 1

    v = s[:i].count('.')

    return b <= v


input()
print('YES' if win(input()) else 'NO')

Требуется помощь в решении задачи

Ответы