enfaite j'ai un probleme avec cet exo ,je l'ai pas compris , j'ai pas compris ce qu'il demande
qlq peut m'expliquer et Merci d'avance
Choisir un manteau pour les vacances est toujours difficile, surtout lorsque l'on ne sait pas encore où l'on part. En effet chaque manteau est adapté à une certaine plage de température et vous aimeriez bien choisir un manteau qui s'adaptera à vos besoins.
Vous voilà dans un vaste magasin de manteaux, un peu perdu dans l'énorme choix proposé. Pour chacun des manteaux du magasin, vous connaissez l'intervalle de température qui lui correspond.
Avec votre logique impassible, vous décidez d'inventer un critère qui vous aidera à choisir votre manteau : Le niveau d'un manteau sera défini comme le nombre d'autres manteaux du magasin dont l'intervalle de température est contenu dans l'intervalle de celui-ci.
Vous décidez de sortir votre ordinateur et d'écrire un programme qui déterminera le niveau maximal que l'on peut trouver.
Limites de temps et de mémoire (Python)
Temps : 2 s sur une machine à 1 GHz.
Mémoire : 8 000 ko.
Contraintes
1 <= nbManteaux <= 20 000.
0 <= temperatureinf, temperaturesup <= 500 000 000, l'intervalle de température d'un manteau.
Entrée
Sur la première ligne de l'entrée, votre programme lira un unique entier : nbManteaux, le nombre de manteaux du magasin.
Il lira ensuite nbManteaux lignes contenant chacune deux entiers indiquant l'intervalle de température d'un manteau.
Sortie
Votre programme affichera un unique entier : le niveau maximal d'un manteau.
Exemple
entrée :
8
1 3
2 5
5 8
3 6
2 5
3 8
3 6
3 8
sortie :
4
Commentaires
Dans l'exemple présenté, les niveaux des manteaux sont, dans l'ordre : 0, 1, 0, 1, 1, 4, 1, 4.
Le résultat à afficher est donc 4.
Si vous ne passez pas en temps les derniers tests, c'est que votre algorithme est trop lent. A vous de l'améliorer, par vous-même.
j'ai tenté un code, et quand je suis allé sur france ioi pour le valider, j'ai vu qu'en fait, je l'avais déjà résolu il y a longtemps avec un code 10 fois plus efficace ...
conclusion, j'étais bien meilleur avant en algo.
le voici:
z = [tuple(map(int,input().split()))for i in range(int(input()))]
z.sort(key=lambda x:x[1]-x[0],reverse=1)
qgr = 0
while qgr<len(z)/2:
mag = len(z)
a,*b = z
z = [i for i in b if not (i[0]>=a[0] and i[1]<=a[1])]
if mag-len(z)>qgr: qgr=mag-len(z)
print(qgr-1)
Voici ma solution. Par contre j'ai écrit ça il y a un an et aujourd'hui je ne la comprend plus Mais elle fonctionne, en moins d'une seconde effectivement.
N = int(input())
manteaux = [tuple(map(int, input().split())) for i in range(N)]
manteaux = dict(enumerate(sorted(manteaux, key=lambda x: (x[0], -x[1]))))
m2 = sorted(manteaux, key=lambda x: (-manteaux[x][1], manteaux[x][0]))
p2 = {m: i for i, m in enumerate(m2)}
print(max(N - i - p2[i] - 1 for i in range(N)))
10 manteaux en 2 groupes : 4 manteaux dont 1 a le plus grand intervalle + 6 autres.
Normalement mon code devrait pas passer. Je pense qu'il faut enlever le /2 du while. Je peux pas tester là, je suis au boulot.
J'ai testé ton code avec des intervalles aléatoires. Ça ne plante pas et ça semble correct.
Pour la fiabilité, il faudrait que je mette plus d'un algo dans mon code et que je teste avec la même liste.
Si je fais des séries à répétitions et que tout est pareil, c'est un bon indice que les algo devraient être corrects.
j'ai testé, et il faut effectivement modifier la condition du while dans mon code, c'était bien un coup de chance si j'ai passé les test france ioi, ils n'avaient pas tout prévu ^^:
Peux-tu me redonner ton code exact? Je ne sais pas lequel je teste (sans /2 avec /2 avec //2)
Sinon, je donnerai mon code non coloré au risque de me faire tuer ...
Avec les tests courants, ton code est environ 4 fois plus rapide que celui de thelinekioubeur.
z = [tuple(map(int,input().split()))for i in range(int(input()))]
m = 0
z.sort(key=lambda x:x[1]-x[0],reverse=1)
qgr = 0
while qgr<len(z):
mag = len(z)
a,*b = z
z = [i for i in b if not (i[0]>=a[0] and i[1]<=a[1])]
if mag-len(z)>qgr: qgr=mag-len(z)
print(qgr-1)
«... Le niveau d'un manteau sera défini comme le nombre d'autres manteaux du magasin dont l'intervalle de température est contenu dans l'intervalle de celui-ci.»
Qui est le 'celui-ci'?
Ceux qui sont inclus dans le plus grand? Ou ceux qui sont emboîtés comme dans les poupées russes.
Ton code fonctionne parfaitement si c'est la deuxième possibilité.
Le Tout est souvent plus grand que la somme de ses parties.
Le premier élément de la liste de départ n'est pas inclus dans la liste résultante de toute façon.
Tu as absolument raison. La comparaison est surement plus rapide que l'affectation. Du coup je pense qu'on peut même se passer du reverse et faire a=z.pop() à la place de a=z[0].
et sans l'indexage de 'a' c'est encore plus rapide:
z = [tuple(map(int,input().split()))for i in range(int(input()))]
m = 0
z.sort(key=lambda x:x[1]-x[0])
qgr = 0
while qgr<len(z):
mag = len(z)
aw,ah = z.pop()
z = [i for i in z if not (i[0]>=aw and i[1]<=ah)]
if mag-len(z)>qgr: qgr=mag-len(z)
print(qgr-1)
- Edité par josmiley 26 septembre 2020 à 7:24:48
Python c'est bon, mangez-en.
Choisir son manteau
× 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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.