3298 - fmi orase2

Cerinţa

Suntem în anul 2050. Resursele de apă de pe planeta noastră sunt limitate din cauza schimbărilor climatice. Pentru ca toți locuitorii unui oraș să supraviețuiască în cazul unei catastrofe, orașul trebuie să aibă o rezervă de cel puțin 1 km^3 de apă. Pentru a face față mai ușor unor catastrofe, orașele pot forma alianțe în care se pot împrumuta reciproc cu apă. Astfel, într-o alianță formată din h orașe, fiecare oraș trebuie să aibă o rezervă de cel puțin h km^3 de apă (pentru a putea supraviețui toți locuitorii săi și a putea să împrumute cu câte 1 km^3 de apă fiecare dintre celelalte h - 1 orașe aliate).

Fiind dat numărul m de orașe și un șir de m numere naturale strict pozitive, notate cu c[1] c[2] ... c[m], unde fiecare număr c[i] reprezintă capacitatea maximă de stocare a orașului i, să se determine numărul maxim de orașe h care pot forma o alianță, adică există cel puțin h orașe care pot reține fiecare o cantitate de apă cel puțin egală cu h km^3.

Date de intrare

Fișierul de intrare fmi_orase2.in conține pe prima linie numărul m, iar pe a doua linie m numere naturale separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fișierul de ieșire fmi_orase2.out va conține pe prima linie numărul h, reprezentând cel mai mare număr de orașe care se pot alia. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

1 ≤ m ≤ 100
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000

Exemple

Exemplul 1

fmi_orase2.in: 5; 3 1 6 1 5
Ieșire: Datele sunt corecte.
fmi_orase2.out: 3

Exemplul 2

fmi_orase2.in: 5; 7 81 2 3 4
Ieșire: Datele sunt corecte.
fmi_orase2.out: 4

Exemplul 3

fmi_orase2.in: 2; 314441 41241241
Ieșire: Datele nu sunt comform restricțiilor impuse.

Rezolvare

3298 - fmi orase2

def orase(vector,m):

   f = open("fmi_orase2.out", "w")
   vector.sort(reverse=True)
   h = 0
   for i in range(m):
       h += 1
       if h >= vector[i]:
           break
   f.write(str(h))

def conform_restrictiilor():

   with open("fmi_orase2.in", "r") as f:
       m =  int(f.readline())
       vector = list(map(int, f.readline().split()))
       if not (1 <= m <= 100):
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
       for x in vector:
           if x >= 1000:
               print("Datele nu sunt conform restricțiilor impuse.")
               exit()
       print("Datele sunt corecte.")
       return vector, m

if __name__ == '__main__':

   vector , m = conform_restrictiilor()
   orase(vector , m)

</syntaxhighlight>