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

From Algopedia
Jump to: navigation, search
Line 37: Line 37:
 
* Configurația inițială este:
 
* Configurația inițială este:
  
 
+
: [[File:Psycho-fig32.png]]
  
 
* Se împinge bila albă și se sare cu cea neagră peste ea (șirul de mutări 14):
 
* Se împinge bila albă și se sare cu cea neagră peste ea (șirul de mutări 14):
  
 
+
: [[File:Psycho-fig33.png]]
  
 
* Se împinge bila neagră și se sare de două ori cu cele albe peste ea (șirul de mutări 322):
 
* Se împinge bila neagră și se sare de două ori cu cele albe peste ea (șirul de mutări 322):
  
 
+
: [[File:Psycho-fig34.png]]
  
 
* Se împinge bila albă și se sare de trei ori cu cele negre peste ea (șirul de mutări 1444):
 
* Se împinge bila albă și se sare de trei ori cu cele negre peste ea (șirul de mutări 1444):
  
 
+
: [[File:Psycho-fig35.png]]
  
 
* Se împinge bila neagră și se sare de patru ori cu cele albe peste ea (șirul de mutări 32222):
 
* Se împinge bila neagră și se sare de patru ori cu cele albe peste ea (șirul de mutări 32222):
  
 +
: [[File:Psycho-fig36.png]]
  
 
+
: ...
..............................................................................................................
 
  
 
* Se împinge bila albă (mutarea 1)
 
* Se împinge bila albă (mutarea 1)
  
 
+
: [[File:Psycho-fig37.png]]
  
 
* Se sare de '''''N''''' ori cu cele negre peste ea (șirul de mutări 44..44):
 
* Se sare de '''''N''''' ori cu cele negre peste ea (șirul de mutări 44..44):
  
 
+
: [[File:Psycho-fig38.png]]
  
 
Ultimele două configurații sunt simetrice. În acest moment șirul de mutări se inversează:
 
Ultimele două configurații sunt simetrice. În acest moment șirul de mutări se inversează:
Line 69: Line 69:
 
* Se împinge bila albă (mutarea 1):
 
* Se împinge bila albă (mutarea 1):
  
 +
: [[File:Psycho-fig39.png]]
  
 
+
...
..............................................................................................................
 
  
 
* Se sare de patru ori cu bilele albe și se împinge bila neagră (șirul de mutări 22223):
 
* Se sare de patru ori cu bilele albe și se împinge bila neagră (șirul de mutări 22223):
  
 
+
: [[File:Psycho-fig40.png]]
  
 
* Se sare de trei ori cu bilele negre și se împinge bila albă (șirul de mutări 4441):
 
* Se sare de trei ori cu bilele negre și se împinge bila albă (șirul de mutări 4441):
  
 
+
: [[File:Psycho-fig41.png]]
  
 
* Se sare de două ori cu bilele albe și se împinge bila neagră (șirul de mutări 223):
 
* Se sare de două ori cu bilele albe și se împinge bila neagră (șirul de mutări 223):
  
 
+
: [[File: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ă:
 
* Se sare cu bila neagră și se împinge bila albă (șirul de mutări 41), obținându-se configurația finală:
  
 
+
: [[File: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.
 
Î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.

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