Fotbal

Problema este mai dificilă decât pare la prima vedere. Întâi vom calcula numărul de puncte obţinute de fiecare echipă, numărul total de goluri înscrise şi primite şi golaverajul. Vom sorta echipele după aceste criterii şi în continuare lucrăm cu acest clasament. Vom grupa echipe de pe poziţii consecutive dacă au obţinut acelaşi număr de puncte şi vom avea trei cazuri în funcţie de mărimea unei asemenea grupe:

  1. Dacă grupa are un singur element, echipa respectivă ocupă clar locul din clasament.
  2. Dacă grupa are două elemente, trebuie verificat meciul direct dintre cele două echipe. Dacă au jucat meci egal, se va verifica golaverajul, în caz de egalitate numărul golurilor înscrise, iar dacă şi acesta este egal se va da cu banul.
  3. Dacă grupa are trei sau patru elemente, vom apela recursiv procedura, numai pentru echipele respective. Limita pentru n garantează că în cel mai rău caz se va întâmpla un singur apel de acest gen.

Un caz special, care mai trebuie tratat este, când există o singură grupă, adică toate echipele au punctaj egal. Acest caz se tratează printr-o nouă grupare, de data asta după golaveraj şi atribuirea poziţiilor corespunzătoare pentru echipele din fiecare grupă.

Complexitatea finală este O(n2).

O altă soluţie foloseşte un vector în care se reţine pentru fiecare echipă numărul echipelor mai bune decât aceasta. Întâi, vom face clasamentul după punctajul obţinut. Dacă vor exista mai multe echipe la egalitate, vom marca aceste echipe într-un vector martor şi vom reface clasamentul separat pentru ele în funcţie de rezultatul direct, golaveraj şi numărul golurilor înscrise. În implementare, dacă una din aceste echipe este mai bună decât cealaltă, se va aduna încă o poziţie la valoarea curentă din vector. După acest pas, pentru a determina poziţia cea mai bună pentru fiecare dintre echipe vom număra pe câte poziţii apar valori strict mai mici. Pentru poziţia cea mai rea pe care o poate ocupă în clasament vom aduna toate valorile din vector mai mici sau egale.