Une première ligne contenant deux entiers (séparés par un espace) : N et P. N = Nombre total d'élèves inscrits dans la classe (entre 1 et un milliard); P = Nombre d'élèves qui vont venir en classe aujourd'hui.
Les P lignes suivantes contiennent chacune un entier: l'identifiant d'un élève qui arrive en cours, c'est-à-dire sa position dans la liste alphabétique des élèves de la classe. On vous garantit que chaque identifiant n'apparaît qu'une fois.
En sortie
Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Si tous les élèves inscrits sont présents, vous devez afficher -1.
Exemple
entrée :
10 5
4
1
7
3
2
sortie :
1
2
2
2
5
Voilà ce que j'ai fait de mieux:
import sys
def main():
max, venus = map(int, sys.stdin.readline().split())
presents = []
absent = 1
for _ in range(venus):
arrivant = int(sys.stdin.readline())
max -= 1
if arrivant > absent:
presents.append(arrivant)
elif arrivant == absent:
absent += 1
if presents:
presents.sort()
indice = 0
l = len(presents)
while indice < l and absent == presents[indice]:
indice += 1
absent += 1
del presents[:indice]
if not max:
absent =- 1
sys.stdout.write(str(absent)+'\n')
main()
Malheureusement, pour 3 tests sur 20 je reçois le message suivant:
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
Je n'ai pas pu accéder à ton lien parce que je ne suis pas connecté. L'énoncé n'est pas très clair. À la lumière de ton exemple, j'ai écrit ce qui suit. Ça fonctionne avec l'exemple. J'ai utilisé les "set" plutôt qu'une liste. Ça devrait être plus rapide: - max, venus = map(int, input().split()) absent = 1 presents = set() for _ in range(venus): arrivant = int(input()) presents.add(arrivant) while absent in presents: absent += 1 if absent <= max: print(absent) else: print(-1)
Le Tout est souvent plus grand que la somme de ses parties.
Merci. Mais ça ne passe que 9 tests sur 20 (même message que moi pour les 11 autres).
Je reproduis l'énoncé original:
Ce matin, en arrivant en cours, vous êtes le seul à l'heure : tous vos camarades sont en retard ou absents. Comme d'habitude, après un certain temps, votre professeur va faire l'appel dans l'ordre alphabétique, et va punir très sévèrement le premier élève qui ne répondra pas présent. Il sera plus clément pour les suivants car il aura déjà réussi à déverser sa rage quotidienne sur quelqu'un.
Les autres élèves arrivent un par un, dans un ordre quelconque. À chaque fois que l'un d'eux arrive, vous vous demandez quel serait l'élève puni, si votre professeur faisait l'appel juste après l'arrivée du nouvel élève.
Les élèves sont numérotés en fonction de leur position dans l'ordre d'appel. Étant donnée la liste des élèves qui arrivent, votre programme doit calculer, pour chaque nouvel élément de la liste, l'élève ayant l'identifiant le plus petit qui n'est pas présent à ce moment.
Limites de temps et de mémoire (Python)
Temps : 2,5 s sur une machine à 1 GHz.
Mémoire : 16 000 ko.
Contraintes
1 ≤ N ≤ 1 000 000 000, où N est le nombre d'élèves inscrits dans votre classe.
1 ≤ P ≤ 250 000, où P est le nombre d'élèves présents aujourd'hui.
1 ≤ Ei ≤ N, où Ei est l'identifiant d'un élève.
De plus, on vous garantit que :
Dans 20% des fichiers tests, on a N ≤ 1 000 et P ≤ 1 000.
Dans 70% des fichiers tests, on a N ≤ 250 000.
Entrée
La première ligne de l'entrée contient deux entiers séparés par un espace : N et P.
Les P lignes suivantes contiennent chacune un entier : l'identifiant d'un élève qui arrive en cours, c'est-à-dire sa position dans la liste alphabétique des élèves de la classe. On vous garantit que chaque identifiant n'apparaît qu'une fois.
Sortie
Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Si tous les élèves inscrits sont présents, vous devez afficher -1.
Dans le programme de Pierrot, on sait que les élèves de 1 à absent-1 sont arrivés. On peut donc les retirer de l'ensemble présents, ce qui réduit sa taille
import sys
def main():
max, venus = map(int, input().split())
absent = 1
presents = set()
for _ in range(venus):
arrivant = int(input())
if arrivant == absent:
absent += 1
while absent in presents:
presents.remove(absent)
absent += 1
else:
presents.add(arrivant)
if absent <= max:
print(absent)
else:
print(-1)
En bref, l'ensemble des élèves présents est modélisé par l'union de deux trucs disjoints
les entiers de 1 à absent -1
les éléments du set "présents"
---
dans le programme d'origine, ce qui fout dedans, c'est l'utilisation d'une liste, qui est retriée constamment. Alors que la recherche dans un set se fait en temps constant.
Si n vaut 1_000_000_000 tu auras un problème de mémoire. Il faut réduire le plus possible la longueur des set/list/dict s'il y a lieu. Il faudrait éviter le parcours de longues séquences. Dans quelle mesure les set et les dict sont rapides aà parcourir?
Le Tout est souvent plus grand que la somme de ses parties.
Pour 2 tests: Erreur d'exécution. Voici ce qui a été affiché :
Traceback (most recent call last):
line 5
print(min(t - s))
ValueError: min() arg is an empty sequence
Pour 2 tests: Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
Pour tous les autres: Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
Nos codes ne dépassent pas la zone des set ou listes, mais la mémoire imposée. Comme je viens de le dire, les ensembles sont trop longs et prennent trop de temps à parcourir. Je cherche encore un truc ...
On pourrait faire une recherche dichotomique pour insérer l'arrivant et chercher si l'absent est dans la liste.
On pourrait garder le plus petit et le plus grand arrivant. On pourrait ainsi éviter d'ajouter des éléments dans la liste.
...
Qui a dit que cet algo était simple?
- Edité par PierrotLeFou 22 mars 2022 à 17:44:16
Le Tout est souvent plus grand que la somme de ses parties.
La solution ne serait pas de stocker des elements individuels mais des ranges dès qu'on le peut. Ainsi, plutôt que d'avoir [0,1,2,3,4] on peut directement avoir range(5). L'espace occupé par un range est constant. En outre, il permet aussi d'utiliser in.
Le problème est qu'on peut avoir plusieurs range dans la liste. Si comme je l'ai dit, on garde le plus petit et le plus grand. L'absent pourrait se trouver dans un de ces range ou entre deux range. Comment mettre à jour ces range de façon efficace?
Le Tout est souvent plus grand que la somme de ses parties.
Le problème est qu'on peut avoir plusieurs range dans la liste. Si comme je l'ai dit, on garde le plus petit et le plus grand. L'absent pourrait se trouver dans un de ces range ou entre deux range. Comment mettre à jour ces range de façon efficace?
Non, mais justement, on ne met que les range pour lesquels tout le monde est là ... sinon ça n'a aucun intérêt. Au début c'est coûteux parce qu'un range prend plus de place en mémoire qu'un int, mais plus il y a d'item moins cela devient coûteux. Si dans la liste on a [range(10, 15), range(16, 18), range(20, 23)] et que 15 apparait, on se retrouve avec [range(10,18), range(20,23)] en fusionnant les deux premiers.
Ça j'avais compris. Mais il y a toujours la contrainte de temps qui semble assez serrée. Et si les range sont ordonnés comme on devrait pouvoir le faire, comment les représente-t-on? par ex: [10, 15, 16, 18, 20, 23] où les positions paires sont les débuts et les positions impaires sont les fins. ou encore [[10, 15], [16, 18], [20, 23]] et [range(10, 16), range(16, 19), range(20, 24)] fonctionne également. Mais la dernière forme est plus difficile à gérer.
Le Tout est souvent plus grand que la somme de ses parties.
Un ami me dit qu'il a la solution; selon lui, il y aurait un indice capital dans l'énoncé auquel je n'ai pas fait attention. Pour l'instant je ne vois pas.
Y a-t-il quelque chose à tirer de ces lignes?
De plus, on vous garantit que :
Dans 20% des fichiers tests, on a N ≤ 1 000 et P ≤ 1 000.
Une manière d'optimiser serait-elle en affichant toute (ou une partie) des lignes d'un coup?
Je me souviens que lorsque j'avais fait les exos france-ioi (avec un autre langage), c'était un problème que j'avais eu et qui plombait mon algo en temps.
Dans les 30% de tests, il n'y aurait pas de -1 à afficher aussi. Le -1 est à afficher que lorsque P >= N (qui n'arrive que dans le cas particulier où P = N).
EDIT: Le truc des 250k affichages est faux. C'est juste P affichages quoiqu'il arrive.
@umfred: merci pour le truc des .start et .stop L'énoncé dit: > En sortie > Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Que veut dire "à chaque fois qu'un élève arrive"? Est--ce qu'on laisse supposer qu'on n'a pas besoin d'accumuler ceux qui sont venus? > Si tous les élèves inscrits sont présents, vous devez afficher -1. KoaTao a bien précisé que cela n'arrive que si n == p Mais doit-on afficher -1 dès le début ou après p-1 lignes?
-
Je me ramasse des indices:
Supposons qu'on a une telle liste d'intervalles, le nouvel arrivant ne se trouvera dans aucun intervalle, puisqu'on nous garantit qu'il n'apparaît qu'une fois.
Il se trouvera soit avanrt le premier, soit après le dernier ou entre deux intervalles.
Si l'absent se trouve entre le plus petit et le plus grand, il faudra faire sauter les intervalles des éléments plus petits.
Joyeuse gestion des intervalles.
Si on nous accorde 16 000 Ko, on doit bien pouvoir accumuler quelque chose ...
edit: J'ai codé quelque chose avec les intervalles qui fonctionne avec l'exemple mentionné et je suppose qu'il marchera pour tous les cas. J'ai choisi de représenter les intervalles tels que les positions paires (0, 2, 4, ...) représentent les bornes inférieures et les positions impaires suivantes représentent les bornes supérieures. Je ne sais pas si ma fonction insertion est suffisamment efficace. On ne doit rien retrancher de la liste des intervalles. Je n'enlevais rien de mes set() dans le code précédent. - # Recherche dichotomique avec point d'insertion. def recherche(liste, val): d = 0 f = len(liste) while d < f: m = (d+f) // 2 if liste[m] == val: return m elif liste[m] > val: f = m else: d = m+1 return -(d+1) # Point d'insertion. # Insertion de la valeur (elle ne peut pas être déjà présente) # Les intervalles seront disjoints. def insertion(liste, val): if len(liste) == 0: liste[:] = [val, val] elif val < liste[0]: liste[:] = [val, val] + liste elif val > liste[-1]: liste.extend([val, val]) else: p = recherche(liste, val) p = -(p+1) # Sera forcément négatif. p = p ^ (p&1) # Borne inférieure si les bornes sont égales. if liste[p-1]+2 == liste[p]: liste[p-1:p+1] = [] elif liste[p-1] == val-1: liste[p-1] = val elif liste[p] == val+1: liste[p] = val else: liste[p:p+1] = [val, val, liste[p]] # Code principal. max, venus = map(int, input().split()) absent = 1 presents = [] for _ in range(venus): arrivant = int(input()) insertion(presents, arrivant) p = recherche(presents, absent) if p < 0: # On n'est pas sur une borne. p = -(p+1) # Point d'insertion if p&1: # Dans un intervalle absent = presents[p] + 1 # Suivant de l'intervalle else: # On est sur une borne. absent = presents[p|1] + 1 # Borne supérieure + 1 if absent <= max: print(absent) else: print(-1)
- Edité par PierrotLeFou 23 mars 2022 à 6:10:40
Le Tout est souvent plus grand que la somme de ses parties.
Est-ce que tu as essayé si, comme KoaTao l'a évoqué, en faisant la saisie au début (boucle de saisie), puis en bouclant sur le tableau des saisies ça changeait quelque chose ?
*1 ≤ P ≤ 250 000, où P est le nombre d'élèves présents aujourd'hui.
Ce qu'on peut remarquer rapidement dans ce programme c'est qu'on a le droit à suffisamment d'espace mémoire pour stocker 1 million ou plus d'éléments. Donc plutôt que de créer des structures complexes, et d'essayer d'optimiser en taille la mémoire. On peut directement utiliser ce qu'on nous donne. Bien sur on ne peut pas stocker 1 milliards d'éléments, mais sachant que seulement 250 000 élèves seront présent, il nous suffit de stocker 250.000 éléments. On peut donc noter dans un tableau de booléens si un élève (<250.000) est présent ou absent.
[false]*250000
Remplir ce tableau se fait en O(1) Et mettre à jour la position du dernier absent est en O(n) mais ne se recalcule pas à chaque boucle, c'est O(n) sur toute la durée du programme. Donc on obtiens un programme plus rapide qu'un set car on a juste un tableau statique.
(texte de neo-magestik, pour ceux qui l'ont connu, de chez France IOI)
Voilà une solution (merci à neo-magestik qui m'a bien aiguillé):
import sys
def main():
max, venus = map(int, sys.stdin.readline().split())
absent = 1
presents = [False]*250002
for i in range(1,venus):
arrivant = int(sys.stdin.readline())
if arrivant <= 250000: presents[arrivant] = True
if arrivant == absent:
while presents[absent]: absent += 1
sys.stdout.write(str(absent)+'\n')
dernier = int(input())
if venus == max: absent =- 1
elif dernier == absent:
presents[dernier]=True
while presents[absent]: absent += 1
sys.stdout.write(str(absent)+'\n')
main()
Et merci à vous tous aussi pour votre soutien et votre implication.
J'ai quand même appris quelques choses intéressantes de vos idées et propositions.
bah c'est possible, mais tant que l'étudiant n°1 ne sera pas passé, ça sera toujours lui le plus petit absent et au pire, ça sera le 250000-1 qui sera le plus petit
neo-magestik a écrit: > Remplir ce tableau se fait en O(1) Désolé, ça se fait en O(p) (tout de même très rapide) >Et mettre à jour la position du dernier absent est en O(n) mais ne se recalcule pas à chaque boucle, c'est O(n) sur toute la durée du programme. Mettre à jour la position de l'arrivant se fait en O(1) au pire p fois. Et on ne parcours le tableau qu'une fois, soit O(p) pour tout le programme.
Et absent est augmenté au pire à chaque tour de boucle, donc absent <= 250000+1
- Edité par PierrotLeFou 24 mars 2022 à 2:20:58
Le Tout est souvent plus grand que la somme de ses parties.
de ce que j'ai compris, un code dans ce genre là devrait solutionner les limitations matériel et temporel imposés:
lst =[]
P = P.sort(reverse=False)
for i in P:
i -= 1
if len(P) == N:
print(-1)
else:
lst.append(i)
# que ce passe t'il si c'est le premier elève de la liste qui est absent: le prof passe sa colère aucun élève?
voici comme je gère ce cas là:
if lst[0] == 0:
lst[0] = None
else:
pass
explication vite fait du code:
je parcours les élèments de la liste P (liste des élèves présents) que j'ai au préalable trié par ordre croissant
je vérifie si la longueur de la liste P est élage à la valeur du nb d'éléve inscrit, auquel cas, tt le monde est là et je print -1
sinon, j'append dans une liste les éléments (éléves) qui précédent ceux présent
et y a le cas où c'est l'éléve à la position 1 de la liste alphabétique qui est absent...pour pas me retrouver avec un 0, je dis que ça vaut None.
si vous avez encore des erreur dû au temps d'éxécution, je vous invite à jeter un coup d'oeil sur la méthode invert du package operator (faire un import).
cela peut être utile surtout si la liste P passé en paramètre est supérieure ou égale
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.
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.
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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.