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 2listy.

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 Truelub 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 Falselub 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.

CJam, 32 30 29 bajtów

q~2@#2b\{)/(W%)1$0=|@]s:~}/:&

Wypróbuj online.

Przypadki testowe

$ cjam pancakes.cjam <<< '2 [1 1 2 2]'; echo
1
$ cjam pancakes.cjam <<< '2 [1 2 2 1]'; echo
0

Jak to działa

q~                            " N, L := eval(input())                                     ";
  2@#2b                       " P := base(2 ** N, 2)                                      ";
       \{                }/   " for F in L:                                               ";
         )/                   "   P := split(P, F + 1)                                    ";
           (W%)               "   T, U, V := P[1:], reverse(P[0])[:-1], reverse(P[-1])[0] ";
               1$0=|          "   V |= U[0]                                               ";
                    @]s:~     "   P := map(eval, str([U, V, T]))                          ";
                           :& " print and(P)                                              ";

Haskell, 92 90 86 84 114 110 99 98

wymóg pełnego programu jest tak denerwujący. Zastanawiam się, dlaczego ktokolwiek miałby tego wymagać.

m(n:s)=all(<1)$foldl(\r@(p:s)n->reverse(take n s)++(p*r!!n):drop n s)[0..n]s
main=readLn>>=print.m

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:

*Main> main
[2,1,1,2,2]
True

Python, 92 bajty

Myślę, że to działa:

s=[1]+[0,0]*input()
for f in input():x=f*2;s[0]=s[x]=s[0]|s[x];s[:x]=s[x-1::-1]
print all(s)

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:

$ python pancakes.py
2
1, 1, 2, 2
True

Python 2: 75

Uproszczenie rozwiązania grc i feersum.

n,b=input()
s=[1]+[0]*n
for x in b:s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

Zapisywanie stanu syropu 2*n+1krawędzi naleśników jest zbędne, ponieważ dotykające się krawędzie są zawsze takie same. Zamiast tego zapamiętuje stan każdego z n+1połączeń naleśnikowych. W ten sposób przelew syropu jest automatycznie rozliczany.

Jedyną potrzebną aktualizacją jest zachowanie syropu na xskrzyżowaniu, gdy przecina go klapka. Odbywa się to przez lub-ing syrop na okres po klapce 0do x.

Dwukrotne wprowadzenie danych nie wpływa na liczbę znaków.

s=[1]+[0]*input()
for x in input():s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

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 zamiastall() .

Edycja: Naprawiono błąd wprowadzony przez nieudane wypróbowanie różnych metod wprowadzania, które nie zmieniają liczby znaków.

n,F=input()
L=[1]+2*n*[0]
for f in F:f*=2;L[0]=L[f]=L[0]|L[f];L[:f]=L[~-f::-1]
print[1]*2*n<L

Przykładowe wejście / wyjście:

2, [1, 1, 2]

False

APL, 77

∧/⊃{x[1]+←⍺⌷x←⍵⋄(⌽⍺↑x),⍺↓x}/(⌽1+⎕),⊂1,⎕⍴0

Python 2, 107

d=[1]+[0,0]*input()
for i in input():n=2*i;d[:n]=reversed(d[:n]);d[n]=d[n-1]=d[n]|d[n-1]
print(all(d[:-1]))

Haskell, 129 125

t(m:l)=all(any(<1).(\i->foldr(\n->foldr($)[].map(n%))[i]l))[0..m]
n%i|i>n=(i:)|i<n=(n-i:)|1>0=(n:).(0:)
main=readLn>>=print.t

Prawdopodobnie 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ą. foldrskutecznie 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óconym nnaleśnikiem, każdy wpis staje się [n-i]jeśli i<n, [n,0]jeśli i==ni [i]jeśli i>n. Strona, o której mowa, została pokryta wtedy i tylko wtedy, gdy wynikowa lista po wszystkich przerzuceniach zawiera znak 0( any (<1)). allrobi resztę i mainkonwertuje to wszystko na program, który można uruchomić.

Program pobiera dane wejściowe stdinw postaci [n_pancakes, flip1, flip2, flip3, ...]zakończonej nową linią.