0403 - Concert

From Bitnami MediaWiki
Revision as of 00:00, 23 March 2024 by Aurelia Raluca (talk | contribs) (Pagină nouă: = Cerinţa = Gigel este un cântăreț începător. El știe deja să cânte <code>n</code> melodii, și pentru fiecare melodie se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de <code>T</code> secunde. El vrea să cânte cât mai multe melodii, pentru a-și demonstra talentul deosebit. Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf. = Date de intrare = F...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerinţa[edit | edit source]

Gigel este un cântăreț începător. El știe deja să cânte n melodii, și pentru fiecare melodie se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de T secunde. El vrea să cânte cât mai multe melodii, pentru a-și demonstra talentul deosebit.

Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf.

Date de intrare[edit | edit source]

Fişierul de intrare concerIN.txt conţine pe prima linie numerele n T. Fiecare dintre următoarele n linii conține durata unei melodii, în formatul m:s, unde m și s pot avea una sau două cifre.

Date de ieşire[edit | edit source]

Fişierul de ieşire concertOUT.txt va conţine pe prima linie numărul M, reprezentând numărul maxim de melodii care pot fi alese. Următoarea linie va conține M numere între 1 și n, reprezentând numărul de ordine al melodiilor alese, așa cum sunt ele date în fișierul de intrare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricţii şi precizări[edit | edit source]

  • 1 ≤ n ≤ 100
  • 1 ≤ T ≤ 1000
  • 0 ≤ m ≤ 10
  • 0 ≤ s ≤ 59

Exemplul 1:[edit | edit source]

concertIN.txt

7 450
2:30
1:45
2:10
03:00
01:15
02:05
2:05

concertOUT.txt

4
2 5 6 7 

Explicație[edit | edit source]

În 450 de secunde se pot cânta maxim 4 melodii, de exemplu cele numerotate cu: 2 5 6 7.

Exemplul 2:[edit | edit source]

concertIN.txt

101 450
2:30
1:45
2:10
03:00
01:15
02:05
2:05

concertOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, t):

   if not (1 <= n <= 100 and 1 <= t <= 1000):
       return False
   return True

def main():

   with open("concertIN.txt", "r") as fin, open("concertOUT.txt", "w") as fout:
       n, t = map(int, fin.readline().split())
       
       if not verificare_restrictii(n, t):
           fout.write("Datele nu corespund restrictiilor impuse")
           return
       v = [(0, 0)] * (n + 1)  
       for i in range(1, n + 1):
           s = fin.readline().strip()
           hour, minute = map(int, s.split(':'))
           if not (0 <= hour <= 10 and 0 <= minute <= 59):
               fout.write("Datele nu corespund restrictiilor impuse")
               return
           v[i] = (60 * hour + minute, i)
       v.sort()
       indici = []
       for i in range(1, n + 1):
           if v[i][0] <= t:
               t -= v[i][0]
               indici.append(v[i][1])
       indici.sort()
       fout.write(str(len(indici)) + '\n')
       fout.write(' '.join(map(str, indici)) + ' ')

if __name__ == "__main__":

   main()

</syntaxhighlight>