3648 - Pitici

Cerința

În orașul Piticot locuiesc N pitici, fiecare într-o casă pe o stradă cu sens unic. Casele sunt așezate de-a lungul străzii, în sensul în care se circulă începând cu casa numerotată cu 1 până la casa numerotată cu N. În orașul Piticot piticii nu au un nume obișnuit! Ei poartă ca nume numărul casei în care stau. Neobișnuite sunt și casele lor! Dacă suni la soneria oricărei case depui atâta efort încât slăbești pe loc un număr de pitic-kilograme. Pentru că au constatat că în timpul pandemiei s-au îngrășat, fiecare și-a propus să slăbească un număr de pitic-kilograme, într-o singură zi. Pentru asta fiecare pitic va alerga pe stradă, plecând din propria casă și respectând sensul de deplasare al străzii iar în timpul alergării va suna la fiecare casă întâlnită, inclusiv la propria casă, o singură dată la fiecare. Ca regulă, suplimentară ei se vor opri din alergare în următoarele situații:

Orice pitic se va opri la prima casă la care, după ce a sunat, a constatat că a slăbit de când a pornit alergarea, cel puțin cât și-a propus; Orice pitic se va opri din alergare dacă a sunat la ultima casă (casa N), chiar dacă nu a reușit să slăbească cât și-a propus. Scrieți un program care determină care este numărul maxim de pitici care au sunat la o casă și la câte case s-a sunat de acest număr maxim de ori.

Date de intrare

Fișierul de intrare pitici.in conține pe prima linie numărul natural N. Pe a doua linie se găsesc N numere naturale A[i], reprezentând numărul de pitic-kilograme cu care orice pitic slăbește dacă sună la casa cu numărul i (1 ≤ i ≤ N). A treia linie conține N numere naturale B[i], reprezentând numărul de pitic-kilograme pe care piticul i dorește să îl slăbească. În cadrul unei linii datele sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire pitici.out conține pe prima linie numerele Max și Nr, separate prin-un spațiu, care reprezintă numărul maxim de pitici care au sunat la o casă, respectiv la câte case s-a sunat de număr maxim de ori.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ N ≤ 200.000
• 1 ≤ A[i] ≤ 1.000.000.000
• 1 ≤ B[i] ≤ 10^18
• A[i] ≤ B[i], pentru orice 1 ≤ i ≤ N.

Exemplu 1

Intrare

7
1 2 4 5 6 6 6
4 2 8 10 14 6 17

Iesire

2 6

Rezolvare

<syntaxhighlight lang="python" line> def citire_date():

   with open("pitici.in", "r") as f:
       N = int(f.readline().strip())
       A = list(map(int, f.readline().strip().split()))
       B = list(map(int, f.readline().strip().split()))
   return N, A, B

def calculeaza_max_pitici(N, A, B):

   case = [0] * (N + 1)
   
   for i in range(N):
       casa = i + 1
       while casa <= N and A[i] > 0:
           case[casa] += 1
           A[i] -= B[i]
           casa += 1
   
   max_pitici = max(case)
   numar_case = case.count(max_pitici)
   
   return max_pitici, numar_case

def scrie_rezultate(max_pitici, numar_case):

   with open("pitici.out", "w") as f:
       f.write(f"{max_pitici} {numar_case}\n")

def main():

   N, A, B = citire_date()

   # Verificarea restrictiilor
   assert 1 <= N <= 200000, "N trebuie sa fie intre 1 si 200.000"
   assert all(1 <= a <= 1000000000 for a in A), "Fiecare A[i] trebuie sa fie intre 1 si 1.000.000.000"
   assert all(1 <= b <= 1000000000 for b in B), "Fiecare B[i] trebuie sa fie intre 1 si 1.000.000.000"

   max_pitici, numar_case = calculeaza_max_pitici(N, A, B)
   scrie_rezultate(max_pitici, numar_case)

if __name__ == "__main__":

   main()

</syntaxhighlight>