ra

Time limit: 0.3s Memory limit: 128MB Input: ra.in Output: ra.out

Se dă nn și un șir a1,a2,ana_1, a_2, \dots a_n de numere naturale. Inițial, toate numerele sunt colorate în roșu\textcolor{red}{roșu}. Într-o operație, poți să alegi un număr roșu\textcolor{red}{roșu} și să îl faci albastru\textcolor{blue}{albastru}.

Cerință

Află numărul minim de operații pe care trebuie să le faci astfel încât suma numerelor albastre\textcolor{blue}{albastre} să fie strict mai mare decât suma numerelor roșii\textcolor{red}{roșii}.

Date de intrare

Pe prima linie a fișierului de intrare ra.in se află numărul nn. Pe a doua linie se află șirul a1,a2,,ana_1, a_2, \dots, a_n.

Date de ieșire

Să se afișeze în fișierul ra.out numărul minim de operații astfel încât suma numerelor albastre să fie strict mai mare decât suma celor roșii.

Restricții și precizări

  • 2n10 0002 \leq n \leq 10 \ 000
  • 1ai1091 \leq a_i \leq 10^9
# Punctaj Restricții
1 60 ai1 000a_i \leq 1 \ 000
2 40 Fără restricții suplimentare

Exemplul 1

ra.in

5
2 4 2 6 7

ra.out

2

Explicație

La primul exemplu, inițial șirul arată astfel: 2 4 2 6 7\textcolor{red}{2 \ 4 \ 2 \ 6 \ 7}.

Suma valorilor roșii este 2+4+2+6+7=212 + 4 + 2 + 6 + 7 = 21.

Suma valorilor albastre este 00 (deoarece nu am colorat niciun element în albastru).

În prima operație, vom alege elementul de pe a doua poziție să îl colorăm în albastru.

Acum șirul nostru arată astfel: 2 4 2 6 7\textcolor{red}{2} \ \textcolor{blue}{4} \ \textcolor{red}{2 \ 6 \ 7}. Suma valorilor roșii este 2+2+6+7=172 + 2 + 6 + 7 = 17, iar suma valorilor albastre este 44.

În a doua operație, vom alege elementul de pe ultima poziție și îl vom colora în albastru.

Șirul devine: 2 4 2 6 7\textcolor{red}{2} \ \textcolor{blue}{4} \ \textcolor{red}{2 \ 6} \ \textcolor{blue}{7}. Are suma valorilor roșii 2+2+6=102 + 2 + 6 = 10 și suma valorilor albastre 4+7=114 + 7 = 11. Deci, suma valorilor albastre\textcolor{blue}{albastre} este strict mai mare decât a celor roșii\textcolor{red}{roșii}.

Observăm că dacă am fi colorat numerele 66 și 77 în albastru, am obține o altă soluție cu 22 operații.

Exemplul 2

ra.in

10
6 3 8 4 5 6 5 5 7 5

ra.out

5

Explicație

Pentru al doilea exemplu, obținem o soluție cu 55 operații dacă colorăm valorile 88, 77, 66, 66, 55 (observăm că doar unul dintre valorile de 55 va fi colorat în albastru).

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