La revanche des pancakes

Bonjour à tous !

Je suis en train de m'amuser sur les problèmes donnés par la Google Code Jam. Je viens tout juste de commencer, j'en suis au Problème B : La revanche des pancakes, donner lors des phases de qualification qui s'est déroulé le 8 avril.

J'ai pensé que ça serait intéressant de traduire ici le problème pour ceux qui veulent réfléchir sur ce projet et qui sont fâchés avec l'anglais ou pour ceux qui ne connaissaient pas.

Vous êtes invités à poster votre solution (et explications) et/ou des conseils pour les membres les plus expérimentés.

Problème

La Maison Des Pancakes vient d'élaborer une nouvelle sorte de pancake ! Il possède une face souriante fait de pépite de chocolat (face contente). Sur l'autre face il n'y a rien (face vide).

Tu es le responsable de l'équipe des vendeurs, et la cuisine vient de te donner une pile de pancakes que tu dois servir à un client. Comme tout bon serveur de pancake, tu as une vision à rayon X des pancakes et tu peut voir chaque pancakes de la pile et savoir si ils ont leur face contente en haut ou leur face vide en haut. Tu penses que le client serait plus content si chaque pancakes à sa face heureuse vers le haut lorsque tu leurs sert.

Tu sais faire la manœuvre suivante : soulever un certain nombre de pancakes (éventuellement tous) à partir du haut de la pile, retourner le groupe de pancakes que tu viens de soulever, et les reposer sur les autres pancakes que tu n'as pas retournés. Quand tu retournes le groupe de pancakes tu les retournes tous en un seul mouvement, tu ne les retournes pas un par un. Formellement : si on numérote les pancakes $1, 2, ..., N$ de celui au dessus à celui en dessous. Tu choisis les $i$ premiers pancakes à retourner. Après les avoir retournés la pile sera : $i, i-1, ..., 2, 1, i+1, i+2, ..., N$. Les pancakes $1, 2, ..., i$ sont alors positionner avec leurs face opposé vers le haut (par rapport au début), tandis que les pancakes $i+1, i+2, ..., N$ ont leur même face vers le haut.

Par exemple, appelons la face contente '+' et la face vide '-'. Considérons cette pile de pancakes (en partant du haut): $--+-$. Une bonne façon de faire la manœuvre serai de prendre les 3 premiers pancakes ($--+$) de les retourner tous un seul mouvement ($-++$) et de les reposer sur la pile de pancakes (qui elle n'a pas changée). La nouvelle pile serai alors : $-++-$. Un autre façon valide de faire serai de prendre et de retourner le premier, ou les deux premiers, ou les quatre premiers. En revanche, prendre le deuxième pancake directement pour le retourner ne serai pas bon. Tu peux prendre uniquement une groupe de pancakes à partir du haut de la pile.

Input

Le première ligne de saisis donne le nombre de cas à tester, $T$. Les $T$ lignes suivantes correspondent à chaque cas. Un cas consiste en une chaîne de caractère $S$ constitué uniquement de $+$ (face content du pancakes vers la haut) et de $-$ (face vide de pancake vers le haut). La chaîne de caractères, lorsqu'on la lit de gauche à droite représente la pile lorsqu'on la regarde du haut vers la bas.

Output

Pour chaque cas testés, la sortie contient la ligne suivante : Case #x : y. Où x désigne le numéro du cas testé (on commence par le cas n°1) et $y$ le nombre minimum que tu dois exécuter la manœuvre pour voir tous les pancakes avec leurs face content vers le haut.

Limites

$1 \le T \le 100$ Chaque caractère de $S$ doit être soit $+$ soit $+$

Exemple

1
2
3
4
5
6
7

Input        Output
5            Case #1: 1
-            Case #2: 1
-+           Case #3: 2
+-           Case #4: 0
+++          Case #5: 3
--+-

Cas #1 : tu dois effectuer la manœuvre 1 fois, retourner le premier pancakes

Cas #2 : Tu dois effectuer la manœuvre 2 fois, retourner le premier pancake.

Cas #3 : Tu dois effectuer la manœuvre 2 fois. Une solution optimale serai de retourner le premier pancake pour avoir la pile suivante : $--$. Puis de retourner cette pile pour avoir la pile suivante : $++$. NB : On ne peut pas retourner la pancakes $-$ directement, il n'est pas au dessus de la pile, or il faut choisir un groupe de pancakes à partir du dessus de la pile.

Cas #4 : Tu ne dois pas effectuer la moindre manœuvre.

Cas #5 : Une bonne façon de faire serai de retourner la pile entière pour avoir : $+-++$. Puis de retourner le premiers pancakes puis de retourner les 2 premiers.

Fichier de test

Vous pouvez vous rendre sur la page du problème, si vous cliquez sur les boutons "Solve B-small" ou "Solve B-large" vous pouvez accéder à un fichier pour tester votre code.

PS : L'anglais et moi ne sommes pas forcement amis, j'ai essayé, de faire de mon mieux pour traduire le problème, mais si vous voyez des erreurs (de phrase mal dîtes ou de français) n'hésitez pas, si vous le souhaitez, me le signaler ou à corriger directement (pour le staff)

Heureusement que je me suis fait mes propres pancakes alors, je suis sûr qu'ils sont bons au moins

Sinon j'ai fait un petit programme :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

T = int(input())

for i in range(T):
    S = input()
    cnt = 0 # Compteur de manoeuvre
    same_face = 0
    k = 0

    while same_face != len(S) :
        if '-' in S:
            if S[k] == '+':
                cha = '-'
            else:
                cha = '+'


            if S[k:].find(cha) == -1: # Si le reste de la pile (pas encore trié) est bien trié
                same_face = len(S)
                if S[k] == '-':
                    cnt = cnt + 1
            else: # Si la pile n'est pas triée : s'il il y a un '+' après un '-' (ou inversement)
                same_face += S[k:].find(cha) 
                k += S[k:].find(cha) # On recupère l'indice jusqu'au quel les pancakes sont triés
                cnt = cnt + 1 
        else:
            same_face = len(S)

    else: 
        print("Case #"+str(i)+": "+str(cnt))

En gros je prend les $i$ premiers pancakes que je retourne (enfin je les retourne pas vraiment dans le programme), j'augment le compteur de manœuvre. Puis après je prend les $j$ pancakes de la même face à partir de $i$, je les retourne, etc. Quand tous les pancakes sont retournés j'affiche le résultat.

J'en suis pas satisfait à 100%, faudra que je le retravaille pour voir si je peux améliorer des choses. Et je viens tout juste de me remettre au Python, je vous préviens le début à été plutôt difficile

En attendant si vous avez des conseils à me donner ils sont les bienvenus !