Partage
  • Partager sur Facebook
  • Partager sur Twitter

France IOI Affectation des salles

Erreurs dépassement mémoire

    19 mai 2024 à 10:44:25

    Bonjour,

    je suis sur un exercice que j'avais résolu en C++

    je m'exerce à python

    voici les données

    Votre ami Jacques a planifié toute sa saison de spectacles et choisi les horaires des différentes représentations, mais a oublié de définir un point très important : dans quelle salle se produira chaque représentation.

    Jacques vous indique de combien de salles il dispose, et vous décrit la période de temps pendant laquelle se déroulera chacune des représentations qu'il a planifiées pour divers spectacles. Votre objectif est d'écrire un programme qui détermine si Jacques dispose d'un nombre suffisant de salles pour y répartir les représentations, puis de proposer une affectation de salle à chacune d'elles.

    Les périodes de deux représentations affectées à la même salle ne peuvent pas se recouvrir. La période d'une représentation est un intervalle décrit par deux dates, exprimées en unités de temps depuis le début de l'année. Pour que deux représentations successives ne se recouvrent pas, la date de début de la deuxième doit être supérieure ou égale à la date de fin de la première.

    Limites de temps et de mémoire (Python)

    • Temps : 5 s sur une machine à 1 GHz.
    • Mémoire : 24 000 ko.

    Contraintes

    • 1 <= S <= 100, où S est le nombre de salles du complexe de Jacques.
    • 1 <= R <= 100 000, où R est le nombre de représentations planifiées.
    • 0 <= Di < Fi <= 1 000 000 000, où Di et Fi sont respectivement la date de début et la date de fin de la représentation i.

    Entrée

    La première ligne de l'entrée contient deux entiers S et Rséparés par une espace : le nombre de salles disponibles et le nombre de représentations planifiées.

    Chacune des R lignes suivantes décrit une représentation par deux entiers Di et Fi, donnant les dates de début et de fin de la période prévue pour cette représentation.

    Sortie

    La première ligne de la sortie doit contenir le texte "OUI" s'il est possible d'affecter les représentations aux salles sans recouvrement, et "NON" sinon.
    Si une affectation est possible, la deuxième ligne doit contenir R entiers séparés par des espaces, donnant pour chaque représentation, dans l'ordre dans lequel elles sont décrites en entrée, le numéro de la salle à laquelle vous choisissez de l'affecter. Les salles sont numérotées de 1 à S.

    Exemple

    entrée :

    2 5
    0 4
    4 9
    2 6
    7 11
    10 12

    sortie :

    OUI
    1 1 2 2 1

    Commentaires

    Jacques dispose de 2 salles et a planifié 5 représentations.

    Il est possible de répartir les représentations entre les deux salles sans recouvrement :

    Les 1ère, 2ème et 5ème représentations sont affectées à la salle 1, respectivement du temps 0 au temps 4, du temps 4 au temps 9, et du temps 10 au temps 12.

    Les 3ème et 4ème représentations sont affectées à la salle 2, respectivement du temps 2 au temps 6, et du temps 7 au temps 11.

    Plusieurs affectations sont possibles (on peut par exemple échanger les deux salles), vous pouvez donner n'importe laquelle.

    voici ce que j'ai fait

    import heapq
    import sys
    def assign_salles(S, R, representations):
        events = []
        for i, (start, end) in enumerate(representations):
            events.append((start, 'start', i))
            events.append((end, 'end', i))
        
        events.sort(key=lambda x: (x[0], x[1] == 'start'))
        
        free_rooms = list(range(1, S + 1))
        heapq.heapify(free_rooms)
        
        room_assignment = [None] * R
        ongoing_reps = {}
        for event in events:
            date, event_type, index = event
            
            if event_type == 'start':
                if not free_rooms:
                    return "NON"
                assigned_room = heapq.heappop(free_rooms)
                room_assignment[index] = assigned_room
                ongoing_reps[index] = assigned_room
            else:
                assigned_room = ongoing_reps.pop(index)
                heapq.heappush(free_rooms, assigned_room)
        
        return "OUI\n" + " ".join(map(str, room_assignment))
    if __name__ == "__main__":
        input = sys.stdin.read
        data = input().split()
        
        S = int(data[0])
        R = int(data[1])
        representations = []
        index = 2
        for _ in range(R):
            Di = int(data[index])
            Fi = int(data[index + 1])
            representations.append((Di, Fi))
            index += 2
        
        result = assign_salles(S, R, representations)
        print(result)

    et j'obtiens 14/17 ok

    sur les tests 4, 9 et 10 j'ai l'erreur suivante :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.

    Or le solution proposée en Python arrive aux mêmes erreurs. Donc je ne comprends pas si erreur du site ou pas ?

    • Partager sur Facebook
    • Partager sur Twitter
      21 mai 2024 à 1:56:09

      Tu as écrit:

      > je suis sur un exercice que j'avais résolu en C++

      Est-ce que TOUS les exercices étaient corrects en C++?

      Reprend ton code en C++ et essaies de le traduire correctement.

      Attention, en C++ on peut déborder d'un tableau et le code semble fonctionner.

      Python ne te laissera pas de chance sur ce point.

      Voici un bon lien sur les files de priorité:

      http://pascal.ortiz.free.fr/contents/python/structures_de_donnees/les_files_de_priorite.html

      La ligne suivante peut te jouer un tour:

          events.sort(key=lambda x: (x[0], x[1] == 'start'))

      En Python (comme en C++) True vaut 1 et False vaut 0. Les "start" vont être placés après les autres.

      -
      Edité par PierrotLeFou 21 mai 2024 à 2:20:33

      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        21 mai 2024 à 21:29:54

        Merci @PierrotLeFou

        je regarde ça

        mon programme en c++ passe tous les tests

        c'est surtout que la solution du site ne passe pas les mêmes tests que mon programme

        • Partager sur Facebook
        • Partager sur Twitter
          24 mai 2024 à 21:59:29

          Voilà j'ai trouvé une solution non sans mal pour passer le problème de mémoire

          import sys
          import heapq
          def main():
              nbSalle, nbRepresentation = map(int, input().split())
              events = []
              index = 0
              for line in sys.stdin:
                  debut, fin = map(int, line.split())
                  events.append((debut, fin, index))
                  index += 1
                  if index >= nbRepresentation:
                      break
              events.sort()
              free_rooms = [(0, i) for i in range(1, nbSalle + 1)]
              heapq.heapify(free_rooms)
              room_assignment = [0] * nbRepresentation
              for start, end, idx in events:
                  # Vérifie si une salle est disponible pour la représentation
                  salle_disponible = False
                  for _, (end_time, _) in enumerate(free_rooms):
                      if end_time <= start:
                          assigned_room = heapq.heappop(free_rooms)[1]
                          heapq.heappush(free_rooms, (end, assigned_room))
                          room_assignment[idx] = assigned_room
                          salle_disponible = True
                          break
                  if not salle_disponible:
                      print("NON")
                      return
              print("OUI")
              #print(" ".join(map(str, room_assignment)))
              print(*room_assignment)
          if __name__ == "__main__":
              main()



          • Partager sur Facebook
          • Partager sur Twitter
            25 mai 2024 à 23:25:18

            Bien joué. :)
            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

              6 juin 2024 à 13:44:44

              Bonjour,

              L'utilisation de heapq faisait-elle partie des contraintes ?

              J'ai refait le truc sans ça en 27 lignes:

              # -*- coding:Utf-8 -*-
              #05/06/2024 15:50:30
              
              def try_to_insert(schedule, room):
                  ''' Checks if schedule can be inserted in room '''
              
                  ok = True
                  start, end = schedule[0], schedule[1]
              
                  for show in room:
                      show_start, show_end = shows_to_plan[show][0], shows_to_plan[show][1]
                      if(show_start < start < show_end or show_start < end <show_end): ok = False
              
                  return(ok)
              
              max_rooms = 2
              shows_to_plan = {1:[0,4], 2:[4,9], 3:[2,6], 4:[7,11], 5:[10,12]}
              rooms = [[1]]
              
              for show_nb, schedule in shows_to_plan.items():
                  if(show_nb == 1): continue
              
                  found = False
                  for room in rooms:
                      ok = try_to_insert(schedule, room)
                      if(ok):
                          found = True
                          room.append(show_nb)
                  if(not found): rooms.append([show_nb])
              
              if(len(rooms) <= max_rooms):
                  print('\nOK\n')
                  for show_nb in shows_to_plan.keys():
                      for k in range(len(rooms)):
                          if(show_nb in rooms[k]): print('Spectacle {} en salle {}'.format(show_nb, k+1))
              else:
                  print('\nNOT OK')



              -
              Edité par Phil_1857 6 juin 2024 à 13:45:14

              • Partager sur Facebook
              • Partager sur Twitter
                7 juin 2024 à 8:10:00

                Voici un code un peu "tricky" pour sauver de la mémoire.

                Il devrait être rapide malgré le jeu avec les entrées du dictionnaire:

                -

                from array import array
                S, R = map(int, input().split())
                representations = array('q', [0] * (2*R))
                resultat = array('q', [0] * R)
                m20 = (1<<20) - 1
                m17 = 1<<17
                i = 0
                for r in range(R):
                    d, f = map(int, input().split())
                    representations[i] = (d<<20) + m17 + r     # Les représentations se terminant à ce moment doivent passer après celles qui y débutent.
                    representations[i+1] = (f<<20) + r
                    i += 2
                salles = list(range(S, 0, -1))
                assignation = {}
                for r in sorted(representations):
                    r &= m20
                    if r & m17 == 0:
                        salles.append(assignation[r])
                        resultat[r] = assignation[r]
                        del(assignation[r])
                    else:
                        if len(salles) == 0:
                            print("NON")
                            exit()
                        r ^= m17
                        assignation[r] = salles.pop()
                print("OUI")
                print(*resultat)

                -
                Edité par PierrotLeFou 7 juin 2024 à 8:11:01

                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  8 juin 2024 à 6:13:12

                  Je ne trouve pas l'exo sur france ioi, quelqu'un aurait le lien SVP ?

                  -
                  Edité par josmiley 8 juin 2024 à 9:03:30

                  • Partager sur Facebook
                  • Partager sur Twitter

                  Python c'est bon, mangez-en. 

                    8 juin 2024 à 9:48:12

                    voici le lien

                    https://www.france-ioi.org/algo/task.php?idChapter=532&iOrder=10&idCourse=1131&idTask=1131

                    @Phil_1857

                    Effectivement ton programme donne bien la bonne solution pour l'exemple

                    mais pourrais tu le réécrire pour que je puisse le tester sur le site et voire s'il respecte les contraintes de temps et mémoire

                    voici un exemple

                    en entrée le programme doit prendre

                    2 5
                    0 4
                    4 9
                    2 6
                    7 11
                    10 12

                    et en sortie le résultat

                    OUI
                    1 1 2 2 1

                    @PierrotLeFou

                    Ton programme passe tous les tests

                    Pour les tests 4 9 et 10 qui posent problèmes les temps données sont respectivement de

                    2.82s

                    2.46s

                    3.05s

                    Pour te donner un point de repère

                    Mon programme au dessus passe les tests 4, 9 , 10 avec les temps suivants:

                    1.34s

                    1.09s

                    1.68s

                    • Partager sur Facebook
                    • Partager sur Twitter
                      8 juin 2024 à 18:08:08

                      Bonjour,

                      Qu'entends-tu par:

                      "le réécrire pour que je puisse le tester sur le site"  ???

                      • Partager sur Facebook
                      • Partager sur Twitter
                        9 juin 2024 à 4:07:22

                        En fait, je n'ai pas besoin du dictionnaire. J'écris directement dans le résultat.

                        J'utilise un générateur qui donne directement les éléments au tri:

                        -

                        def lecture(R):


                            for r in range(R):


                                d, f = map(int, input().split())


                                yield (d<<20) + m17 + r


                                yield (f<<20) + r

                        S, R = map(int, input().split())


                        m17 = 1<<17


                        m20 = (1<<20) - 1


                        assignation = [0] * R


                        salles = list(range(S, 0, -1))


                        for r in sorted(lecture(R)):

                            r &= m20


                            if r & m17 == 0:


                                salles.append(assignation[r])


                            else:


                                if len(salles) == 0:


                                    print("NON")


                                    exit()


                                assignation[r^m17] = salles.pop()


                        print("OUI")


                        print(*assignation)

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          9 juin 2024 à 10:24:32

                          @PierrotLeFou

                          Ton dernier programme passe tous les tests.

                          Pour info sur les tests 4, 9, 10 voici les temps :

                          2.32s

                          2.08s

                          2.53s

                          @Phil_1857

                          je voulais dire le réecrire pour pouvoir saisir les entrées dans le terminal et une sortie conforme à ce qui est demandé

                          du coup j'ai fait ceci

                          # -*- coding:Utf-8 -*-
                          #05/06/2024 15:50:30
                           
                          def try_to_insert(schedule, room):
                              # Checks if schedule can be inserted in room '''
                           
                              ok = True
                              start, end = schedule[0], schedule[1]
                           
                              for show in room:
                                  show_start, show_end = shows_to_plan[show][0], shows_to_plan[show][1]
                                  if(show_start < start < show_end or show_start < end <show_end): ok = False
                           
                              return(ok)
                          """ 
                          max_rooms = 2
                          shows_to_plan = {1:[0,4], 2:[4,9], 3:[2,6], 4:[7,11], 5:[10,12]}
                          print(shows_to_plan)
                          """
                          # First line: number of rooms and number of representations
                          max_rooms, nbRepresentation = map(int, input().split())
                          # Read the shows into a dictionary
                          shows_to_plan = {}
                          for i in range(1, nbRepresentation + 1):
                              debut, fin = map(int, input().split())
                              shows_to_plan[i] = (debut, fin)
                          
                          rooms = [[1]]
                           
                          for show_nb, schedule in shows_to_plan.items():
                              if(show_nb == 1): continue
                           
                              found = False
                              for room in rooms:
                                  ok = try_to_insert(schedule, room)
                                  if(ok):
                                      found = True
                                      room.append(show_nb)
                              if(not found): rooms.append([show_nb])
                           
                          if(len(rooms) <= max_rooms):
                              print('OUI')
                              for show_nb in shows_to_plan.keys():
                                  for k in range(len(rooms)):
                                      if(show_nb in rooms[k]): print((k+1),end=" ")
                              
                          else:
                              print('NON')
                          
                          

                          mais dans cet exemple

                          3 6

                          2 6

                          10 12

                          1 4

                          7 15

                          3 4

                          5 8

                          le programme renvoie

                          OUI

                          1 1 2 1 2 3 3

                          au lieu de

                          OUI

                          2 1 1 2 3 1

                          • Partager sur Facebook
                          • Partager sur Twitter
                            9 juin 2024 à 20:59:54

                            Bonjour,

                            J'ai modifié la fonction try_to_insert:

                            def try_to_insert(schedule, room):
                                ''' Checks if schedule can be inserted in room '''
                            
                                ok = True
                                start, end = schedule[0], schedule[1]
                            
                                for show in room:
                                    show_start, show_end = shows_to_plan[show][0], shows_to_plan[show][1]
                                    if(show_start < start < show_end or show_start < end < show_end): ok = False
                                    if(start < show_start < end or start < show_end < end): ok = False
                            
                                return(ok)

                            Ca donne:

                            1,1,2,2,3,3

                            qui répond au problème aussi bien que 2,1,1,2,3,1



                            • Partager sur Facebook
                            • Partager sur Twitter
                              10 juin 2024 à 11:38:06

                              Duncan4031 a écrit:

                              Voilà j'ai trouvé une solution non sans mal pour passer le problème de mémoire

                              import sys
                              import heapq
                              def main():
                                  nbSalle, nbRepresentation = map(int, input().split())
                                  events = []
                                  index = 0
                                  for line in sys.stdin:
                                      debut, fin = map(int, line.split())
                                      events.append((debut, fin, index))
                                      index += 1
                                      if index >= nbRepresentation:
                                          break
                                  events.sort()
                                  free_rooms = [(0, i) for i in range(1, nbSalle + 1)]
                                  heapq.heapify(free_rooms)
                                  room_assignment = [0] * nbRepresentation
                                  for start, end, idx in events:
                                      # Vérifie si une salle est disponible pour la représentation
                                      salle_disponible = False
                                      for _, (end_time, _) in enumerate(free_rooms):
                                          if end_time <= start:
                                              assigned_room = heapq.heappop(free_rooms)[1]
                                              heapq.heappush(free_rooms, (end, assigned_room))
                                              room_assignment[idx] = assigned_room
                                              salle_disponible = True
                                              break
                                      if not salle_disponible:
                                          print("NON")
                                          return
                                  print("OUI")
                                  #print(" ".join(map(str, room_assignment)))
                                  print(*room_assignment)
                              if __name__ == "__main__":
                                  main()



                              Et comment tu as fait ? J'ai pas compris .

                              • Partager sur Facebook
                              • Partager sur Twitter

                              Python c'est bon, mangez-en. 

                                10 juin 2024 à 18:55:30

                                Moi non plus (pas tout à fait).

                                Il empile des tuples (temps, numéro de salle) qui sortent en temps voulu (du moins je pense).

                                Si la salle est occupée au moment où elle resort, on a un problème, sinon on peut la réassigner.

                                Je crois que le enumerate est inutile:

                                        for _, (end_time, _) in enumerate(free_rooms):

                                Et je comprend pourquoi mon code est plus lent. Je trie 2 fois plus d'éléments, ce qui me donne un temps de tri environ 2.2 fois plus lent.

                                -
                                Edité par PierrotLeFou 10 juin 2024 à 19:19:04

                                • Partager sur Facebook
                                • Partager sur Twitter

                                Le Tout est souvent plus grand que la somme de ses parties.

                                  10 juin 2024 à 20:04:02

                                  j'ai trouvé, finalement ça passe, c'est la liste compréhension qui bloquait le schmilblick.

                                  import sys
                                  
                                  def foo():
                                      S,R = map(int,input().split())
                                      rep = []
                                      for k,l in enumerate(sys.stdin):
                                         i,j = l.split()
                                         rep.append((int(i),int(j),k))
                                      out = [0]*R
                                      salles = [0]*S
                                      for d,f,o in sorted(rep):
                                          for e,s in enumerate(salles):
                                              if d>=s:
                                                  salles[e] = f
                                                  out[o] = e+1
                                                  break
                                          else:
                                              print('NON')
                                              break
                                      else:
                                          print('OUI')
                                          print(*out)
                                      
                                  foo()   


                                  test  4: 1.66s

                                  test  9: 0.84s

                                  test 10: 1.18s

                                  -
                                  Edité par josmiley 10 juin 2024 à 22:04:55

                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  Python c'est bon, mangez-en. 

                                    11 juin 2024 à 2:41:38

                                    Je combine le code de Duncan4031 et josmiley.

                                    -

                                    import sys
                                    import heapq
                                    def trouve():
                                        S,R = map(int,input().split())
                                        rep = []
                                        for r, P in enumerate(sys.stdin):
                                            rep.append((*map(int, P.split()), r))
                                        ass = [0]* R
                                        salles = [(0, i) for i in range(1, S+1)]
                                        heapq.heapify(salles)
                                        for d, f, r in sorted(rep):
                                            t, s = heapq.heappop(salles)     # Obtenir la prochaine salle disponible.
                                            if t <= d:     # Si la salle est déjà disponible à ce moment.
                                                ass[r] = s     # Je l'assigne à la représentation.
                                                heapq.heappush(salles, (f, s))     # Je la rend disponible à la fin de la représentation.
                                            else:     # Aucune salle disponible à ce moment.
                                                print('NON')     # Je suis bloqué.
                                                return
                                        print('OUI')
                                            print(*ass)
                                    trouve()

                                    • Partager sur Facebook
                                    • Partager sur Twitter

                                    Le Tout est souvent plus grand que la somme de ses parties.

                                      11 juin 2024 à 4:54:06

                                      Je m'aperçois que j'ai le même code que Duncan4031 en fait ^^, ça m'apprendra à survoler le fil sans lire les autres codes. Au moins j'ai découvert heapq, c'est très intéressant. Effectivement le gain est considérable certaines fois.

                                      sans heapq / avec heapq

                                      test  4: 1.66s / 0.95s

                                      test  9: 0.84s / 0.85s

                                      test 10: 1.18s / 1.3s

                                      -
                                      Edité par josmiley 11 juin 2024 à 5:33:01

                                      • Partager sur Facebook
                                      • Partager sur Twitter

                                      Python c'est bon, mangez-en. 

                                        11 juin 2024 à 16:39:40

                                        @PierrotLeFou

                                        l'interpréteur python du site doit être un peu vieux. du coup J'ai remplacé

                                        rep.append((*map(int, P.split()), r))

                                        par

                                        debut, fin = map(int, P.split())

                                        suivi de

                                        rep.append((debut, fin, r))

                                        pour éviter l'utilisation de l'expression étoilée.

                                        ce qui donne

                                        import sys
                                        import heapq
                                        
                                        def trouve():
                                            S, R = map(int, input().split())
                                            rep = []
                                            for r, P in enumerate(sys.stdin):
                                                debut, fin = map(int, P.split())
                                                rep.append((debut, fin, r))
                                            ass = [0] * R
                                            salles = [(0, i) for i in range(1, S + 1)]
                                            heapq.heapify(salles)
                                            
                                            for d, f, r in sorted(rep):
                                                t, s = heapq.heappop(salles)  # Obtenir la prochaine salle disponible.
                                                if t <= d:  # Si la salle est déjà disponible à ce moment.
                                                    ass[r] = s  # Je l'assigne à la représentation.
                                                    heapq.heappush(salles, (f, s))  # Je la rends disponible à la fin de la représentation.
                                                else:  # Aucune salle disponible à ce moment.
                                                    print('NON')  # Je suis bloqué.
                                                    return
                                            print('OUI')
                                            print(*ass)
                                        
                                        trouve()


                                        pour les tests 4, 9, 10

                                        1.15s

                                        1.08s

                                        1.55s

                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        France IOI Affectation des salles

                                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                        • Editeur
                                        • Markdown