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

From Algopedia
Jump to: navigation, search
Line 869: Line 869:
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
== Problema 4 ==
 +
 +
Continuăm cu o problemă care a fost de asemenea dată spre rezolvare la a VIII-a Olimpiadă Internațională de Informatică, Veszprem 1996. Problema în sine nu a fost foarte grea și mulți elevi au luat punctaj maxim. Totuși, enunțul permite unele modificări interesante care practic schimbă cu totul problema.
 +
 +
'''ENUNȚ''': Să considerăm următorul joc de două persoane. Tabla de joc constă într-o secvență de întregi pozitivi. Cei doi jucători mută pe rând. Mutarea fiecărui jucător constă în alegerea unui număr de la unul din cele două capete ale secvenței. Numărul ales este șters de pe tablă. Jocul se termină când toate numerele au fost selectate. Primul jucător câștigă dacă suma numerelor alese de el este mai mare sau egală cu cea a numerelor alese de cel de-al doilea jucător. În caz contrar, câștigă al doilea jucător.
 +
 +
Dacă tabla conține inițial un număr par de elemente, atunci primul jucător are o strategie de câștig. Trebuie să scrieți un program care implementează strategia cu care primul jucător câștigă jocul. Răspunsurile celui de-al doilea jucător sunt date de un program rezident. Cei doi jucători comunică prin trei proceduri ale modulului <tt>Play</tt> care v-a fost pus la dispoziție. Procedurile sunt <tt>StartGame</tt>, <tt>MyMove</tt> și <tt>YourMove</tt>. Primul jucător începe jocul apelând procedura fără parametri <tt>StartGame</tt>. Dacă alege numărul de la capătul din stânga, el va apela procedura <tt>MyMove('L')</tt>. Analog, apelul de procedură <tt>MyMove('R')</tt> trimite un mesaj celui de-al doilea jucător prin care îl informează că a ales numărul de la capătul din dreapta. Cel de-al doilea jucător, deci computerul, mută imediat, iar primul jucător poate afla mutarea acestuia executând procedura <tt>YourMove(C)</tt>, unde <tt>C</tt> este o variabilă de tip <tt>Char</tt> (în C/C++ apelul este <tt>YourMove(&C)</tt>). Valoarea lui <tt>C</tt> este <tt>'L'</tt> sau <tt>'R'</tt>, după cum numărul ales este de la capătul din stânga sau din dreapta.
 +
 +
'''Intrarea''': Prima linie din fișierul <tt>INPUT.TXT</tt> conține dimensiunea inițială '''''N''''' a tablei. '''''N''''' este par și 2 ≤ '''''N''''' ≤ 100. Următoarele '''''N''''' linii conțin fiecare câte un număr, reprezentând conținutul tablei de la stânga la dreapta. Fiecare număr este cel mult 200.
 +
 +
'''Ieșirea''': Când jocul se termină, programul trebuie să scrie rezultatul final în fișierul <tt>OUTPUT.TXT</tt>. Fișierul conține două numere pe prima linie, reprezentând suma numerelor alese de primul, respectiv de cel de-al doilea jucător. Programul trebuie să joace un joc corect și ieșirea trebuie să corespundă jocului jucat.
 +
 +
'''Exemplu''':
 +
 +
{|class="wikitable
 +
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
 +
|-
 +
| <tt>6<br>4<br>7<br>2<br>9<br>5<br>2</tt>
 +
| <tt>15 14</tt>
 +
|}
 +
 +
'''Timp limită de execuție''': 20 secunde pentru un test.
 +
 +
Acesta a fost enunțul original, la care va trebui să facem câteva modificări, în parte deoarece nu putem folosi modulul <tt>Play</tt>, în parte pentru a face problema mai restrictivă:
 +
 +
* Mutările vor fi anunțate pe ecran prin tipărirea unui caracter <tt>'L'</tt> sau <tt>'R'</tt>;
 +
* Mutările celui de-al doilea jucător vor fi comunicate de un partener uman, prin introducerea de la tastatură a unui caracter <tt>'L'</tt> sau <tt>'R'</tt>;
 +
* Rezultatul final se va tipări pe ecran, sub aceeași formă (pereche de numere).
 +
* Timpul de gândire pentru fiecare mutare trebuie să fie cât mai mic (practic răspunsul să fie instantaneu);
 +
* '''Complexitatea totală''' a calculelor efectuate să fie <math>O(N)</math>.
 +
* '''Timpul de implementare''' a fost cam de 1h 40 min. Propunem reducerea lui la 30 minute.
 +
 +
'''REZOLVARE''': Este ușor de demonstrat că o rezolvare „greedy” a problemei (la fiecare mutare jucătorul 1 alege numărul mai mare) nu atrage întotdeauna câștigul. Iată un contraexemplu:
 +
 +
[[File:Psycho-fig49.png]]
 +
 +
La prima mutare, jucătorul 1 poate să aleagă fie numărul 7, fie numărul 2. Dacă se va „lăcomi” la 7, jucătorul 2 va lua numărul 10 și inevitabil va câștiga. Soluția pentru primul jucător este să ia numărul 2, apoi, indiferent de ce va juca partenerul său, va putea lua numărul 10 și va câștiga.
 +
 +
Iată o soluție izbitor de simplă de complexitate <math>O(N)</math>: La citirea datelor se face suma elementelor aflate pe poziții pare și a celor aflate pe poziții impare. Să presupunem că suma elementelor de ordin par este mai mare sau egală cu cea a elementelor de ordin impar (cazul invers se tratează analog). Atunci, dacă primul jucător ar putea să aleagă toate elementele de ordin par (care sunt într-adevăr '''''N'''''/2, adică atâtea câte are el dreptul să aleagă), ar câștiga jocul. Jucătorul 1 poate începe jocul prin a lua primul sau ultimul element din secvență, deci îl va alege pe ultimul, care are număr de ordine par. Al doilea jucător are de ales între primul și al '''''N'''''-1-lea element, ambele având număr de ordine impar. Indiferent ce variantă o va adopta, primul jucător va avea din nou acces la un element de pe o poziție pară. Dacă jucătorul 2 alege elementul din stânga (primul), atunci jucătorul 1 va putea lua elementul de după el (al doilea), iar dacă jucătorul 2 alege elementul din dreapta (al '''''N'''''-1-lea), atunci jucătorul 1 va putea lua elementul dinaintea el (al '''''N'''''-2-lea). Deci primul jucător nu are altceva de făcut decât să repete mutările făcute de cel de-al doilea. Să privim de exemplu desfășurarea jocului pe tabla dată în enunț:
 +
 +
[[File:Psycho-fig50.png]]
 +
 +
Programul în sine nici nu are nevoie să mai rețină vectorul de numere în memorie, din moment ce primul jucător nu are altceva de făcut decât să imite mutările celui de-al doilea. Un calcul al sumelor la citirea datelor este suficient. Complexitatea <math>O(N)</math> este optimă, deoarece vectorul trebuie parcurs cel puțin o dată pentru citirea configurației inițiale a tablei.
 +
 +
<syntaxhighlight lang="c">
 +
#include <stdio.h>
 +
 +
void main(void)
 +
{ FILE *F=fopen("input.txt","rt");
 +
  int SEven,SOdd,N,i,K;
 +
 +
  fscanf(F,"%d\n",&N);
 +
  for (i=1, SEven=SOdd=0; i<=N; i++)
 +
    { fscanf(F, "%d\n", &K);
 +
      if (i&1) SOdd+=K;
 +
        else SEven+=K;
 +
    }
 +
  fclose(F);
 +
 +
  printf("Mutarea mea: %c\n", SEven>=SOdd ? 'R' : 'L');
 +
  for (i=1; i<N/2; i++)
 +
    { printf("Mutarea dvs. (L/R) ? ");
 +
      printf("Mutarea mea: %c\n", getchar());
 +
      getchar(); /* Caracterul newline */
 +
    }
 +
  printf("Mutarea dvs. (L/R) ? ");
 +
  getchar();
 +
 +
  if (SEven>=SOdd)
 +
    printf("%d %d\n", SEven, SOdd);
 +
    else printf("%d %d\n", SOdd, SEven);
 +
}
 +
</syntaxhighlight>
 +
 +
O a doua variantă a enunțului aduce unele condiții suplimentare:
 +
 +
* Se cere să se tipărească numai diferența maximă de scor pe care o poate obține primul jucător, considerând că ambii parteneri joacă perfect;
 +
* '''Complexitatea cerută''' este <math>O(N^2)</math>.
 +
* '''Timpul de implementare''' este de 45 minute, maxim 1h.
 +
 +
 +
'''REZOLVARE''': Trebuie mai întâi să lămurim ce se înțelege prin „joc perfect”. Jucătorul 1 are întotdeauna victoria la îndemână (metoda este arătată mai sus), dar nu la orice scor. Jucătorul 2 urmărește să minimizeze diferența de scor. Fie '''''D''''' diferența de scor cu care se termină un joc. '''''D''''' poate lua diferite valori pentru aceeași configurație inițială a tablei, în funcție de mutările făcute de cei doi jucători. Fie <math>D_{MAX}</math> diferența maximă de scor pe care o poate obține primul jucător indiferent de mutările celui de-al doilea. Exact această valoare trebuie aflată. <math>D_{MAX}</math> nu este propriu-zis o diferență maximă. Jucătorul 1 poate să câștige și la diferențe mai mari decât <math>D_{MAX}</math>, dar trebuie ca jucătorul 2 să-l „ajute”. Să reluăm exemplul cu 4 numere:
 +
 +
[[File:Psycho-fig51.png]]
 +
 +
În acest caz, primul jucător are asigurat scorul 12-8 (deci diferența 4). Pentru aceasta, el începe prin a lua numărul 2, apoi, orice ar replica celălalt, va lua numărul 10, jucătorului 2 revenindu-i așadar numerele 1 și 7. El poate obține și scorul 17-3 (jucătorul 1 ia numărul 7, celălalt ia 2, jucătorul 1 ia 10, iar celălalt ia 1), dar aceasta se întâmplă numai dacă jucătorul 2 face o greșeală. După cum am arătat mai sus, dacă primul jucător începe luând numărul 7, el pierde în mod normal partida. Iată deci că în acest caz <math>D_{MAX}=4</math>.
 +
 +
Pentru a putea afla diferența maximă de scor, este bine să privim mereu în adâncime. Există patru variante în care ambii parteneri pot face câte o mutare:
 +
 +
# Ambii jucători aleg numere din partea stângă;
 +
# Ambii aleg numere din partea dreaptă;
 +
# Primul jucător alege numărul din stânga, iar celălalt pe cel din dreapta;
 +
# Primul jucător alege numărul din dreapta, iar celălalt pe cel din stânga;
 +
 +
În urma oricărei variante de mutare, secvența se scurtează cu două elemente. Dacă am putea cunoaște dinainte care este rezultatul jocului pentru fiecare din secvențele scurte, am putea să decidem care variantă de joc este cea mai convenabilă pentru secvența inițială, ținând cont și de modul de joc al jucătorului al doilea. Tocmai de aici vine și ideea de rezolvare. Să notăm cu '''''A'''''[1], '''''A'''''[2], ..., '''''A'''''['''''N'''''] secvența citită la intrare. Vom construi o matrice '''''D''''' cu '''''N''''' linii și '''''N''''' coloane, unde '''''D'''''['''''i''''','''''j'''''] este diferența maximă pe care o poate obține jucătorul 1 pentru secvența '''''A'''''['''''i'''''], '''''A'''''['''''i'''''+1], ...,  '''''A'''''['''''j''''']. Bineînțeles, sunt luate în considerare numai secvențele de lungime pară. Scopul nostru este să-l aflăm pe '''''D'''''[1,'''''N'''''].
 +
 +
Elementele matricei pe care le putem afla fără multă bătaie de cap sunt '''''D'''''[1,2], '''''D'''''[2,3], ..., '''''D'''''['''''N'''''-1,'''''N''''']. Într-adevăr, dintr-o secvență de numai două numere, primului jucător îi revine cel mai mare, iar celui de-al doilea - cel mai mic. Așadar
 +
 +
<math>D[i,i + 1] = |A[i] - A[i + 1]|</math>
 +
 +
Cum calculăm '''''D'''''['''''i''''','''''j'''''] dacă cunoaștem valorile matricei '''''D''''' pentru toate subsecvențele incluse în secvența '''''A'''''['''''i'''''], '''''A'''''['''''i'''''+1], ...,  '''''A'''''['''''j'''''] ? După cum am mai spus, avem patru variante:
 +
 +
[[File:Psycho-fig52.png]]
 +
 +
Trebuie să ținem minte că, dacă primul jucător optează să-l aleagă pe A[i] (una din primele două variante), atunci jucătorul 2 va juca în așa fel încât pierderea să fie minimă, iar scorul final va fi <math>\min(R_1,R_2)</math>. Dacă jucătorul 1 alege varianta 3 sau 4, scorul final va fi <math>\min(R_3,R_4)</math>. Dar jucătorul 1 este primul la mutare, deci va alege varianta care îi maximizează profitul. Rezultatul este
 +
 +
<math>D[i,j] = \max(\min(R_1, R_2), \min(R_3, R_4))</math>
 +
 +
adică
 +
 +
<math>
 +
\begin{align}
 +
D[i,j] = \max( & A[i] + \min(D[i + 2, j] - A[i + 1], D[i + 1, j - 1] - A[j]), \\
 +
              & A[j] + \min(D[i + 1, j - 1] - A[i], D[i, j - 2] - A[j - 1]))
 +
\end{align}
 +
</math>
 +
 +
Matricea D se completează pe diagonală, pornind de la diagonala principală și mergând până în colțul de N-E. Iată cum arată matricea atașată datelor de intrare din enunț:
 +
 +
<math>
 +
D =
 +
\begin{pmatrix}
 +
X & 3 & X & 10 & X & 7 \\
 +
X & X & 5 & X & 9 & X \\
 +
X & X & X & 7 & X & 4 \\
 +
X & X & X & X & 4 & X \\
 +
X & X & X & X & X & 3 \\
 +
X & X & X & X & X & X
 +
\end{pmatrix}
 +
</math>
 +
 +
Pentru exemplul din enunț, răspunsul este deci <math>D_{MAX}=7</math>. Cum elementele matricei sunt parcurse cel mult o dată, rezultă o complexitate de <math>O(N^2)</math>.
 +
 +
<syntaxhighlight lang="c">
 +
#include <stdio.h>
 +
#include <stdlib.h>
 +
#define NMax 101
 +
 +
int D[NMax][NMax], A[NMax], N;
 +
 +
void ReadData(void)
 +
{ FILE *F=fopen("input.txt","rt");
 +
  int i;
 +
 +
  fscanf(F,"%d\n",&N);
 +
  for (i=1; i<=N;)
 +
    fscanf(F, "%d\n", &A[i++]);
 +
  fclose(F);
 +
}
 +
 +
int Min(int A, int B)
 +
{
 +
  return A<B ? A : B;
 +
}
 +
 +
int Max(int A, int B)
 +
{
 +
  return A>B ? A : B;
 +
}
 +
 +
void FindMax(void)
 +
{ int i,j,k;
 +
 +
  for (i=1;i<N;i++)
 +
    D[i][i+1]=abs(A[i]-A[i+1]);
 +
  for (k=3;k<=N-1;k++)
 +
    for (i=1;i+k<=N;i++)
 +
      { j=i+k;
 +
        D[i][j]=Max(A[i]+Min(D[i+2][j]-A[i+1],
 +
                            D[i+1][j-1]-A[j]),
 +
                    A[j]+Min(D[i+1][j-1]-A[i],
 +
                            D[i][j-2]-A[j-1]));
 +
      }
 +
  printf("Diferenta maxima este %d\n",D[1][N]);
 +
}
 +
 +
void main(void)
 +
{
 +
  ReadData();
 +
  FindMax();
 +
}
 +
</syntaxhighlight>
 +
 +
Programul prezentat mai sus poate fi optimizat, dacă timpul o permite și dacă acest lucru este necesar. Lăsăm cititorul să încerce să rezolve aceeași problemă folosind o cantitatate de memorie direct proporțională cu '''''N'''''.

Revision as of 08:41, 9 March 2018

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul VI: Probleme de concurs

Problema 1

ENUNȚ: Se consideră următorul joc: Pe o tablă liniară cu 2N+1 căsuțe sunt dispuse N bile albe (în primele N căsuțe) și N bile negre (în ultimele N căsuțe), căsuța din mijloc fiind liberă. Bilele albe se pot mișca numai spre dreapta, iar cele negre numai spre stânga. Mutările posibile sunt:

  1. O bilă albă se poate deplasa o căsuță spre dreapta, numai dacă aceasta este liberă;
  2. O bilă albă poate sări peste bila aflată imediat în dreapta ei (indiferent de culoarea acesteia), așezându-se în căsuța de dincolo de ea, numai dacă aceasta este liberă;
  3. O bilă neagră se poate deplasa o căsuță spre stânga, numai dacă aceasta este liberă;
  4. O bilă neagră poate sări peste bila aflată imediat în stânga ei (indiferent de culoarea acesteia), așezându-se în căsuța de dincolo de ea, numai dacă aceasta este liberă.

Trebuie schimbat locul bilelor albe cu cele negre. Se mai cere în plus ca prima mutare să fie făcută cu o bilă albă.

Intrarea: De la tastatură se citește numărul N ≤ 1000.

Ieșirea: În fișierul OUTPUT.TXT se vor tipări două linii terminate cu <Enter>. Pe prima se va tipări numărul de mutări efectuate, iar pe a doua o succesiune de cifre cuprinse între 1 și 4, nedespărțite prin spații, corespunzătoare mutărilor ce trebuie făcute.

Exemple:

  • N=1 ⇒ Ieșirea "141"
  • N=2 ⇒ Ieșirea "14322341"

Complexitate cerută: O(N^{2}).

Timp de implementare: 1h.

Timp de rulare: 10 secunde pentru un test.

REZOLVARE: La prima vedere, problema pare să se preteze la o rezolvare în timp exponențial, prin metoda „Branch and Bound”. Un neajuns al enunțului pare să fie faptul că nu se specifică dacă numărul de mutări efectuate trebuie sau nu să fie minim. Pentru a ne lămuri, să privim în detaliu soluțiile pentru N=1 și N=2:

  • Pentru N = 1, toate mutările sunt forțate ((a) - se mută bila albă, (b) - se sare cu cea neagră peste ea, (c) - se mută din nou bila albă); trebuie remarcat că după mutările (a) și (b) se obțin două configurații simetrice una în raport cu cealaltă (oglindite).
  • Pentru N = 2, se poate începe sărind cu bila albă de la margine peste cealaltă, dar această mutare ar duce la blocarea jocului. Este deci obligatoriu să se înceapă prin a împinge bila albă centrală (a). Următoarea mutare este forțată ((b) - se sare cu bila neagră peste cea albă), apoi toate mutările sunt obligate (în sensul că dacă la orice pas se face altă mutare decât cea care conduce la soluție, jocul se blochează în câteva mutări): (c) - se împinge bila neagră, (d), (e) - se sare de două ori cu bilele albe, (f) - se împinge bila neagră, (g) - se sare cu bila neagră, (h) - se împinge bila albă. Trebuie din nou remarcat că după mutările (c) și (e) se obțin două configurații simetrice.

Așadar în ambele cazuri, soluția este unică. De fapt, există două soluții asemănătoare, una dacă se începe cu o mutare a bilei albe și una dacă se începe cu o mutare a bilei negre. Fiindcă enunțul impune ca prima mutare să se facă cu o bilă albă, soluția este unică. Se mai observă și că, atât pentru N=1 cât și pentru N=2 șirul de mutări este simetric. Pentru a indica efectiv modul de determinare a soluției (care va sugera și ideea de scriere a programului) și pentru a explica observațiile de mai sus, să generalizăm observațiile făcute pentru un N oarecare.

  • Configurația inițială este:
Psycho-fig32.png
  • Se împinge bila albă și se sare cu cea neagră peste ea (șirul de mutări 14):
Psycho-fig33.png
  • Se împinge bila neagră și se sare de două ori cu cele albe peste ea (șirul de mutări 322):
Psycho-fig34.png
  • Se împinge bila albă și se sare de trei ori cu cele negre peste ea (șirul de mutări 1444):
Psycho-fig35.png
  • Se împinge bila neagră și se sare de patru ori cu cele albe peste ea (șirul de mutări 32222):
Psycho-fig36.png
...
  • Se împinge bila albă (mutarea 1)
Psycho-fig37.png
  • Se sare de N ori cu cele negre peste ea (șirul de mutări 44..44):
Psycho-fig38.png

Ultimele două configurații sunt simetrice. În acest moment șirul de mutări se inversează:

  • Se împinge bila albă (mutarea 1):
Psycho-fig39.png

...

  • Se sare de patru ori cu bilele albe și se împinge bila neagră (șirul de mutări 22223):
Psycho-fig40.png
  • Se sare de trei ori cu bilele negre și se împinge bila albă (șirul de mutări 4441):
Psycho-fig41.png
  • Se sare de două ori cu bilele albe și se împinge bila neagră (șirul de mutări 223):
Psycho-fig42.png
  • Se sare cu bila neagră și se împinge bila albă (șirul de mutări 41), obținându-se configurația finală:
Psycho-fig43.png

În concluzie, șirul de mutări este: o împingere - un salt - o împingere - două salturi - o împingere - trei salturi - ... - o împingere - N-1 salturi - o împingere - N salturi - o împingere - N-1 salturi - ... - o împingere - trei salturi - o împingere - două salturi - o împingere - un salt - o împingere, culorile alternând la fiecare pas.

Pentru a calcula numărul de mutări, putem să le numărăm pe măsură ce le efectuăm, dar deoarece se cere afișarea mai întâi a numărului de mutări și după aceea a mutărilor în sine, trebuie fie să stocăm toate mutările în memorie, fie să lucrăm cu fișiere temporare, ambele variante putând duce la complicații nedorite. Din fericire, numărul de mutări se poate calcula cu ușurință astfel: fiecare piesă albă trebuie mutată în medie cu N pași către dreapta și fiecare piesă neagră trebuie mutată cu N pași către stânga. Deci numărul total de pași este 2N(N+1). Din secvența generală de mutări expusă mai sus se observă că nu se fac decât 2N împingeri de piese (mutări de un singur pas), restul fiind salturi (mutări de câte doi pași). Deci numărul de mutări este:

2N+{\frac  {2N(N+1)-2N}{2}}=2N+N^{2}=N(N+2)

De aici deducem că nu există un algoritm mai bun decât O(N^{2}), deoarece numărul de mutări este O(N^{2}). Propunem ca temă cititorului să demonstreze că nu există decât două succesiuni de mutări care rezolvă problema, din care una începe cu mutarea unei piese albe, iar cealaltă este oglindirea ei și începe cu mutarea unei piese negre, deci nu poate constitui o soluție corectă. Demonstrația începe prin a arăta că sunt necesare cel puțin 2N împingeri de piese. Această demonstrație explică de ce nu se cere un număr minim de mutări în enunț - cerința nu ar avea sens întrucât soluția este oricum unică. Acestea fiind zise, programul arată astfel:

#include <stdio.h>
int N;
FILE *OutF;

void Jump(int Level, char A, char B)
{ int i;
  putc(A,OutF);
  for (i=1;i<=Level;i++) putc(B,OutF);
  if (Level<N)
    {
      Jump(Level+1,'1'+'2'-A,'4'+'3'-B);
      for (i=1;i<=Level;i++) putc(B,OutF);
    }
  putc(A,OutF);
}

void main(void)
{
  printf("N=");scanf("%d",&N);
  OutF=fopen("output.txt","wt");
  fprintf(OutF,"%ld\n",(long)N*(N+2));
  Jump(1,'1','4');
  fprintf(OutF,"\n");
  fclose(OutF);
}


Problema 2

Problema următoare a fost propusă la a VI-a Olimpiadă Internațională de Informatică, Stockholm 1994. Este și ea un bun exemplu de situație în care putem cădea în plasa unei rezolvări „Branch and Bound” atunci când nu este cazul.

ENUNȚ: Se dă o configurație de 3 x 3 ceasuri, fiecare având un singur indicator care poate arăta numai punctele cardinale (adică orele 3, 6, 9 și 12). Asupra acestor ceasuri se poate acționa în nouă moduri distincte, fiecare acțiune însemnând mișcarea limbilor unui anumit grup de ceasuri în sens orar cu 90°. În figura de mai jos se dă un exemplu de configurație inițială a ceasurilor și se arată care sunt cele nouă tipuri de mutări (pentru fiecare tip de mutare se mișcă numai ceasurile reprezentate hașurat).

Psycho-fig44.png

Se cere ca, într-un număr minim de mutări, să aducem toate indicatoarele la ora 12.

Intrarea se face din fișierul INPUT.TXT, care conține configurația inițială sub forma unei matrice 3 x 3. Pentru fiecare ceas se specifică câte o cifră: 0 = ora 12, 1 = ora 3, 2 = ora 6, 3 = ora 9.

Ieșirea se va face în fișierul OUTPUT.TXT sub forma unui șir de numere între 1 și 9, pe un singur rând, separate prin spațiu, reprezentând șirul de mutări care aduc ceasurile în starea finală. Se cere o singură soluție.

Exemplu: Pentru figura de mai sus, fișierul INPUT.TXT este

3 3 0
2 2 2
2 1 2

iar fișierul OUTPUT.TXT ar putea fi:

5 8 4 9

Timp de implementare: 1h - 1h 15min.

Timp de rulare: o secundă.

Complexitate cerută: O(1) (timp constant).

REZOLVARE: Din câte am văzut pe la concursuri, peste jumătate din elevi s-ar apuca direct să implementeze o rezolvare Branch and Bound la această problemă, fără să-și mai bată capul prea mult. Există argumente în favoarea acestei inițiative:

  • Mulți preferă să nu mai piardă timpul căutând o altă soluție, mai ales că problema seamănă mult cu „Lampa lui Dario Uri” (care de fapt este exact problema ceasurilor, dar în care ceasurile au doar două stări în loc de patru). În plus, se știe că pe cazul general al unei table N x N, cele două probleme nu admit rezolvări polinomiale și atunci cea mai sigură soluție este prin tehnica Branch and Bound.
  • De asemenea, se observă că numărul total de configurații posibile pentru o tablă cu 9 ceasuri este de 4^{9}, adică aproximativ un sfert de milion. Un algoritm Branch and Bound ar furniza așadar o soluție în timp rezonabil. Raționamentul multor elevi este „decât să pierd timpul căutând o soluție mai bună, fără să am certitudinea că o voi găsi, mai bine folosesc timpul implementând un Branch care măcar știu sigur că merge”.
  • Problema cere o soluție într-un număr minim de pași, lucru care îi cam descurajează pe cei care încă ar vrea să caute alte rezolvări. „Alte rezolvări” înseamnă de obicei un Greedy comod de implementat, iar asupra rezolvărilor Greedy se poartă întotdeauna discuții interminabile pe culoarele sălilor de concurs referitor la „cât de bune sunt” (adică în cât la sută din cazuri furnizează soluția optimă).

Se pierd însă din vedere unele lucruri esențiale. În primul rând, tabla nu este de N x N, ci are dimensiuni fixate, 3 x 3. În al doilea rând, implementarea unui Branch and Bound în timp de concurs este o aventură nu tocmai ușor de dus la bun sfârșit (personal mi-a fost frică să o încerc vreodată). În sfârșit, după cum se va vedea mai jos, problema șirului minim de transformări este o pseudo-problemă, deoarece soluția simplă este oricum unică.

Ce se înțelege prin „soluție simplă”? Să remarcăm două lucruri:

  1. Aplicarea de patru ori a aceleiași mutări nu schimbă nimic în configurația ceasurilor. Într-adevăr, mutarea va afecta de fiecare dată același grup de ceasuri, iar aplicarea de patru ori va roti fiecare indicator cu 360°, adică îl va aduce în poziția inițială. Din acest motiv, toate afirmațiile făcute în cele ce urmează vor fi valabile în algebra modulo 4.
  2. Ordinea în care se aplică transformările nu contează.

În consecință, prin „soluție simplă” se înțelege un șir de mutări ordonat crescător în care nici o mutare nu apare de mai mult de trei ori. Să demonstrăm acum că soluția simplă este unică.

Fie A\in M_{3}({\mathbb  {Z}}_{4}) matricea citită de la intrare, unde a_{{i,j}} arată de câte ori a fost rotit ceasul C_{{i,j}} peste ora 12. Fie matricea B\in M_{3}({\mathbb  {Z}}_{4}),b_{{i,j}}=4-a_{{i,j}}. Matricea B arată de câte ori mai trebuie rotit fiecare ceas până la ora 12. O soluție înseamnă a efectua fiecare din cele 9 mutări de un număr de ori, p_{1},p_{2},\dots ,p_{9}. Cum afectează aceste mutări ceasurile? Se poate deduce ușor:

Ceasul Tipurile de mutări care îl afectează
C_{{1,1}} 1, 2, 4
C_{{1,2}} 1, 2, 3, 5
C_{{1,3}} 2, 3, 6
C_{{2,1}} 1, 4, 5, 7
C_{{2,2}} 1, 3, 5, 7, 9
C_{{2,3}} 3, 5, 6, 9
C_{{3,1}} 4, 7, 8
C_{{3,2}} 5, 7, 8, 9
C_{{3,3}} 6, 8, 9

Se obține deci un sistem de 9 ecuații cu 9 necunoscute:

P={\begin{pmatrix}p_{1}+p_{2}+p_{4}&p_{1}+p_{2}+p_{3}+p_{5}&p_{2}+p_{3}+p_{6}\\p_{1}+p_{4}+p_{5}+p_{7}&p_{1}+p_{3}+p_{5}+p_{7}+p_{9}&p_{3}+p_{5}+p_{6}+p_{9}\\p_{4}+p_{7}+p_{8}&p_{5}+p_{7}+p_{8}+p_{9}&p_{6}+p_{8}+p_{9}\\\end{pmatrix}}\equiv B

Să presupunem că acest sistem admite două soluții p_{1},p_{2},\dots ,p_{9} și q_{1},q_{2},\dots ,q_{9}. Atunci P\equiv B{\pmod  {4}} și Q\equiv B{\pmod  {4}}, deci P\equiv Q{\pmod  {4}} și, prin diferite combinații liniare ale celor 9 ecuații se deduce p_{1}\equiv q_{1}, p_{2}\equiv q_{2}, ..., p_{9}\equiv q_{9}{\pmod  {4}}, adică cele două soluții sunt echivalente.

Odată ce am demonstrat că soluția este unică, algoritmul de găsire a ei este foarte simplu: găsim o soluție oarecare, o ordonăm crescător și eliminăm orice grup de 4 mutări identice. Pentru a găsi o soluție oarecare, avem nevoie de niște mutări predefinite care să miște un singur ceas cu o singură poziție înainte, fără a afecta celelalte ceasuri. Aceste mutări vor fi reținute sub forma unui vector cu 9 componente, fiecare componentă indicând de câte ori se efectuează fiecare din cele 9 tipuri de mutări. Deoarece avem nevoie de 9 asemenea mutări predefinite, câte una pentru fiecare ceas, rezultatul va fi o matrice predefinită. De exemplu, pentru a determina secvența de mutări care rotește ceasul C_{{1,1}} cu o poziție, trebuie rezolvat sistemul

{\begin{pmatrix}p_{1}+p_{2}+p_{4}&p_{1}+p_{2}+p_{3}+p_{5}&p_{2}+p_{3}+p_{6}\\p_{1}+p_{4}+p_{5}+p_{7}&p_{1}+p_{3}+p_{5}+p_{7}+p_{9}&p_{3}+p_{5}+p_{6}+p_{9}\\p_{4}+p_{7}+p_{8}&p_{5}+p_{7}+p_{8}+p_{9}&p_{6}+p_{8}+p_{9}\\\end{pmatrix}}\equiv {\begin{pmatrix}1&0&0\\0&0&0\\0&0&0\end{pmatrix}}

lucru care nu este foarte ușor, dar se poate duce la bun sfârșit în timp de concurs. Soluția este p_{1}=3,p_{2}=3,p_{3}=3,p_{4}=3,p_{5}=3,p_{6}=2,p_{7}=3,p_{8}=2,p_{9}=0, adică mutarea 1 trebuie efectuată de trei ori, mutarea 2 de trei ori ș.a.m.d. Se obține prima linie din matricea predefinită, (3, 3, 3, 3, 3, 2, 3, 2, 0). Mai trebuie rezolvate propriu-zis sistemele de ecuații pentru ceasurile C_{{1,2}} și C_{{2,2}}, soluțiile celorlalte sisteme decurgând ușor prin simetrie. Soluțiile apar în textul sursă.

Odată determinate aceste șiruri elementare de mutări, vom lua pe rând fiecare ceas, vom aplica șirul elementar corespunzător de atâtea ori cât e nevoie pentru a-l aduce la ora 12 și vom aduna modulo 4 toate mutările făcute. Vectorul sumă care rezultă este tocmai soluția noastră.

Pentru exemplul din enunț, folosind constantele din programul sursă, obținem:

B={\begin{pmatrix}1&1&0\\2&2&2\\2&3&2\end{pmatrix}}

și

1 x (3,3,3,3,3,2,3,2,0) = (3,3,3,3,3,2,3,2,0) +
1 x (2,3,2,3,2,3,1,0,1) = (2,3,2,3,2,3,1,0,1)
0 x (3,3,3,2,3,3,0,2,3) = (0,0,0,0,0,0,0,0,0)
2 x (2,3,1,3,2,0,2,3,1) = (0,2,2,2,0,0,0,2,2)
2 x (2,3,2,3,1,3,2,3,2) = (0,2,0,2,2,2,0,2,0)
2 x (1,3,2,0,2,3,1,3,2) = (2,2,0,0,0,2,2,2,0)
2 x (3,2,0,3,3,2,3,3,3) = (2,0,0,2,2,0,2,2,2)
3 x (1,0,1,3,2,3,2,3,2) = (3,0,3,1,2,1,2,1,2)
2 x (0,2,3,2,3,3,3,3,3) = (0,0,2,0,2,2,2,2,2)
------------------------
(0,0,0,1,1,0,0,1,1)

Prin urmare soluția simplă a exemplului este: 4 5 8 9.

#include <stdio.h>
typedef int Matrix[9][9];
typedef int Vector[9];
const Matrix A=
  {{3,3,3,3,3,2,3,2,0},  // Mutarile care misca ceasul C11
   {2,3,2,3,2,3,1,0,1},  // .
   {3,3,3,2,3,3,0,2,3},  // .
   {2,3,1,3,2,0,2,3,1},  // .
   {2,3,2,3,1,3,2,3,2},  // .
   {1,3,2,0,2,3,1,3,2},  // .
   {3,2,0,3,3,2,3,3,3},  // .
   {1,0,1,3,2,3,2,3,2},  // .
   {0,2,3,2,3,3,3,3,3}}; // Mutarile care misca ceasul C33

void main(void)
{ FILE *F=fopen("input.txt","rt");
  Vector V={0,0,0,0,0,0,0,0,0}; // Vectorul suma
  int i,j,k;

  for (i=0;i<=8;i++)
    { fscanf(F,"%d",&k);
      for (j=0;j<=8;j++)
        V[j]=(V[j]+(4-k)*A[i][j])%4;
    }
  fclose(F);

  F=fopen("output.txt","wt");
  for(i=0;i<=8;i++)
    for(j=1;j<=V[i];j++)
      fprintf(F,"%d ",i+1);
  fclose(F);
}


Problema 3

Problema de mai jos este un exemplu de situație în care căutarea exhaustivă a soluției este cea mai bună alegere. Ea a fost propusă spre rezolvare la a VIII-a Olimpiadă Internațională de Informatică, Veszprem, Ungaria 1996.

ENUNȚ: Văzând succesul cubului său magic, Rubik a inventat versiunea plană a jocului, numit „pătrate magice”. Se folosește o tablă compusă din 8 pătrate de dimensiuni egale. Cele opt pătrate au culori distincte, codificate prin numere de la 1 la 8, ca în figura următoare:

Psycho-fig45.png

Configurația tablei se poate reprezenta într-un vector cu 8 elemente citind cele opt pătrate, începând din colțul din stânga sus și mergând în sens orar. De exemplu, configurația din figură se reprezintă prin vectorul (1, 2, 3, 4, 5, 6, 7, 8). Aceasta este configurația inițială a tablei.

Unei configurații i se pot aplica trei transformări elementare, identificate prin literele „A”, „B” și „C”:

  • „A” schimbă între ele cele două linii ale tablei;
  • „B” rotește circular spre dreapta întregul dreptunghi (cu o poziție);
  • „C” rotește în sens orar cele patru pătrate centrale (cu o poziție);

Efectele transformărilor elementare asupra configurației inițiale sunt reprezentate în figura de mai jos:

Psycho-fig46.png

Din configurația inițială se poate ajunge în orice configurație folosind numai combinații de tranformări elementare. Trebuie să scrieți un program care calculează o secvență de transformări elementare care să aducă tabla de la configurația inițială la o anumită configurație finală cerută.

Intrarea: Fișierul INPUT.TXT conține 8 întregi pe aceeași linie, separați prin spații, descriind configurația finală.

Ieșirea se va face în fișierul OUTPUT.TXT. Pe prima linie a acestuia se va tipări lungimea L a secvenței de transformări, iar pe fiecare din următoarele L linii se va tipări câte un caracter „A”, „B” sau „C”, corespunzător mutărilor care trebuie efectuate.

Exemplu:

INPUT.TXT OUTPUT.TXT
2 6 8 4 5 7 3 1 7
B
C
A
B
C
C
B

Timp limită pentru un test: 20 secunde.

Timp de implementare: 1h 30’ - 1h 45’

Note:

  1. La concurs s-au acordat, pentru fiecare test, două puncte dacă se furniza o soluție și încă două dacă lungimea ei nu depășea 300 de mutări.
  2. Concurenților li s-a furnizat un program auxiliar, MTOOL.EXE, cu care se puteau verifica soluțiile furnizate.

REZOLVARE: Și la această problemă se întrevăd două abordări, ca și în problema ceasurilor: una bazată pe mutări predefinite, iar cealaltă pe o căutare exhaustivă a soluției. De data aceasta însă, prima este neinspirată. Să le analizăm pe rând pe fiecare, plecând de la următoarele considerente:

  • Dacă se aplică de două ori la rând mutarea A, tabla rămâne nemodificată;
  • Dacă se aplică de patru ori consecutiv una din mutările B sau C, tabla rămâne nemodificată;
  • Ordinea în care se efectuează mutările contează.

Soluția pe care autorul a prezentat-o la concurs avea predefinite mai multe mutări care schimbau între ele oricare două pătrate vecine de pe tablă. Mergând din aproape în aproape, fiecare pătrat era adus în poziția corespunzătoare. Spre exemplu, succesiunea de mutări predefinite care duceau la configurația din exemplu este:

Psycho-fig47.png

Această soluție funcționează instantaneu și este relativ ușor de implementat. Ea are însă defectul că soluția furnizată este extrem de lungă, ajungând frecvent la 500 de mutări. Din cele zece teste date, numai trei s-au încadrat în limita de 300 de mutări. Iată mai jos și sursa Pascal prezentată la concurs, care a câștigat numai 26 din cele 40 de puncte acordate pentru problemă:

program Magic;
{$B-,I-,R-,S-}
{ Tabla este 1 2 3 4
             A B C D }
const r12='BCBBB'; { Roteste in sens orar coloanele 12 }
      r23='C';     { Roteste in sens orar coloanele 23 }
      r34='BBBCB'; { Roteste in sens orar coloanele 34 }
      r14='BBCBB'; { Roteste in sens orar coloanele 41 }

      plBCD=r12+r23+r34+r14; { Permuta patratele BCD }
      PL234=plBCD+'A'+plBCD+'A'; { Permuta coloanele 234 }

      { SXY schimba intre ele coloanele X si Y }
      S14='B'+PL234;
      S12='BBB'+S14+'B';
      S23='BB'+S14+'BB';
      S34='B'+S14+'BBB';
      S13=r12+r12+r23+r23+r12+r12;
      S24='B'+S13+'BBB';

      { RevXY schimba intre ele patratele vecine X si Y }
      RevC3=plBCD+r23+r12+r12+r34+r34+'BBB'+plBCD+'A';
      RevD4='BBB'+RevC3+'B';
      RevB2='B'+RevC3+'BBB';
      RevA1='BB'+RevC3+'BB';

      Rev23='C'+RevC3+'CCC';
      Rev12='B'+Rev23+'BBB';
      Rev34='BBB'+Rev23+'B';
      Rev14='BB'+Rev23+'BB';

      RevAB='A'+Rev12+'A';
      RevBC='A'+Rev23+'A';
      RevCD='A'+Rev34+'A';
      RevAD='A'+Rev14+'A';

type Matrix=array[1..2,1..4] of Integer;
     Vector=array[1..60000] of Char;
var A,B:Matrix;
    V:Vector;
    N:Integer;

procedure MakeAMatrix;
begin
  A[1,1]:=1;
  A[1,2]:=2;
  A[1,3]:=3;
  A[1,4]:=4;
  A[2,1]:=8;
  A[2,2]:=7;
  A[2,3]:=6;
  A[2,4]:=5;
end;

procedure ReadBMatrix;
begin
  Assign(Input,'input.txt');
  Reset(Input);
  Read(B[1,1]);
  Read(B[1,2]);
  Read(B[1,3]);
  Read(B[1,4]);
  Read(B[2,4]);
  Read(B[2,3]);
  Read(B[2,2]);
  Read(B[2,1]);
  Close(Input);
end;

procedure AddString(S:String);
{ Adauga o secventa la sirul-solutie }
var i:Integer;
begin
  for i:=1 to Length(S) do
    begin
      Inc(N);
      V[N]:=S[i];
    end;
end;

procedure FindElement(K:Integer;var X,Y:Integer);
{ Cauta un element intr-o permutare }
var i,j:Integer;
begin
  for i:=1 to 2 do
    for j:=1 to 4 do
      if A[i,j]=K then begin
                         X:=i;
                         Y:=j;
                         Exit;
                       end;
end;

procedure Switch(var X,Y:Integer);
{ Schimba intre ele doua numere }
var IAux:Integer;
begin
  IAux:=X;X:=Y;Y:=IAux;
end;

procedure Process;
{ Transforma pozitia in pozitia B prin schimbari
  repetate ale elementelor vecine }
var i,j,k,l,m:Integer;
begin
  for j:=1 to 4 do
    for i:=1 to 2 do
      begin
        FindElement(B[i,j],k,l);
        { Gaseste elementul care trebuie adus
          pe pozitia (i,j) }
        if k<>i then begin
                       { Il aduce pe linia corecta }
                       case l of
                         1:AddString(RevA1);
                         2:AddString(RevB2);
                         3:AddString(RevC3);
                         4:AddString(RevD4);
                       end; {case}
                       Switch(A[k,l],A[i,l]);
                       k:=i;
                     end;
        for m:=l downto j+1 do
          { Il aduce pe coloana corecta }
          begin
            if k=1
              then case m of
                     2:AddString(Rev12);
                     3:AddString(Rev23);
                     4:AddString(Rev34);
                   end
              else case m of
                     2:AddString(RevAB);
                     3:AddString(RevBC);
                     4:AddString(RevCD);
                   end;
            Switch(A[k,m],A[k,m-1]);
          end;
      end;
end;

procedure Cut(K,D:Integer);
{ Taie din vectorul V D pozitii incepand cu K }
var i:Integer;
begin
  for i:=K to N-D do
    V[i]:=V[i+D];
  Dec(N,D);
end;

procedure Reduce;
{ Reduce secventele de mutari identice }
var i:Integer;
begin
  i:=1;
  repeat
    case V[i] of
      'A':if (i<=N-1) and (V[i+1]='A')
            then Cut(i,2)
            else Inc(i);
      'B':if (i<=N-3) and (V[i+1]='B')
            and (V[i+2]='B') and (V[i+3]='B')
            then Cut(i,4)
            else Inc(i);
      'C':if (i<=N-3) and (V[i+1]='C')
            and (V[i+2]='C') and (V[i+3]='C')
            then Cut(i,4)
            else Inc(i);
    end; {case}
  until i=N;
end;

procedure WriteSolution;
var i:Integer;
begin
  Assign(Output,'output.txt');
  Rewrite(Output);
  WriteLn(N);
  for i:=1 to N do WriteLn(V[i]);
  Close(Output);
end;

begin
  N:=0;
  MakeAMatrix;
  ReadBMatrix;
  Process;
  Reduce;
  WriteSolution;
end.

Singura soluție pare deci a fi una de tipul Branch and Bound, care nu este tocmai la îndemână. Cu toate acestea, numărul total de configurații posibile ale tablei este de numai 8! = 40320. Într-adevăr, fiecare poziție de pe tablă se reprezintă printr-o permutare a mulțimii {1,2,3,4,5,6,7,8}. Se poate face deci cu ușurință o căutare exhaustivă a soluției. Aceasta simplifică mult structurile de date folosite (implementarea Branch & Bound folosește structuri destul de încâlcite). În plus, practica arată că se poate ajunge în orice configurație în mai puțin de 25 de mutări.

Algoritmul de căutare este cunoscut sub numele de algoritmul lui Lee și are la bază următoarea idee: Se pornește cu configurația inițială, care este depusă într-o coadă. La fiecare pas se extrage prima configurație disponibilă din coadă, se efectuează pe rând fiecare din cele trei mutări și se obțin trei succesori. Aceștia sunt adăugați la sfârșitul cozii, dacă nu există deja în coadă. Acest pas se numește expandare. Expandarea continuă până când elementul selectat spre expandare este tocmai configurația finală.

Figura următoare indică modul de expandare a cozii, cu mențiunea că printr-o succesiune de litere ne-am referit la configurația care se obține efectuând mutările respective:

Psycho-fig48.png

Se observă că, la pasul 2, în coadă au fost adăugate doar configurațiile „AB” și „AC”, iar configurația „AA” nu, deoarece prin efectuarea de două ori a mutării „A” se revine la configurația inițială, care a fost deja expandată. De asemenea, la pasul 3, după expandarea configurației „B” au fost adăugate în coadă numai configurațiile „BB” și „BC”, deoarece configurația „BA” este echivalentă cu configurația „AB”, aflată deja în listă.

Pseudocodul algoritmului este:

citeste datele de intrare
initializeaza coada cu configuratia initiala
cat timp primul element al cozii nu este configuratia finala:
  expandeaza primul element al cozii
  pentru i=[A,B,C]
    daca succesorul i nu a fost deja pus in coada atunci
      adauga succesorul i in coada
  sterge primul element al cozii
reconstituie sirul de mutari

Algoritmul de mai sus garantează și găsirea soluției optime (în număr minim de mutări). Rămân de lămurit două lucruri: (1) Cum ne dăm seama dacă o configurație există deja în coadă și (2) cum se face reconstituirea soluției.

Pentru a afla dacă o configurație mai există în listă, cea mai simplă metodă ar fi o căutare secvențială a listei. Totuși, această versiune ar fi extrem de lentă, deoarece coada atinge rapid dimensiuni respectabile (de ordinul miilor de elemente). În plus, un element al listei ar reține configurația propriu-zisă (un vector cu opt elemente), ceea ce ar duce la un consum ridicat de memorie. Testul de egalitate a doi vectori ar fi și el costisitor din punct de vedere al timpului.

Există însă o altă metodă mai simplă. Am demonstrat că numărul de configurații posibile ale tablei este 8! = 40320. Dacă am putea găsi o funcție bijectivă H:{\mathbf  {P_{8}}}\to \{0,1,\dots ,40319\}, unde {\mathbf  {P_{8}}} este mulțimea permutărilor de 8 elemente, atunci ar fi suficient un vector caracteristic cu 40320 elemente. De îndată ce introducem în coadă o nouă configurație K, nu avem decât să bifăm elementul corespunzător din vectorul caracteristic. Înainte de a adăuga o configurație în coadă, testăm dacă nu cumva elementul corespunzător ei a fost deja bifat, semn că nodul a mai fost vizitat.

Cum se construiește funcția H? Pentru orice permutare p\in {\mathbf  {P_{8}}}, H(p) este poziția lui p în ordonarea lexicografică a lui {\mathbf  {P_{8}}} (începând de la 0):

H(1, 2, 3, 4, 5, 6, 7, 8) = 0
H(1, 2, 3, 4, 5, 6, 8, 7) = 1
H(1, 2, 3, 4, 5, 7, 6, 8) = 2
....................................
H(8, 7, 6, 5, 4, 3, 1, 2) = 40318
H(8, 7, 6, 5, 4, 3, 2, 1) = 40319

Se observă că primele 7! = 5040 elemente din ordonare au pe prima poziție un 1, următoarele 5040 au pe prima poziție un 2 etc. De asemenea, dintre elementele care au pe prima poziție un 1, primele 6! = 720 au pe a doua poziție un 2, următoarele 720 au pe a doua poziție un 3 etc.

Să calculăm de exemplu H(2, 6, 8, 4, 5, 7, 3, 1). Prima cifră a permutării este 2, deci se adaugă 7! = 5040. Rămân cifrele 1, 3, 4, 5, 6, 7 și 8. A doua cifră a permutării este 6, a cincea ca valoare dintre cifrele rămase, deci se adaugă 4 x 6! = 2880. Rămân cifrele 1, 3, 4, 5, 7 și 8 etc. Se aplică procedeul până la ultima cifră și rezultă:

Cifre rămase Permutarea Valoarea adăugată
1, 2, 3, 4, 5, 6, 7, 8 2 1 x 7! = 5040
1, 3, 4, 5, 6, 7, 8 6 4 x 6! = 2880
1, 3, 4, 5, 7, 8 8 5 x 5! = 600
1, 3, 4, 5, 7 4 2 x 4! = 48
1, 3, 5, 7 5 2 x 3! = 12
1, 3, 7 7 2 x 2! = 4
1, 3 3 1 x 1! = 1
1 1 0 x 0! = 0
H(p) = 8585

Reciproc se construiește permutarea când i se cunoaște valoarea atașată:

Cifre nefolosite H(p) Cifra selectată
1, 2, 3, 4, 5, 6, 7, 8 8585 8585 div 7! = 1 2 8585 mod 7! = 3545
1, 3, 4, 5, 6, 7, 8 3545 3545 div 6! = 4 6 3545 mod 6! = 665
1, 3, 4, 5, 7, 8 665 665 div 5! = 5 8 665 mod 5! = 65
1, 3, 4, 5, 7 65 65 div 4! =2 4 65 mod 4! = 17
1, 3, 5, 7 17 17 div 3! = 2 5 17 mod 3! = 5
1, 3, 7 5 5 div 2! = 2 7 5 div 2! = 1
1, 3 1 1 div 1!=1 3 1 mod 1! = 0
1 0 0 div 0!=0 1

Rezultă p=(2, 6, 8, 4, 5, 7, 3, 1).

Această metodă de căutare are și avantajul că în listă se va ține un singur număr pe doi octeți, făcându-se economie de memorie. Expandarea unui nod constă din trei pași:

  1. Se extrage primul număr din listă și se reconstituie configurația atașată;
  2. Se fac cele trei mutări, obținându-se trei succesori;
  3. Pentru fiecare succesor se calculează funcția H și dacă configurația nu este găsită în listă, este adăugată.

Pentru a face reconstituirea soluției avem nevoie de date suplimentare. Respectiv, vectorul caracteristic atașat permutărilor nu va mai reține doar dacă o poziție a fost „văzută” sau nu, ci și poziția din care ea provine (prin valoarea funcției H). Trebuie de asemenea reținut tipul mutării (A, B sau C) prin care s-a ajuns în acea configurație. Cei doi vectori se numesc Father și MoveKind. Inițial, toate elementele vectorului Father au eticheta „Unknown”, semnificând că nodurile nu au fost încă vizitate, cu excepția elementului atașat configurației inițiale, care poartă eticheta specială „Root” (rădăcină).

Pseudocodul pentru expandarea unui nod arată cam așa:

K ← primul numar din coada
P ← H-1(K)
afla cei trei succesori QA, QB, QC
pentru i=A,B,C
  daca Father[H(Qi)]=Unknown atunci
    Father[H(Qi)] ← K
    MoveKind[H(Qi)] ← i
    adauga H(Qi) in coada
sterge K din coada

Reconstituirea soluției se face recursiv: se pornește de la configurația finală și se merge înapoi (folosind informația din vectorul Father) până la configurația inițială, măsurându-se astfel numărul de mutări. La revenire se tipăresc toate mutările efectuate (folosind informația din vectorul MoveKind).

#include <stdio.h>
#include <stdlib.h>
#define Unknown 0xFFFF
#define Root 0xFFFE

typedef huge unsigned Vector[40320];
typedef char CharVector[40320];
typedef int Perm[8];
typedef struct list { unsigned X; struct list * Next; } List;

Perm StartPerm={1,2,3,4,5,6,7,8}, EndPerm;
const Perm Moves[3]=
   {{7,6,5,4,3,2,1,0},
    {3,0,1,2,5,6,7,4},
    {0,6,1,3,4,2,5,7}};
/* Cele trei tipuri de mutari */
Vector Father; /* Legaturile de tip tata */
CharVector MoveKind;
unsigned StartValue,EndValue;
/* Valorile atasate configuratiilor initiala si finala */
List *Head, *Tail; /* Coada de expandat */

/**** Bijectia care asociaza un numar unei permutari ****/

unsigned Perm2Int(Perm P)
{ int i,j,k,Fact=5040;
  unsigned Sum=0;

  for (i=0;i<=6;i++)
    { k=P[i]-1;
      for (j=0;j<i;j++)
        if (P[j]<P[i]) k--;
      Sum+=k*Fact;
      Fact/=(7-i);
    }
  return Sum;
}

void Int2Perm(unsigned Sum, Perm P)
{ int i,j,k,Order,Fact=5040;
  Perm Used={0,0,0,0,0,0,0,0};

  for (i=0;i<=7;i++)
    { Order=Sum/Fact;
      j=-1;
      for (k=0;k<=Order;k++)
        do j++; while (Used[j]);
      Used[j]=1;
      P[i]=j+1;
      Sum%=Fact;
      if (i!=7) Fact/=(7-i);
    }
}

/**** Lucrul cu liste ****/

void InitList(void)
{
  Head=Tail=malloc(sizeof(List));
  Tail->X=StartValue;
  Tail->Next=NULL;
}

void AddToTail(unsigned K)
{
  Tail->Next=malloc(sizeof(List));
  Tail=Tail->Next;
  Tail->X=K;
  Tail->Next=NULL;
}

void Behead(void)
/* Sterge capul listei */
{ List *LCor=Head;

  Head=Head->Next;
  free(LCor);
}

/**** Cautarea propriu-zisa ****/

void MakeMove(Perm P,Perm Q,int Kind)
/* Kind = 0, 1 sau 2 */
{ int i;
  for (i=0;i<=7;i++)
    Q[i]=P[Moves[Kind][i]];
}

void Expand(void)
{ List *LCor;
  Perm P1,P2;
  unsigned i,XSon,Done;

  InitList();
  do {
    Int2Perm(Head->X,P1);
    for(i=0;i<=2;i++)
      { MakeMove(P1,P2,i);
        XSon=Perm2Int(P2);
        if (Father[XSon]==Unknown)
          { Father[XSon]=Head->X;
            MoveKind[XSon]=i+65;
            AddToTail(XSon);
          }
      }
    Done=(Head->X==EndValue);
    Behead(); }
  while (!Done);
}

/* Intrarea si iesirea */

void InitData(void)
{ FILE *F=fopen("input.txt","rt");
  unsigned i;

  for (i=0;i<=7;i++) fscanf(F,"%d",&EndPerm[i]);
  fclose(F);
  StartValue=Perm2Int(StartPerm);
  EndValue=Perm2Int(EndPerm);
  for (i=0;i<40320;) Father[i++]=Unknown;
  Father[StartValue]=Root;
}

void WriteMove(FILE *F,unsigned K,int Len)
{
  if (K!=StartValue)
    { WriteMove(F,Father[K],Len+1);
      fprintf(F,"%c\n",MoveKind[K]);
    }
    else fprintf(F,"%d\n",Len);
}

void Restore(void)
{ FILE *F=fopen("output.txt","wt");

  WriteMove(F,EndValue,0);
  fclose(F);
}

void main(void)
{
  InitData();
  Expand();
  Restore();
}

Problema 4

Continuăm cu o problemă care a fost de asemenea dată spre rezolvare la a VIII-a Olimpiadă Internațională de Informatică, Veszprem 1996. Problema în sine nu a fost foarte grea și mulți elevi au luat punctaj maxim. Totuși, enunțul permite unele modificări interesante care practic schimbă cu totul problema.

ENUNȚ: Să considerăm următorul joc de două persoane. Tabla de joc constă într-o secvență de întregi pozitivi. Cei doi jucători mută pe rând. Mutarea fiecărui jucător constă în alegerea unui număr de la unul din cele două capete ale secvenței. Numărul ales este șters de pe tablă. Jocul se termină când toate numerele au fost selectate. Primul jucător câștigă dacă suma numerelor alese de el este mai mare sau egală cu cea a numerelor alese de cel de-al doilea jucător. În caz contrar, câștigă al doilea jucător.

Dacă tabla conține inițial un număr par de elemente, atunci primul jucător are o strategie de câștig. Trebuie să scrieți un program care implementează strategia cu care primul jucător câștigă jocul. Răspunsurile celui de-al doilea jucător sunt date de un program rezident. Cei doi jucători comunică prin trei proceduri ale modulului Play care v-a fost pus la dispoziție. Procedurile sunt StartGame, MyMove și YourMove. Primul jucător începe jocul apelând procedura fără parametri StartGame. Dacă alege numărul de la capătul din stânga, el va apela procedura MyMove('L'). Analog, apelul de procedură MyMove('R') trimite un mesaj celui de-al doilea jucător prin care îl informează că a ales numărul de la capătul din dreapta. Cel de-al doilea jucător, deci computerul, mută imediat, iar primul jucător poate afla mutarea acestuia executând procedura YourMove(C), unde C este o variabilă de tip Char (în C/C++ apelul este YourMove(&C)). Valoarea lui C este 'L' sau 'R', după cum numărul ales este de la capătul din stânga sau din dreapta.

Intrarea: Prima linie din fișierul INPUT.TXT conține dimensiunea inițială N a tablei. N este par și 2 ≤ N ≤ 100. Următoarele N linii conțin fiecare câte un număr, reprezentând conținutul tablei de la stânga la dreapta. Fiecare număr este cel mult 200.

Ieșirea: Când jocul se termină, programul trebuie să scrie rezultatul final în fișierul OUTPUT.TXT. Fișierul conține două numere pe prima linie, reprezentând suma numerelor alese de primul, respectiv de cel de-al doilea jucător. Programul trebuie să joace un joc corect și ieșirea trebuie să corespundă jocului jucat.

Exemplu:

INPUT.TXT OUTPUT.TXT
6
4
7
2
9
5
2
15 14

Timp limită de execuție: 20 secunde pentru un test.

Acesta a fost enunțul original, la care va trebui să facem câteva modificări, în parte deoarece nu putem folosi modulul Play, în parte pentru a face problema mai restrictivă:

  • Mutările vor fi anunțate pe ecran prin tipărirea unui caracter 'L' sau 'R';
  • Mutările celui de-al doilea jucător vor fi comunicate de un partener uman, prin introducerea de la tastatură a unui caracter 'L' sau 'R';
  • Rezultatul final se va tipări pe ecran, sub aceeași formă (pereche de numere).
  • Timpul de gândire pentru fiecare mutare trebuie să fie cât mai mic (practic răspunsul să fie instantaneu);
  • Complexitatea totală a calculelor efectuate să fie O(N).
  • Timpul de implementare a fost cam de 1h 40 min. Propunem reducerea lui la 30 minute.

REZOLVARE: Este ușor de demonstrat că o rezolvare „greedy” a problemei (la fiecare mutare jucătorul 1 alege numărul mai mare) nu atrage întotdeauna câștigul. Iată un contraexemplu:

Psycho-fig49.png

La prima mutare, jucătorul 1 poate să aleagă fie numărul 7, fie numărul 2. Dacă se va „lăcomi” la 7, jucătorul 2 va lua numărul 10 și inevitabil va câștiga. Soluția pentru primul jucător este să ia numărul 2, apoi, indiferent de ce va juca partenerul său, va putea lua numărul 10 și va câștiga.

Iată o soluție izbitor de simplă de complexitate O(N): La citirea datelor se face suma elementelor aflate pe poziții pare și a celor aflate pe poziții impare. Să presupunem că suma elementelor de ordin par este mai mare sau egală cu cea a elementelor de ordin impar (cazul invers se tratează analog). Atunci, dacă primul jucător ar putea să aleagă toate elementele de ordin par (care sunt într-adevăr N/2, adică atâtea câte are el dreptul să aleagă), ar câștiga jocul. Jucătorul 1 poate începe jocul prin a lua primul sau ultimul element din secvență, deci îl va alege pe ultimul, care are număr de ordine par. Al doilea jucător are de ales între primul și al N-1-lea element, ambele având număr de ordine impar. Indiferent ce variantă o va adopta, primul jucător va avea din nou acces la un element de pe o poziție pară. Dacă jucătorul 2 alege elementul din stânga (primul), atunci jucătorul 1 va putea lua elementul de după el (al doilea), iar dacă jucătorul 2 alege elementul din dreapta (al N-1-lea), atunci jucătorul 1 va putea lua elementul dinaintea el (al N-2-lea). Deci primul jucător nu are altceva de făcut decât să repete mutările făcute de cel de-al doilea. Să privim de exemplu desfășurarea jocului pe tabla dată în enunț:

Psycho-fig50.png

Programul în sine nici nu are nevoie să mai rețină vectorul de numere în memorie, din moment ce primul jucător nu are altceva de făcut decât să imite mutările celui de-al doilea. Un calcul al sumelor la citirea datelor este suficient. Complexitatea O(N) este optimă, deoarece vectorul trebuie parcurs cel puțin o dată pentru citirea configurației inițiale a tablei.

#include <stdio.h>

void main(void)
{ FILE *F=fopen("input.txt","rt");
  int SEven,SOdd,N,i,K;

  fscanf(F,"%d\n",&N);
  for (i=1, SEven=SOdd=0; i<=N; i++)
    { fscanf(F, "%d\n", &K);
      if (i&1) SOdd+=K;
        else SEven+=K;
    }
  fclose(F);

  printf("Mutarea mea: %c\n", SEven>=SOdd ? 'R' : 'L');
  for (i=1; i<N/2; i++)
    { printf("Mutarea dvs. (L/R) ? ");
      printf("Mutarea mea: %c\n", getchar());
      getchar(); /* Caracterul newline */
    }
  printf("Mutarea dvs. (L/R) ? ");
  getchar();

  if (SEven>=SOdd)
    printf("%d %d\n", SEven, SOdd);
    else printf("%d %d\n", SOdd, SEven);
}

O a doua variantă a enunțului aduce unele condiții suplimentare:

  • Se cere să se tipărească numai diferența maximă de scor pe care o poate obține primul jucător, considerând că ambii parteneri joacă perfect;
  • Complexitatea cerută este O(N^{2}).
  • Timpul de implementare este de 45 minute, maxim 1h.


REZOLVARE: Trebuie mai întâi să lămurim ce se înțelege prin „joc perfect”. Jucătorul 1 are întotdeauna victoria la îndemână (metoda este arătată mai sus), dar nu la orice scor. Jucătorul 2 urmărește să minimizeze diferența de scor. Fie D diferența de scor cu care se termină un joc. D poate lua diferite valori pentru aceeași configurație inițială a tablei, în funcție de mutările făcute de cei doi jucători. Fie D_{{MAX}} diferența maximă de scor pe care o poate obține primul jucător indiferent de mutările celui de-al doilea. Exact această valoare trebuie aflată. D_{{MAX}} nu este propriu-zis o diferență maximă. Jucătorul 1 poate să câștige și la diferențe mai mari decât D_{{MAX}}, dar trebuie ca jucătorul 2 să-l „ajute”. Să reluăm exemplul cu 4 numere:

Psycho-fig51.png

În acest caz, primul jucător are asigurat scorul 12-8 (deci diferența 4). Pentru aceasta, el începe prin a lua numărul 2, apoi, orice ar replica celălalt, va lua numărul 10, jucătorului 2 revenindu-i așadar numerele 1 și 7. El poate obține și scorul 17-3 (jucătorul 1 ia numărul 7, celălalt ia 2, jucătorul 1 ia 10, iar celălalt ia 1), dar aceasta se întâmplă numai dacă jucătorul 2 face o greșeală. După cum am arătat mai sus, dacă primul jucător începe luând numărul 7, el pierde în mod normal partida. Iată deci că în acest caz D_{{MAX}}=4.

Pentru a putea afla diferența maximă de scor, este bine să privim mereu în adâncime. Există patru variante în care ambii parteneri pot face câte o mutare:

  1. Ambii jucători aleg numere din partea stângă;
  2. Ambii aleg numere din partea dreaptă;
  3. Primul jucător alege numărul din stânga, iar celălalt pe cel din dreapta;
  4. Primul jucător alege numărul din dreapta, iar celălalt pe cel din stânga;

În urma oricărei variante de mutare, secvența se scurtează cu două elemente. Dacă am putea cunoaște dinainte care este rezultatul jocului pentru fiecare din secvențele scurte, am putea să decidem care variantă de joc este cea mai convenabilă pentru secvența inițială, ținând cont și de modul de joc al jucătorului al doilea. Tocmai de aici vine și ideea de rezolvare. Să notăm cu A[1], A[2], ..., A[N] secvența citită la intrare. Vom construi o matrice D cu N linii și N coloane, unde D[i,j] este diferența maximă pe care o poate obține jucătorul 1 pentru secvența A[i], A[i+1], ..., A[j]. Bineînțeles, sunt luate în considerare numai secvențele de lungime pară. Scopul nostru este să-l aflăm pe D[1,N].

Elementele matricei pe care le putem afla fără multă bătaie de cap sunt D[1,2], D[2,3], ..., D[N-1,N]. Într-adevăr, dintr-o secvență de numai două numere, primului jucător îi revine cel mai mare, iar celui de-al doilea - cel mai mic. Așadar

D[i,i+1]=|A[i]-A[i+1]|

Cum calculăm D[i,j] dacă cunoaștem valorile matricei D pentru toate subsecvențele incluse în secvența A[i], A[i+1], ..., A[j] ? După cum am mai spus, avem patru variante:

Psycho-fig52.png

Trebuie să ținem minte că, dacă primul jucător optează să-l aleagă pe A[i] (una din primele două variante), atunci jucătorul 2 va juca în așa fel încât pierderea să fie minimă, iar scorul final va fi \min(R_{1},R_{2}). Dacă jucătorul 1 alege varianta 3 sau 4, scorul final va fi \min(R_{3},R_{4}). Dar jucătorul 1 este primul la mutare, deci va alege varianta care îi maximizează profitul. Rezultatul este

D[i,j]=\max(\min(R_{1},R_{2}),\min(R_{3},R_{4}))

adică

{\begin{aligned}D[i,j]=\max(&A[i]+\min(D[i+2,j]-A[i+1],D[i+1,j-1]-A[j]),\\&A[j]+\min(D[i+1,j-1]-A[i],D[i,j-2]-A[j-1]))\end{aligned}}

Matricea D se completează pe diagonală, pornind de la diagonala principală și mergând până în colțul de N-E. Iată cum arată matricea atașată datelor de intrare din enunț:

D={\begin{pmatrix}X&3&X&10&X&7\\X&X&5&X&9&X\\X&X&X&7&X&4\\X&X&X&X&4&X\\X&X&X&X&X&3\\X&X&X&X&X&X\end{pmatrix}}

Pentru exemplul din enunț, răspunsul este deci D_{{MAX}}=7. Cum elementele matricei sunt parcurse cel mult o dată, rezultă o complexitate de O(N^{2}).

#include <stdio.h>
#include <stdlib.h>
#define NMax 101

int D[NMax][NMax], A[NMax], N;

void ReadData(void)
{ FILE *F=fopen("input.txt","rt");
  int i;

  fscanf(F,"%d\n",&N);
  for (i=1; i<=N;)
    fscanf(F, "%d\n", &A[i++]);
  fclose(F);
}

int Min(int A, int B)
{
  return A<B ? A : B;
}

int Max(int A, int B)
{
  return A>B ? A : B;
}

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

  for (i=1;i<N;i++)
    D[i][i+1]=abs(A[i]-A[i+1]);
  for (k=3;k<=N-1;k++)
    for (i=1;i+k<=N;i++)
      { j=i+k;
        D[i][j]=Max(A[i]+Min(D[i+2][j]-A[i+1],
                             D[i+1][j-1]-A[j]),
                    A[j]+Min(D[i+1][j-1]-A[i],
                             D[i][j-2]-A[j-1]));
      }
  printf("Diferenta maxima este %d\n",D[1][N]);
}

void main(void)
{
  ReadData();
  FindMax();
}

Programul prezentat mai sus poate fi optimizat, dacă timpul o permite și dacă acest lucru este necesar. Lăsăm cititorul să încerce să rezolve aceeași problemă folosind o cantitatate de memorie direct proporțională cu N.