Задача про сортировку вагонов на языке Python 3.
Ограничение по времени работы программы: 1 секунда
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
ВХОДНЫЕ ДАННЫЕ
Первая строка входных данных содержит число N — количество вагонов в поезде (1≤N≤100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.
ВЫХОДНЫЕ ДАННЫЕ
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.
Я написал программу, и она даже работает. Только она проходит лишь 52 из 65 тестов. Уважаемые знатоки, скажите, что с ней не так. Допускаю, что мог совершить глупую ошибку, писал ночью.
l = int(input())
s = list(map(int, input().split()))
tup = [] # тупик
tr2 = [] # путь 2
for i in range(l):
if s[i] > 1:
if len(tr2) != 0 and s[i] == tr2[-1] + 1:
tr2.append(s[i])
continue
else:
tup.append(s[i])
continue
elif s[i] == 1:
tr2.append(s[i])
tup.reverse()
tr2 += tup
if sorted(tr2) == tr2:
print('YES')
else:
print('NO')
Ограничение по времени работы программы: 1 секунда
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
ВХОДНЫЕ ДАННЫЕ
Первая строка входных данных содержит число N — количество вагонов в поезде (1≤N≤100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.
ВЫХОДНЫЕ ДАННЫЕ
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.
Я написал программу, и она даже работает. Только она проходит лишь 52 из 65 тестов. Уважаемые знатоки, скажите, что с ней не так. Допускаю, что мог совершить глупую ошибку, писал ночью.
l = int(input())
s = list(map(int, input().split()))
tup = [] # тупик
tr2 = [] # путь 2
for i in range(l):
if s[i] > 1:
if len(tr2) != 0 and s[i] == tr2[-1] + 1:
tr2.append(s[i])
continue
else:
tup.append(s[i])
continue
elif s[i] == 1:
tr2.append(s[i])
tup.reverse()
tr2 += tup
if sorted(tr2) == tr2:
print('YES')
else:
print('NO')
More Questions From This User See All
Answers & Comments
Verified answer
Ваше решение не учитывает возможности выезда части вагонов из тупика, все вагоны, попавшие в тупик, почему-то могут выехать из него только в конце. В итоге неверный ответ, например, на тесте 2 1 3 - выдаст NO вместо YES (Нужная последовательность действий: 2 - в тупик, 1 - через тупик на путь 2, 2 - из тупика на путь 2, 3 - через тупик на путь 2).Вот что-то, приближенное к вашему решению, рассматривающее и эту возможность:
l = int(input())
s = list(map(int, input().split()))
tup = [0] # тупик
tr2 = [0] # путь 2
for i in range(l):
while tup[-1] == tr2[-1] + 1:
tr2.append(tup[-1])
tup.pop()
if s[i] == tr2[-1] + 1:
tr2.append(s[i])
else:
tup.append(s[i])
while tup[-1] == tr2[-1] + 1:
tr2.append(tup[-1])
tup.pop()
if tr2[-1] == l:
print('YES')
else:
print('NO')