// solutie recursiva liata de pe infoarena (asta este cea cu cautare binara)
// O limita superioara pentru numarul de grupuri este S / K unde S reprezinta suma canitatilor de animale. Este evident ca, daca putem construi X grupuri, putem construi si Y ≤ X grupuri, fapt care ne duce la ideea sa cautam binar numarul de grupuri. Pentru a verifica daca putem construi un numar de grupuri X ne imaginam completarea unei matrice cu X linii si K coloane, fiecare linie reprezetand un grup. Din restrictiile problemei elementele de pe fiecare linie trebuie sa fie distincte. Vom completa aceasta matrice coloana cu coloana, pentru fiecare cantitate de animale daca este ≤ X le punem pe toate in matrice, daca este > X punem doar X in matrice (deoarece daca punem mai multe vor fi cel putin doua pe aceeasi linie). Pentru primul exemplu din enunt, matricea se va completa astfel:
//Asadar , daca in final am putut completa toata matricea se pot forma X grupuri. Este evident ca strategia folosita de verificare este optima. Completarea matricei se face doar conceptual, verificarea avand complexitatea O(N) prin parcurgerea vectorului A, rezultand un algoritm de complexitate O(N lg(S/K)).Pe baza algoritmului descris mai sus, se poate obtine un algoritm O(N), desi acesta n-ar fi fost necesar pentru 100 de puncte.
//Algoritmul lucreaza astfel: daca cel mai mare element este ≤ S/K , verificarea prezentata mai sus ne garanteaza ca vom putea obtine S/K grupuri, toate elementele fiind ≤ S/K se vor folosi toate S, iar matricea este (S/K)*K = S. Daca cel mai mare element este > S atunci putem rezolva aceeasi problema recursiv pentru cantitatile existente mai putin cea mai mare si grupuri de marime K-1. Acest rezultat va fi mai mic sau egal cu cel mai mare element, deci ne va ajunge pentru a completa grupurile la marimea K. Deoarece canitatile sunt date sortate, complexitatea este O(N).

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("grupuri.in");
ofstream g("grupuri.out");

int n, k;
long long a[100005];
int main(){

  f >> k >> n;
  long long s = 0;
  for(int i=1; i<=n; i++){
    f>>a[i];
    s += a[i];
  }
  int sol;
  long long left = 1, right = s / k;
  while(left <= right){
    long long mid = (left + right) / 2;
    long long suma = 0;
    for(int i=1; i <= n; i++){
      suma += min(a[i], mid);
    }
    if(suma >= mid * k){
      sol = mid;
      left = mid + 1;
    }
    else{
      right = mid - 1;
    }
  }
  g << sol;
}