Discussion :

[progz_du_dimanche]

Bonjour à tous,

Je suis en train d'essayer de faire l'exercice des montagnes russes sur codingames. J'ai codé une solution qui me permet de passer tous les tests sauf le dernier. Pour comprendre comment traiter un grand nombre de données, je suis allé voir une solution sur google. Et je ne comprends pas en quoi cette solution est plus efficace que la mienne. Si quelqu'un pouvait m'expliquer ?

Mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
 
l, c, n = [int(i) for i in input().split()]
tab=[]
for i in range(n):
    pi = int(input())
    tab.append(pi)
# Write an answer using print
# To debug: print("Debug messages...", file=sys.stderr, flush=True)
dirham=0
for i in range(c):
    remplissage=0
    for j in range(len(tab)): 
        x=int(tab[0])
        remplissage+=x    
        if remplissage>l:
            break
        tab.remove(x) 
        tab.append(x)
        dirham+=x
print(dirham)

La solution que j'ai trouvé (et testé bien entendu) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
places, rides, group_nm = map(int, input().split())
# Gets groups as list of integers
groups = list(map(int, [input() for _ in range(group_nm)]))
 
# Initialize dicts
profits = {}
groups_after = {}
 
for i in range(group_nm):
    # Starting values
    current_index = i
    profits[i] = 0
 
    while True:
        # Group that's about to ride
        next_grp = groups[current_index]
 
        # Go out of loop when no more places are available
        if profits[i] + next_grp > places:
            break
 
        # Increase profits by the number of people in group
        profits[i] += next_grp
 
        # Increment the index
        current_index += 1
 
        # Reset the index if we reached the end of the list
        current_index = 0 if current_index == group_nm else current_index
 
        # We passed through the whole list yet there are more places are available
        if current_index == i:
            break
 
    # Once done, we want to save the index of the group that needs to ride next
    groups_after[i] = current_index
 
# Initialize total and reset current index
total = 0
current_index = 0
 
# Sum up the profits
for i in range(rides):
    total += profits[current_index]
    current_index = groups_after[current_index]
 
# Solution, yay!
print(total)

Evidemment ma solution est moins gracieuse et peut être amélioré. Mais l'ensemble du fonctionnement me semble identique. Si quelqu'un peut éclairer ma lanterne.

Merci d'avance.

[wiztricks]

Salut,

Déjà à cause des lignes 18 et 19:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
        tab.remove(x) 
        tab.append(x)

après vous avez la ligne 14: x = int(tab[0]). tab[0] est déjà un entier.

Enfin relisez ces codes, ce ne sont pas les mêmes algorithmes (ou en tous cas, s'ils produisent le même résultat, il ne se lisent pas de la même façon).

- W

[Sve@r]

Bonjour

Je l'ai fait il y a pas mal de temps cet exercice. Le souci de la solution élémentaire c'est qu'elle est trop longue pour gérer le dernier exercice qui contient (il me semble) 1000000 de personnes.
Je l'ai résolu en utilisant les modulos. Si un manège peut accueillir (par exemple) 150 personnes et qu'on doit en faire passer 305, les 300 premières ne comptent pas...