Na talerzu masz stos naleśników z kulką syropu na górze, tak grubą, że nie może spływać po bokach. Nie będziesz zadowolony z jedzenia, dopóki obie twarze każdego naleśnika nie dotkną przynajmniej syropu, ale teraz tylko jedna twarz górnego naleśnika ma.
Wiesz, że syrop nigdy nie będzie moczył nawet jednego naleśnika, ale można go przenosić w nieskończoność poprzez bezpośredni kontakt między dwoma naleśnikami. Gdy twarz naleśnika dotknie syropu, uważa się, że jest pokryta syropem na zawsze, i sprawi, że każda twarz bez syropu, która go dotknie, również będzie pokryta syropem. Możliwe jest również przeniesienie syropu do iz górnej części płytki.
Każdą twarz naleśnika powlekasz syropem, wkładając szpatułkę pod jeden lub więcej naleśników i przewracając je na całej długości, dokładnie tak, jak w przypadku sortowania naleśników . (Niestety, ta szpachelka jest odporna na syrop i nie pomaga w rozprowadzaniu syropu poprzez dotykanie twarzy naleśników.) Niestety nie zdajesz sobie sprawy, które twarze naleśników dotknęły syropu, ale pamiętasz dokonane przewrócenia.
Biorąc pod uwagę poprzednie przejęcia, czy możesz określić, czy wszystkie naleśniki są już pokryte syropem?
Wyzwanie
Napisz program, który przyjmuje dodatnią liczbę całkowitą N dla liczby naleśników, oraz listę dodatnich liczb całkowitych (wszystkie <= N) dla wykonanych do tej pory obrotów. Każda liczba na liście reprezentuje liczbę naleśników, które zostały przerzucone. Podaj prawdziwą wartość, jeśli naleśniki są gotowe do powlekania, i wartość fałsz, jeśli nie. ( definicja prawdy / fałszu )
Dane wejściowe powinny pochodzić ze stdin lub wiersza poleceń, a dane wyjściowe powinny przejść do stdout (lub najbliższych alternatyw). W porządku, jeśli dane wejściowe wymagają trochę dodatkowego formatowania: np. [1, 1, 2, 2]
Zamiast 1 1 2 2
listy.
Przykłady
Załóżmy, że N = 2, więc mamy na stole stos dwóch naleśników, zaczynając od syropu na wierzchu.
Jeśli lista jest 1 1 2 2
, oznacza to, że ...
- odwróć górny naleśnik - pokrywając górną powierzchnię dolnego naleśnika
- ponownie odwróć górę - pokrywając oryginalną dolną powierzchnię górnego naleśnika
- odwróć oba - pokrywając talerz
- odwróć oba ponownie - pokrywając oryginalną dolną powierzchnię dolnego naleśnika
Ponieważ wszystkie cztery twarze są pokryte, wynik będzie podobny do True
lub 1
.
Jeśli lista jest 1 2 2 1
, oznacza to, że ...
- odwróć górny naleśnik - pokrywając górną powierzchnię dolnego naleśnika
- odwróć oba - nic nie pokrywając
- odwróć oba ponownie - nic nie pokrywając
- ponownie odwróć górę - pokrywając oryginalną dolną powierzchnię górnego naleśnika
Ponieważ twarz dotykająca płytki jest nadal wolna od syropu, wynik byłby podobny do False
lub 0
.
Notatki
- Lista flip flip może być dowolnie duża i może być pusta, w którym to przypadku wynik jest fałszywy.
- Talerz działa jak nośnik syropu, ale nie ma znaczenia, czy zostanie pokryty, czy nie. (W rzeczywistości każde rozwiązanie typu flip będzie powlekało talerz, ponieważ dotykana powierzchnia naleśnika musi być pokryta, ale niezależnie od tego.)
- Talerza nie można odwrócić.
- Możesz założyć, że te naleśniki to dyski jednostkowe bez stron, o których można mówić, tylko dwie przeciwległe ściany.
Punktacja
To jest golf golfowy. Najkrótsze rozwiązanie w bajtach wygrywa.
Put syrup on the pancakes!
)Odpowiedzi:
CJam,
323029 bajtówWypróbuj online.
Przypadki testowe
Jak to działa
źródło
Haskell,
929086841141109998wymóg pełnego programu jest tak denerwujący. Zastanawiam się, dlaczego ktokolwiek miałby tego wymagać.
to rozwiązanie polega na przedstawieniu stosu naleśników według listy boków, gdy sąsiednie naleśniki mają tę samą stronę. każda strona jest liczbą, a strona jest powlekana, jeśli ma wartość zerową.
Uruchom jako:
źródło
Python, 92 bajty
Myślę, że to działa:
Wykorzystuje listę naleśników (w zestawie talerz), aby zapamiętać, które są pokryte syropem. Naleśniki są odwracane przez odwrócenie części listy, ale każdy syrop jest najpierw przenoszony między górną twarzą a nowo odkrytą twarzą.
Stosowanie:
źródło
Python 2: 75
Uproszczenie rozwiązania grc i feersum.
Zapisywanie stanu syropu
2*n+1
krawędzi naleśników jest zbędne, ponieważ dotykające się krawędzie są zawsze takie same. Zamiast tego zapamiętuje stan każdego zn+1
połączeń naleśnikowych. W ten sposób przelew syropu jest automatycznie rozliczany.Jedyną potrzebną aktualizacją jest zachowanie syropu na
x
skrzyżowaniu, gdy przecina go klapka. Odbywa się to przez lub-ing syrop na okres po klapce0
dox
.Dwukrotne wprowadzenie danych nie wpływa na liczbę znaków.
źródło
Python 2, 93 bajty
Na początku zamierzałem opublikować swoją odpowiedź, ale potem grc opublikował już bardzo podobną minutę wcześniej. Więc próbowałem wymyślić kilka ulepszeń. Jedyne, co mogłem znaleźć, to użyć porównania listy leksykograficznej zamiast
all()
.Edycja: Naprawiono błąd wprowadzony przez nieudane wypróbowanie różnych metod wprowadzania, które nie zmieniają liczby znaków.
Przykładowe wejście / wyjście:
źródło
APL, 77
źródło
Python 2, 107
źródło
Haskell,
129125Prawdopodobnie jeszcze nie w pełni golfowany, ale działa bez manipulowania listą powlekanych boków. Zamiast tego działa wstecz, aby dowiedzieć się, czy dana strona naleśnika kiedykolwiek zetknęła się z czymkolwiek, co na początku było górną stroną.
foldr
skutecznie przegląda listę przewrotek do tyłu, dlatego nie mareverse
.Oto więc algorytm: Mapujemy wszystkie odpowiednie strony (
[0..m]
) i tworzymy listę stron, z których nasza strona dziedziczy syrop na każdym kroku, zaczynając od tyłu: początkowo lista jest tylko[i]
, ale z odwróconymn
naleśnikiem, każdy wpis staje się[n-i]
jeślii<n
,[n,0]
jeślii==n
i[i]
jeślii>n
. Strona, o której mowa, została pokryta wtedy i tylko wtedy, gdy wynikowa lista po wszystkich przerzuceniach zawiera znak0
(any (<1)
).all
robi resztę imain
konwertuje to wszystko na program, który można uruchomić.Program pobiera dane wejściowe
stdin
w postaci[n_pancakes, flip1, flip2, flip3, ...]
zakończonej nową linią.źródło
n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]
zamiastfoldr($)[].map(n%)
mieć(=<<).(%)
, to odwzorowuje wszystkie spadki i dołącza do nich.[0..]
i reprezentować powlekany naleśnik jako 0 zamiast robić niezerowe naleśniki. dzięki!