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

From Algopedia
Jump to: navigation, search
Line 122: Line 122:
 
   fprintf(OutF,"\n");
 
   fprintf(OutF,"\n");
 
   fclose(OutF);
 
   fclose(OutF);
 +
}
 +
</syntaxhighlight>
 +
 +
 +
== 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).
 +
 +
[[File: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 <tt>INPUT.TXT</tt>, 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 <tt>OUTPUT.TXT</tt> 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 <tt>INPUT.TXT</tt> este
 +
 +
<pre>
 +
3 3 0
 +
2 2 2
 +
2 1 2
 +
</pre>
 +
 +
iar fișierul <tt>OUTPUT.TXT</tt> ar putea fi:
 +
 +
<pre>
 +
5 8 4 9
 +
</pre>
 +
 +
'''Timp de implementare''': 1h - 1h 15min.
 +
 +
'''Timp de rulare''': o secundă.
 +
 +
'''Complexitate cerută''': <math>O(1)</math> (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 <math>4^9</math>, 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:
 +
 +
# 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.
 +
# 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 <math>A \in M_3(\mathbb{Z}_4)</math> matricea citită de la intrare, unde <math>a_{i,j}</math> arată de câte ori a fost rotit ceasul <math>C_{i,j}</math> peste ora 12. Fie matricea <math>B \in M_3(\mathbb{Z}_4),
 +
b_{i,j}=4 - a_{i,j}</math>. 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, <math>p_1, p_2, \dots, p_9</math>. Cum afectează aceste mutări ceasurile? Se poate deduce ușor:
 +
 +
{|class="wikitable"
 +
! Ceasul || Tipurile de mutări care îl afectează
 +
|-
 +
| <math>C_{1,1}</math> || 1, 2, 4
 +
|-
 +
| <math>C_{1,2}</math> || 1, 2, 3, 5
 +
|-
 +
| <math>C_{1,3}</math> || 2, 3, 6
 +
|-
 +
| <math>C_{2,1}</math> || 1, 4, 5, 7
 +
|-
 +
| <math>C_{2,2}</math> || 1, 3, 5, 7, 9
 +
|-
 +
| <math>C_{2,3}</math> || 3, 5, 6, 9
 +
|-
 +
| <math>C_{3,1}</math> || 4, 7, 8
 +
|-
 +
| <math>C_{3,2}</math> || 5, 7, 8, 9
 +
|-
 +
| <math>C_{3,3}</math> || 6, 8, 9
 +
|}
 +
 +
Se obține deci un sistem de 9 ecuații cu 9 necunoscute:
 +
 +
<math>
 +
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
 +
</math>
 +
 +
Să presupunem că acest sistem admite două soluții <math>p_1, p_2, \dots, p_9</math> și <math>q_1, q_2, \dots, q_9</math>. Atunci <math>P \equiv B \pmod{4}</math> și <math>Q \equiv B \pmod{4}</math>, deci <math>P \equiv Q \pmod{4}</math> și, prin diferite combinații liniare ale celor 9 ecuații se deduce <math>p_1 \equiv q_1</math>, <math>p_2 \equiv q_2</math>, ..., <math>p_9 \equiv q_9 \pmod{4}</math>, 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 <math>C_{1,1}</math> cu o poziție, trebuie rezolvat sistemul
 +
 +
<math>
 +
\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}
 +
</math>
 +
 +
lucru care nu este foarte ușor, dar se poate duce la bun sfârșit în timp de concurs. Soluția este <math>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</math>, 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 <math>C_{1,2}</math> și <math>C_{2,2}</math>, 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:
 +
 +
<math>
 +
B =
 +
\begin{pmatrix}
 +
1 & 1 & 0 \\
 +
2 & 2 & 2 \\
 +
2 & 3 & 2
 +
\end{pmatrix}
 +
</math>
 +
 +
ș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.
 +
 +
<syntaxhighlight lang="c">
 +
#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);
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Revision as of 14:13, 7 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);
}