Bonjour, j'ai actuellement un probleme pour resoudre un exercice de France IOI, ma recherche est trop lente.
Voici l'enonce :
Des affiches rectangulaires sont collées les unes après les autres sur un mur. Toutes les affiches ont la même largeur. On vous donne la hauteur Hi de chacune de ces affiches, dans l'ordre dans lequel elles sont collées. Le coin supérieur gauche de chaque affiche est toujours placé exactement sur le coin supérieur gauche du mur, et ce dernier est toujours plus grand que les affiches. Régulièrement, entre deux collages d'affiches, on vous demande d'indiquer combien d'affiches, parmi celles déjà collées, sont au moins en partie visibles, c'est à dire qu'une surface non nulle n'a été recouverte par aucune affiche collée depuis.
Limites de temps et de mémoire (Python)
Temps : 2 s sur une machine à 1 GHz.
Mémoire : 32 000 ko.
Contraintes
1 <= nbRequetes <= 100 000, où nbRequetes est le nombre de requêtes, une requête pouvant correspondre au collage d'une affiche ou bien à une question sur le nombre d'affiches visibles.
1 <= hauteuri <= 1 000 000, où hauteuri est la hauteur d'une affiche
Entrée
La première ligne de l'entrée est constituée d'un unique entier :nbRequetes
Chacune des nbRequetes lignes suivantes commence par un caractère pouvant être 'Q' ou 'C'. Un caractère 'Q' correspond à la question : "Combien d'affiches sont actuellement visibles?". Un caractère 'C' est suivi d'un entier hauteur et correspond au collage d'une affiche de hauteur hauteur.
Sortie
La sortie de votre programme doit correspondre aux réponses aux questions données en entrée, dans l'ordre dans lequel elles apparaissent.
Et voici ma réponse, mais trop lente :
from bisect import bisect_right
def search(alist, item):
i = bisect_right(alist, item)
return i
requetes = int(input())
tab = []
for i in range(requetes):
requete = input()
if requete == "Q":
print (len(tab))
else :
taille = int(requete[2:])
if len(tab) == 0 :
tab.append(taille)
else :
index_affiche = search(tab, taille)
if index_affiche == len(tab):
tab = [taille]
else :
tab.insert(index_affiche, taille)
tab = tab[index_affiche:]
je ne comprends pas comment optimiser mieux ce programme, quelqu'un pourrait me donner un indice s'il vous plait? J'ai déjà tenté de faire ma propre recherche dichotomique mais c’était trop lent, alors j'en ai pris une d'une library qui je suppose est déjà optimisée, mais malgré tout je suis trop lent... Merci
Je pense que la bisect vous fait perdre plus de temps qu'autre chose.
ls = []
for _ in range(int(input())):
s = input()
if s == "Q":
print(len(ls))
else:
h = int(s.split()[-1])
for i, n in enumerate(ls):
if h >= n:
# Affectation par slicing (remplace toutes les valeurs
# du slice par celles de la nouvelle liste)
ls[i:] = [h]
break
else: # if not break:
ls.append(h)
Ça devrait être suffisant pour passer largement en-dessous de la limite des 2 secondes.
TryCatch Merci pour ta reponse, mais ta solution n'est pas assez rapide :/, meme en ajoutant l'aide de linekioubeur.
Par contre linekioubeur j'ai teste ta solution sur mon premier jet de code et ca marche! Merci
import sys
requetes = int(input())
tab = []
for i in range(requetes):
requete=sys.stdin.readline()
if requete == "Q\n":
print (len(tab))
else :
taille = int(requete[2:])
while len(tab) !=0 and tab[-1]<= taille:
del tab[-1]
tab.append(taille)
import sys
requetes = int(input())
tab = []
for i in range(requetes):
requete=sys.stdin.readline()
if requete == "Q\n":
print (len(tab))
else :
taille = int(requete[2:])
while len(tab) !=0 and tab[-1]<= taille:
del tab[-1]
tab.append(taille)
Et tu passes tous les tests de performance avec ce code ?
Oui, il a une complexite O(2N), ce qui est suffisant pour passer les tests de performances ^^.
Mon second algorithme (la recherche dichotomque) avait une complexité O(N(log(n)) qui était trop longue
- Edité par HugoCarpentier1 15 janvier 2020 à 10:21:38
FRANCE IOI : Optimiser une recherche
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Découverte Python Doc Tkinter Les chaînes de caractères