Difference between revisions of "Psihologia concursurilor de informatică/6 Probleme de concurs 2"

From Algopedia
Jump to: navigation, search
(Problema 7)
(Problema 7)
Line 15: Line 15:
 
'''Exemple''':
 
'''Exemple''':
  
{|class="wikitable
+
{|class="wikitable"
 
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
 
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
 
|-
 
|-

Revision as of 12:43, 9 March 2018

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul VI: Probleme de concurs (7-12)

Problema 7

Problema programării unui turneu de fotbal a fost dată spre rezolvare la a III-a Balcaniadă de Informatică, Varna 1995. Vom prezenta mai întâi enunțul nemodificat al problemei, după care vom adăuga câteva detalii care o vor face mai „provocatoare”.

ENUNȚ: Una din sarcinile Ministerului Sporturilor dintr-o țară balcanică este de a organiza un campionat de fotbal cu N echipe (numerotate de la 1 la N). Campionatul constă din N etape (dacă N este impar) sau N-1 etape (dacă N este par); orice două echipe dispută între ele un joc și numai unul. Scrieți un program care realizează o programare a campionatului.

Intrarea: Numărul de echipe N (2 ≤ N ≤ 24) va fi dat la intrarea standard (tastatură).

Ieșirea se va face în fișierul text OUTPUT.TXT sub forma unui tabel cu numere întregi avînd N linii. Al j-lea element din linia i este numărul echipei care joacă cu echipa i în etapa j (evident, dacă i joacă cu k în etapa j, atunci în tabel k joacă cu i în aceeași etapă). Dacă echipa i este liberă în etapa j, atunci al j-lea element al liniei i este zero.

Exemple:

INPUT.TXT OUTPUT.TXT
3 2 3 0

1 0 3
0 1 2

4 2 3 4

1 4 3
4 1 2
3 2 1

Timp de implementare: circa 1h 45’

Timp de execuție: 33 secunde

Iată și modificările pe care le propunem pentru a aduce cu adevărat problema la nivel de concurs:

  • Limita pentru numărul de echipe este N ≤ 200;
  • Timpul de implementare este de 45 minute;
  • Timpul de execuție este de 2-3 secunde;
  • Complexitatea cerută este O(N^{2}).

REZOLVARE: Vom lăsa pe seama cititorului conceperea, implementarea și testarea unei rezolvări backtracking (adoptată de majoritatea în timpul concursului). De altfel, la Balcaniadă concurenții au avut la dispoziție calculatoare 486 / 50 Mhz, iar un backtracking îngrijit funcționa cam până la N = 18 în timpul impus, ceea ce asigura cam 75% din punctajul maxim. În afară de aceasta, se mai puteau face și alte lucruri nu tocmai elegante, având în vedere că datele de ieșire nu erau foarte mari. Pentru N>18, mulți concurenți lăsau programul să meargă până când termina (câteva minute bune sau chiar mai mult), apoi scriau rezultatele într-un fișier temporar. Matricea rezultată era inclusă ca o constantă în codul sursă. Programul care era dat comisiei de corectare se prefăcea că „se gândește” timp de câteva secunde, apoi scria pur și simplu matricea în fișierul de ieșire. Cu aceasta s-au luat punctaje foarte apropiate de maxim. Totuși, pentru N=24 un backtracking ar fi stat foarte mult pentru a găsi soluția. Tot timpul acesta, calculatorul era blocat, neputând fi folosit. De aceea, mulți concurenți nu au luat punctajul maxim, preferând să renunțe la ultimele teste și să rezolve celelalte probleme. Oricum, backtracking-ul este în acest caz o soluție pentru care raportul punctaj obținut / timp consumat este foarte convenabil.

Există însă și o soluție care poate asigura un punctaj maxim fără bătăi de cap și fără să folosească „date preprocesate”. Ea are complexitatea O(N^{2}) și nu face decât o singură parcurgere a matricei de ieșire. Ce-i drept, autorul a pierdut cam trei ore pentru a o găsi și implementa în timp de concurs, compromițând aproape rezolvarea celorlalte două probleme din ziua respectivă, dar comisia de corectare a fost plăcut impresionată, programul fiind singurul care mergea instantaneu. Rămâne ca voi să alegeți între eleganță și eficiență...

Dacă ținem cont și de restricțiile suplimentare propuse, rezolvarea backtracking nu mai este valabilă. În această situație, iată care este metoda care stă la baza rezolvării în timp pătratic. În primul rând se reduce cazul când N este impar la un caz când N este par, prin mărirea cu 1 a lui N și introducerea unei echipe fictive. În fiecare etapă se consideră că echipa care trebuia să joace cu echipa fictivă stă de fapt „pe bară”. Iată de exemplu cum se rezolvă cazul N=3:

a) Se programează un campionat cu 4 echipe, echipa 4 fiind echipa fictivă:

Echipa Etapa 1 Etapa 2 Etapa 3
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

b) Se neglijează ultima linie din tabel, meciurile echipei fictive nefiind importante:

Echipa Etapa 1 Etapa 2 Etapa 3
1 2 3 4
2 1 4 3
3 4 1 2

c) Peste tot unde apare cifra 4, ea este înlocuită cu 0:

Echipa Etapa 1 Etapa 2 Etapa 3
1 2 3 0
2 1 0 3
3 0 1 2

Mai rămâne să vedem cum se tratează cazul când N este par. E destul de greu de dat o demonstrație matematică metodei care urmează; de fapt, nici nu există una, problema fiind rezolvată în timp de concurs prin inducție incompletă (adică s-a constatat cu creionul pe hârtie că metoda merge pentru N=4, 6, 8 și 10, apoi s-a scris programul care să facă același lucru și s-a constatat că merge și pentru valori mai mari). Să tratăm și aici cazul N=8, apoi să generalizăm procedeul.

Vor fi șapte etape și, fără a reduce cu nimic generalitatea problemei, putem presupune că echipa 1 joacă pe rând cu echipele 2, 3, 4, 5, 6, 7 și 8. Deocamdată tabelul arată astfel:

Echipa Etapa 1 Etapa 2 Etapa 3 Etapa 4 Etapa 5 Etapa 6 Etapa 7
1 2 3 4 5 6 7 8
2 1
3 1
4 1
5 1
6 1
7 1
8 1

Echipa 2 are deja programat un meci cu echipa 1 în prima etapă și mai are de programat meciurile cu echipele 3, 4, 5, 6, 7 și 8 în celelalte etape. Așezarea se poate face oricum, cu condiția ca echipele 1 și 2 să nu își aleagă același partener în aceeași etapă. De exemplu, putem programa meciul 2-3 în etapa a 3-a, meciul 2-4 în etapa a 4-a, ..., iar meciul 2-8 în etapa a 2-a. Astfel am completat linia a doua a tabloului:

Echipa Etapa 1 Etapa 2 Etapa 3 Etapa 4 Etapa 5 Etapa 6 Etapa 7
1 2 3 4 5 6 7 8
2 1 8 3 4 5 6 7
3 1 2
4 1 2
5 1 2
6 1 2
7 1 2
8 2 1

Echipa 3 are programate meciurile cu 1 și 2 și mai are de programat meciurile cu echipele 4, 5, 6, 7 și 8. Pentru a nu crea conflicte (adică două echipe să nu-și aleagă același adversar), putem aplica același procedeu: pornim de la etapa a 5-a și completăm toate celulele goale ale liniei a 3-a cu numerele de la 4 la 8, mergând circular spre dreapta:

Echipa Etapa 1 Etapa 2 Etapa 3 Etapa 4 Etapa 5 Etapa 6 Etapa 7
1 2 3 4 5 6 7 8
2 1 8 3 4 5 6 7
3 7 1 2 8 4 5 6
4 1 2 3
5 1 2 3
6 1 2 3
7 3 1 2
8 2 3 1

Se folosește aceeași metodă pentru a completa și celelalte linii ale matricei. Pentru fiecare linie i (iN-1):

  • Se caută pe linia i apariția valorii i-1;
  • Se caută primul spațiu liber (mergând circular spre dreapta). Primul spațiu liber înseamnă prima etapă în care se poate programa meciul dintre echipele i și i+1 (trebuie ca ambele să fie libere în acea etapă). Se constată experimental că trebuie început de la a doua poziție liberă de după apariția valorii i-1;
  • Se merge circular spre dreapta și, în căsuțele libere întâlnite se trec valorile i+1, i+2, ..., N. Concomitent, pe aceleași coloane ale liniilor i+1, i+2, ..., N se trece valoarea i.
Echipa Etapa 1 Etapa 2 Etapa 3 Etapa 4 Etapa 5 Etapa 6 Etapa 7
1 2 3 4 5 6 7 8
2 1 8 3 4 5 6 7
3 7 1 2 8 4 5 6
4 6 7 1 2 3 8 5
5 8 6 7 1 2 3 4
6 4 5 8 7 1 2 3
7 3 4 5 6 8 1 2
8 5 2 6 3 7 4 1

Fiecare linie a matricei poate fi parcursă in acest fel de maxim 2 ori (o dată pentru găsirea coloanei de start și o dată pentru completarea liniei), deci numărul total de celule vizitate este cel mult 2\times N^{2}. Complexitatea pătratică este cea optimă, deoarece programul trebuie în orice caz să tipărească la ieșire circa N^{2} numere.

#include <stdio.h>
#define NMax 200
unsigned char A[NMax+1][NMax+1];
int N,RealN;

void FindNextFree(int Line,int *K)
/* Cauta (circular) urmatorul spatiu liber pe linia Line */
{ do *K=*K%(N-1)+1;
  while (A[Line][*K]);
}

void MakeMatrix(void)
{ int i,j,k;

  for (i=1;i<=N;i++)
    for (j=1;j<=N;j++) A[i][j]=0;
  for (i=1;i<N;i++)  /* Pentru fiecare echipa */
    { if (i==1)      /* Alege coloana de start */
        j=1;
        else { j=0;
               do j++; while (A[i][j]!=i-1);
               FindNextFree(i,&j);
               FindNextFree(i,&j);
             }
      for (k=i+1;k<=N;k++) /* Completeaza circular linia */
        { A[i][j]=k;
          A[k][j]=i;
          if (k<N) FindNextFree(i,&j);
        }
    }
}

void WriteMatrix(void)
{ int i,j;
  FILE *F=fopen("output.txt","wt");

  for (i=1;i<=RealN;i++)
    { for (j=1;j<N;j++)
        fprintf(F,"%4d",A[i][j]>RealN ? 0 : A[i][j]);
      fprintf(F,"\n");
    }
  fclose(F);
}

void main(void)
{
  printf("N=");scanf("%d",&RealN);
  N=RealN+RealN%2; /* Se adauga 1 daca RealN e impar */
  MakeMatrix();
  WriteMatrix();
}