Vous avez une pile de crêpes sur une assiette avec une boule de sirop sur le dessus tellement épaisse qu’elle ne peut pas couler sur les côtés. Vous ne serez pas heureux de manger jusqu'à ce que les deux faces de chaque crêpe aient au moins touché le sirop, mais à l'heure actuelle, une seule face de la crêpe supérieure l'a.

Vous savez que le sirop ne pénètrera jamais dans un seul pancake, mais il peut être transféré indéfiniment via un contact direct entre deux pancakes. Une fois qu'une face d'une crêpe a touché le sirop, elle est considérée comme étant recouverte de sirop pour toujours et fera en sorte que toute face non enrobée de sirop qui la touche touche également l'enrobage. Il est également possible de transférer du sirop vers le haut et vers le haut de la plaque.

Pour recouvrir chaque face de crêpes de sirop, insérez une spatule sous un ou plusieurs crêpes et renversez-les, exactement comme pour le tri des crêpes . (Malheureusement, cette spatule est résistante au sirop et ne permet pas de le distribuer en touchant les faces des pancakes.) Malheureusement, vous ne savez pas quelles faces des pancakes ont touché le sirop, mais vous vous souvenez des retournements que vous avez faits.

Compte tenu de votre passé, pouvez-vous déterminer si vos crêpes sont toutes encore enrobées de sirop?

Défi

Ecrivez un programme qui prend un entier positif N pour le nombre de crêpes et une liste d’entiers positifs (tous <= N) pour les retournements effectués jusqu’à présent. Chaque nombre dans la liste représente le nombre de crêpes retournées. Affiche une valeur de vérité si les crêpes sont cuites et une valeur de fausseté sinon. ( définition de la vérité ou de la fausseté )

L'entrée doit provenir de stdin ou de la ligne de commande et la sortie doit aller à stdout (ou aux alternatives les plus proches). C'est bien si votre entrée nécessite un formatage supplémentaire: par exemple, [1, 1, 2, 2]au lieu de 1 1 2 2pour la liste.

Exemples

Supposons que N = 2, nous avons donc une pile de deux crêpes sur une assiette, en commençant par le sirop.

Si la liste est 1 1 2 2, cela signifie que nous ...

• retourner la crêpe supérieure - recouvrir la face supérieure de la crêpe inférieure
• retourner le haut à nouveau - enduire la face inférieure originale de la crêpe supérieure
• retourner les deux - recouvrir la plaque
• retournez les deux à nouveau - en recouvrant la face inférieure originale de la crêpe inférieure

Puisque les quatre faces sont revêtues, la sortie serait quelque chose comme Trueou 1.

Si la liste est 1 2 2 1, cela signifie que nous ...

• retourner la crêpe supérieure - recouvrir la face supérieure de la crêpe inférieure
• retourner les deux - rien ne recouvre
• retourner à nouveau les deux - rien ne recouvre
• retourner le haut à nouveau - enduire la face inférieure originale de la crêpe supérieure

Puisque le visage touchant la plaque est toujours exempt de sirop, le résultat serait quelque chose comme Falseou 0.

Remarques

• La liste de retournement peut être arbitrairement longue et vide, auquel cas la sortie est faussée.
• La plaque sert de support à sirop mais peu importe qu’elle soit enrobée ou non. (En fait , toute solution chiquenaude sera manteau de la plaque parce que le visage de crêpe il touche doit être revêtue, mais peu importe.)
• La plaque ne peut pas être retournée.
• Vous pouvez supposer que ces crêpes sont des disques unitaires sans côtés à proprement parler, seulement deux faces opposées.

Notation

C'est du code-golf. La solution la plus courte en octets gagne.

CJam, 32 30 29 octets

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

Essayez-le en ligne.

Cas de test

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

Comment ça marche

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

l'exigence d'un programme complet est tellement ennuyeuse. Je me demande pourquoi quelqu'un aurait besoin de cela.

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

cette solution fonctionne en représentant le tas de crêpes par une liste des côtés, lorsque des crêpes adjacentes partagent le même côté. chaque côté est un nombre et un côté est revêtu s'il a une valeur zéro.

courir comme:

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

Python, 92 octets

Je pense que cela fonctionne:

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)

Il utilise une liste de faces de crêpes (assiette incluse) pour rappeler celles qui sont enrobées de sirop. Les pancakes sont retournés en inversant une partie de la liste, mais tout sirop est d'abord transféré entre la face supérieure et le visage nouvellement révélé.

Usage:

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

Python 2: 75

Une simplification de la solution de grc et 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)

Le stockage de l’état sirop des 2*n+1bords de la crêpe est redondant car les bords touchant sont toujours les mêmes. Cela rappelle l’état de chacune des n+1jonctions des pancakes. De cette façon, le transfert de sirop est automatiquement comptabilisé.

La seule mise à jour nécessaire consiste à conserver le sirop à la xjonction lorsqu'un flip le coupe. Ceci est fait en ornant le sirop post-retournement 0dansx .

La saisie deux fois n’affecte pas le nombre de caractères.

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

Python 2, 93 octets

Au début, j'allais publier ma réponse, mais le groupe en avait déjà posté une très similaire une minute auparavant. J'ai donc essayé de proposer des améliorations. Le seul que j'ai pu trouver est d'utiliser une comparaison de liste lexicographique au lieu deall() .

Éditer: Correction d'une erreur introduite en essayant sans succès différentes méthodes de saisie qui ne changeait pas le nombre de caractères.

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

Échantillon entrée / sortie:

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

Probablement pas encore complètement joué au golf, mais cela fonctionne sans manipuler une liste de côtés revêtus. Au lieu de cela, il fait son chemin en arrière pour déterminer si un côté donné d’une crêpe donnée est jamais entré en contact avec tout ce qui était au sommet au début. foldrparcourt effectivement la liste des retournements, il n’ya donc pas dereverse .

Voici donc l'algorithme: Nous cartographions tous les côtés pertinents ( [0..m]) et faisons une liste des côtés dont notre côté hérite du sirop à chaque étape, en commençant par le dos: initialement, la liste est juste [i], mais avec un revers de npancakes, chaque entrée devient [n-i]si i<n, [n,0]si i==net [i]si i>n. Le côté en question a été revêtu si et seulement si la liste résultante après tous les retournements contient un 0( any (<1)). allfait le reste, etmain convertit tout cela en un programme exécutable.

Le programme prend son entrée stdinsous forme de [n_pancakes, flip1, flip2, flip3, ...], terminé par une nouvelle ligne.