У вас стопка блинов на тарелке с сиропом сверху, настолько толстым, что он не может стечь по бокам. Вы не будете счастливы есть, пока оба лица каждого блина, по крайней мере, не коснутся сиропа, но сейчас только одно лицо верхнего блина имеет.
Вы знаете, что сироп никогда не пропитается даже одним блинчиком, но его можно бесконечно переносить при непосредственном контакте между двумя блинами. После того, как лицо блина коснулось сиропа, оно считается покрытым сиропом навсегда, и любое лицо, не покрытое сиропом, будет также покрыто сиропом. Также возможно перенести сироп на верхнюю сторону тарелки.
Вы продолжаете покрывать каждое лицо блина сиропом, вставляя лопаточку ниже одного или более блинов и переворачивая их повсюду, точно так же, как это делается при сортировке блинов . (К сожалению, эта лопаточка устойчива к сиропу и не помогает распределять сироп, касаясь лица блина.) К сожалению, вы теряете след того, какие лица блина коснулись сиропа, но вы помните, что вы сделали сальто.
Учитывая ваши прошлые сальто, можете ли вы определить, все ли ваши блины покрыты сиропом?
Вызов
Напишите программу, которая принимает положительное целое число N для количества блинов и список положительных целых чисел (все <= N) для сальто, которое вы сделали до сих пор. Каждый номер в списке представляет количество блинов, которые были перевернуты. Выведите истинное значение, если блины уже покрыты оболочкой, и ложное значение, если нет. ( правдивое / ложное определение )
Входные данные должны поступать из stdin или из командной строки, а выходные данные - из stdout (или ближайших альтернатив). Хорошо, если ваш ввод требует небольшого дополнительного форматирования: например, [1, 1, 2, 2]
вместо 1 1 2 2
списка.
Примеры
Предположим, что N = 2, поэтому у нас на тарелке два блина, начиная с сиропа сверху.
Если список есть 1 1 2 2
, это означает, что мы ...
- перевернуть верхний блин - покрытие верхней грани нижнего блина
- переверните верх снова - покрытие оригинальной нижней поверхности верхнего блина
- перевернуть оба - покрытие пластины
- переверните оба снова - покрытие оригинальной нижней поверхности нижнего блина
Поскольку все четыре грани имеют покрытие, на выходе будет что-то вроде True
или 1
.
Если список есть 1 2 2 1
, это означает, что мы ...
- перевернуть верхний блин - покрытие верхней грани нижнего блина
- перевернуть оба - покрытие ничего
- переверните оба снова - ничего не покрывая
- переверните верх снова - покрытие оригинальной нижней поверхности верхнего блина
Поскольку лицо, касающееся пластины, по-прежнему не содержит сиропа, результат будет примерно таким False
или 0
.
Заметки
- Флип-лист может быть сколь угодно большим и может быть пустым, и в этом случае результат будет ложным.
- Пластина действует как носитель сиропа, но это не имеет значения, покрыто ли это или нет. (В действительности любой флип - решение будет покрывать пластины , потому что блин лицо это касается должно быть нанесено покрытие, но независимо.)
- Тарелка не может быть перевернута.
- Вы можете предположить, что эти блины представляют собой единичные диски без сторон, о которых можно говорить, только две противоположные стороны.
счет
Это код-гольф. Самое короткое решение в байтах побеждает.
Put syrup on the pancakes!
Ответы:
CJam,
323029 байтПопробуйте онлайн.
Контрольные примеры
Как это работает
источник
Haskell,
929086841141109998требование полной программы так раздражает. Интересно, зачем кому-то это нужно?
это решение работает путем представления стопки блинов списком сторон, когда соседние блины имеют одну и ту же сторону. каждая сторона является числом, и сторона покрыта, если она имеет нулевое значение.
беги как:
источник
Python, 92 байта
Я думаю, что это работает:
Он использует список граней блинов (включая пластину), чтобы запомнить, какие из них покрыты сиропом. Блины переворачивают, переворачивая часть списка, но любой сироп сначала переносится между верхним лицом и вновь открывшимся лицом.
Использование:
источник
Питон 2: 75
Упрощение решения GRC и Feersum.
Хранение состояния сиропа
2*n+1
краев блина является излишним, потому что касание краев всегда одинаково. Вместо этого он запоминает состояние каждого изn+1
блинов. Таким образом, перенос сиропа учитывается автоматически.Единственное необходимое обновление - сохранить сироп на
x
стыке, когда переворачивает его. Это делается путем добавления сиропа после переворачивания0
вx
.Взятие ввода дважды не влияет на количество символов.
источник
Python 2, 93 байта
Сначала я собирался опубликовать свой ответ, но затем grc уже опубликовал очень похожий за минуту до этого. Поэтому я попытался придумать некоторые улучшения. Единственное, что я смог найти, - это использовать сравнение лексикографического списка вместо
all()
.Редактировать: Исправлена ошибка, возникающая из-за неудачной попытки использования различных методов ввода, которые не изменяли количество символов.
Пример ввода / вывода:
источник
APL, 77
источник
Python 2, 107
источник
Хаскелл,
129125Вероятно, еще не полностью игра в гольф, но это работает без манипулирования списком покрытых сторон. Вместо этого он работает в обратном направлении, чтобы выяснить, вступала ли данная сторона данного блина в контакт с чем-либо, что было верхней стороной в начале.
foldr
эффективно пересекает список сальто назад, поэтому нетreverse
.Итак, вот алгоритм: мы отображаем все соответствующие стороны (
[0..m]
) и составляем список сторон, от которых наша сторона наследует сироп на каждом шаге, начиная со спины: изначально список просто[i]
, но с переворотомn
блинов, каждая запись становится[n-i]
еслиi<n
,[n,0]
еслиi==n
и[i]
еслиi>n
. Рассматриваемая сторона была покрыта тогда и только тогда, когда результирующий список после всех переворотов содержит0
(any (<1)
).all
делает все остальное иmain
преобразует все это в работоспособную программу.Программа получает свой ввод
stdin
в виде[n_pancakes, flip1, flip2, flip3, ...]
, оканчивающемся новой строкой.источник
n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]
вместоfoldr($)[].map(n%)
have(=<<).(%)
, это отобразит все наследования и объединит их.[0..]
и представлять блины с покрытием как 0 вместо того, чтобы делать блины с ненулевым покрытием. Благодарность!