pitici

Time limit: 0.1s
Memory limit: 64MB
Input: pitici.in
Output: pitici.out

În orașul Piticot locuiesc NN 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 11 până la casa numerotată cu NN. Î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 NN), chiar dacă nu a reușit să slăbească cât și-a propus.

Cerința

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 NN. Pe a doua linie se găsesc NN numere naturale AiA_i, reprezentând numărul de pitic-kilograme cu care orice pitic slăbește dacă sună la casa cu numărul i (1iN)i\ (1 \leq i \leq N). A treia linie conține NN numere naturale BiB_i, reprezentând numărul de pitic-kilograme pe care piticul ii 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 MaxMax și NrNr, 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

Restricții și precizări

  • 1N200 0001 \leq N \leq 200 \ 000
  • 1Ai1 000 000 0001 \leq A_i \leq 1 \ 000 \ 000 \ 000
  • 1Bi10181 \leq B_i \leq 10^{18}
  • AiBiA_i \leq B_i, pentru orice 1iN1 \leq i \leq N.

Exemplul

pitici.in

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

pitici.out

2 6

Explicație

Piticul 11 ca să slăbeasca cel puțin 44 pitic-kilograme sună la casele 1,21, 2 și 33. Piticul 22 sună doar la casa 22. Piticul 33 sună la casele 33 și 44. Piticul 44 sună la casele 44 și 55. Piticul 55 sună la casele 5,65, 6 și 77. Piticul 66 sună la casa 66 iar piticul 77 sună doar la casa 77 și nu reușește să slăbească cât și-a propus. Se observă că la casele 2,3,4,5,6,72, 3, 4, 5, 6, 7, s-a sunat de 22 ori, care este și numărul maxim de ori.

Problem info

ID: 1028

Editor: tvladm

Author:

Source: InfoPro, Etapa I, Grupa C1

Tags:

InfoPro Etapa I, Grupa C1

Log in or sign up to be able to send submissions!