Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите решить задачу python

Гоги Сатору Ученик (121), открыт 2 недели назад
Напишите программу, которая принимает на вход целое число n - количество раундов игры Антона, а затем n строк, в каждой из которых находятся последовательности целых чисел, записанных через пробел - стороны кубиков, которые выстроены в ряд. Программа должна выводить для каждого раунда стороны кубиков, записанные через пробел, для получившейся пирамиды, если ее можно сделать, руководствуясь правилами игры; или слово НЕТ, если построение устойчивой пирамиды невозможно.

Формат ввода
Целое число n - количество раундов игры n строк со сторонами кубиков в ряду, записанными через пробел

Формат вывода
Для каждого раунда игры - стороны кубиков в получившейся пирамиде, записанные через пробел (основание - первое число, вершина - последнее), либо строка НЕТ, если построение устойчивой пирамиды невозможно

Пример 1
Ввод Вывод
2
4 3 2 1 3 4
1 3 2
4 4 3 3 2 1
НЕТ
Пример 2
Ввод Вывод
3
10 5 4 3 5 7 6
1
3 2 1 3 2 1
НЕТ
1
НЕТ
Дополнен 2 недели назад
Далеко не все дети умеют себя развлекать самостоятельно, но у пятилетнего Антона такой проблемы нет. Например, сегодня он придумал новую игру, в которую можно играть в одиночку.

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

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

Напишите программу, которая принимает на вход целое число n - количество раундов игры Антона, а затем n строк, в каждой из которых находятся последовательности целых чисел, записанных через пробел - стороны кубиков, которые выстроены в ряд. Программа должна выводить для каждого раунда стороны кубиков, записанные через пробел, для получившейся пирамиды, если ее можно сделать, руководствуясь правилами игры; или слово НЕТ, если построение устойчивой пирамиды невозможно.

Формат ввода
Целое число n - количество раундов игры n строк со сторонами кубиков в ряду, записанными через пробел

Формат вывода
Для каждого раунда игры - стороны кубиков в получившейся пирамиде, записанные через пробел (основание - первое число, вершина - последнее), либо строка НЕТ, если построение устойчивой пирамиды невозможно

Пример 1
Ввод Вывод
2
4 3 2 1 3 4
1 3 2
4 4 3 3 2 1
НЕТ
Пример 2
Ввод Вывод
3
10 5 4 3 5 7 6
1
3 2 1 3 2 1
НЕТ
1
НЕТ
Дополнен 2 недели назад
2 ответа
Анатолий Зяблин Просветленный (31890) 2 недели назад
Вот
 def can_build_pyramid(cube_sides): 
from collections import Counter

# Подсчитываем количество каждой стороны
counts = Counter(cube_sides)

# Сортируем уникальные стороны в порядке убывания
unique_sides = sorted(counts.keys(), reverse=True)

pyramid = []

# Проверяем возможность построения пирамиды
for side in unique_sides:
count = counts[side]
if count > 0:
# Добавляем текущую сторону в пирамиду
pyramid.append(side)
# Уменьшаем количество для следующего уровня
counts[side] -= 1

# Если есть больше одного кубика на этом уровне, добавляем их на следующий уровень
if counts[side] > 0:
# Добавляем столько кубиков, сколько осталось
for _ in range(counts[side]):
pyramid.append(side)
counts[side] = 0

# Проверяем, удалось ли построить устойчивую пирамиду
if len(pyramid) == 0 or pyramid[-1] != unique_sides[-1]:
return "НЕТ"

return ' '.join(map(str, pyramid))

# Чтение данных
n = int(input("Введите количество раундов: "))
results = []

for _ in range(n):
cube_sides = list(map(int, input().split()))
result = can_build_pyramid(cube_sides)
results.append(result)

# Вывод результатов
for res in results:
print(res)
Гоги СаторуУченик (121) 2 недели назад
неправильно
Гоги Сатору, ты даже не потрудился привести полное условие задачи. Тут никто и в душе не знает, что такое "игра Антона". Поэтому ты закономерно получил один ответ от тролля и один - от нейросетевого болванчика.
Cogni Просветленный (40132) 2 недели назад
 def solve_pyramids(n, rounds): 
from functools import lru_cache

results = []

for cubes in rounds:
cubes = list(map(int, cubes.split()))
length = len(cubes)

@lru_cache(maxsize=None)
def backtrack(left, right, last):
if left > right:
return []
options = []
# Выбор с начала
if cubes[left] <= last:
res = backtrack(left + 1, right, cubes[left])
if res is not None:
return [cubes[left]] + res
# Выбор с конца
if cubes[right] <= last:
res = backtrack(left, right - 1, cubes[right])
if res is not None:
return [cubes[right]] + res
return None

# Начинаем с бесконечного значения, чтобы первый кубик мог быть любым
pyramid = backtrack(0, length - 1, float('inf'))
if pyramid:
results.append(' '.join(map(str, pyramid)))
else:
results.append("НЕТ")

return results

# Чтение входных данных
if __name__ == "__main__":
n = int(input())
rounds = [input().strip() for _ in range(n)]
results = solve_pyramids(n, rounds)
for res in results:
print(res)
Похожие вопросы