Difference between revisions of "Clasa a VII-a lecția 20 - 6 feb 2020"

From Algopedia
Jump to navigationJump to search
 
(2 intermediate revisions by the same user not shown)
Line 561: Line 561:
 
Problema [http://varena.ro/problema/z zparcurgere] a fost dată la concursul Grigore Moisil by net 2006.
 
Problema [http://varena.ro/problema/z zparcurgere] a fost dată la concursul Grigore Moisil by net 2006.
  
 +
=== Soluție ===
 
Cum o rezolvăm?
 
Cum o rezolvăm?
  
Line 572: Line 573:
  
 
Ce observăm?
 
Ce observăm?
* Putem împărți problema în patru subprobleme, cele patru pătrate de latură ''N/2''.
+
* Putem împărți problema în patru subprobleme, cele patru pătrate de latură 2<sup>N-1</sup>.
 
* Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
 
* Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
 
* Trebuie să ajustăm elementul de start pentru subproblema mai mică.
 
* Trebuie să ajustăm elementul de start pentru subproblema mai mică.
Line 590: Line 591:
 
În aceste condiții avem relația:
 
În aceste condiții avem relația:
  
  ''E(N, L, C, S) = E(N/2, L', C', S<nowiki>''</nowiki>)''
+
  ''E(N, L, C, S) = E(N-1, L', C', S<nowiki>''</nowiki>)''
  
 
'''Observații''':
 
'''Observații''':
* La fiecare pas ''N'' se înjumătățește.
+
* La fiecare pas ''N'' scade cu 1.
 
* ''E(1, 1, 1, S) = S''.
 
* ''E(1, 1, 1, S) = S''.
  
 
== Tabela ==
 
== Tabela ==
Problema [http://varena.ro/problema/tabela tabela] e o problemă preluată de la [https://infoarena.ro/ infoarena].
+
Problema [http://varena.ro/problema/tabela tabela] este preluată de la [https://infoarena.ro/ infoarena].
  
 +
=== Soluție decrease and conquer ===
 
Pentru a observa regula completăm matricea pînă la latură 8:
 
Pentru a observa regula completăm matricea pînă la latură 8:
  
Line 613: Line 615:
  
 
Acum este mai ușor să observăm reguli:
 
Acum este mai ușor să observăm reguli:
* O matrice de dimensiune 2<sup>N</sup> va conține elemente între 0 și 2<sup>N-1</sup>.
+
* O matrice de dimensiune ''2<sup>N</sup>'' va conține elemente între 0 și ''2<sup>N</sup>-1''.
 
* Dacă împărțim matricea în sferturi, două din sferturi conțin jumate din numere, celelalte două sferturi conțin cea de-a doua jumate din numere.
 
* Dacă împărțim matricea în sferturi, două din sferturi conțin jumate din numere, celelalte două sferturi conțin cea de-a doua jumate din numere.
  
Line 625: Line 627:
  
 
Ce observăm?
 
Ce observăm?
* Putem împărți problema în patru subprobleme, cele patru pătrate de latură ''N/2''.
+
* Putem împărți problema în patru subprobleme, cele patru pătrate de latură ''2<sup>N-1</sup>''.
 
* Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
 
* Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
 
* Trebuie să ajustăm elementul de start pentru subproblema mai mică.
 
* Trebuie să ajustăm elementul de start pentru subproblema mai mică.
Line 631: Line 633:
 
Mai exact:
 
Mai exact:
 
* Dacă linia ''L &le; 2<sup>N-1</sup>'', ea rămîne neschimbată - vorbim de cele două sferturi de sus.
 
* Dacă linia ''L &le; 2<sup>N-1</sup>'', ea rămîne neschimbată - vorbim de cele două sferturi de sus.
* Altfel, vorbim de cele două sferturi de jos, linia ''L'' se ajustează scăzînd ''2<sup>N-1</sup>'', iar elementul de start crește cu ''N/2''.
+
* Altfel, vorbim de cele două sferturi de jos, linia ''L'' se ajustează scăzînd ''2<sup>N-1</sup>'', iar elementul de start crește cu ''2<sup>N-1</sup>''.
 
* Similar, dacă coloana ''C &le; 2<sup>N-1</sup>'', ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
 
* Similar, dacă coloana ''C &le; 2<sup>N-1</sup>'', ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
* Altfel, vorbim de cele două sferturi din dreapta, coloana ''C'' se ajustează scăzînd ''2<sup>N-1</sup>'', iar elementul de start crește cu ''N/2''.
+
* Altfel, vorbim de cele două sferturi din dreapta, coloana ''C'' se ajustează scăzînd ''2<sup>N-1</sup>'', iar elementul de start crește cu ''2<sup>N-1</sup>''.
 
* Dacă atît linia cît și coloana depășesc ''2<sup>N-1</sup>'' elementul de start '''nu se ajustează'''.
 
* Dacă atît linia cît și coloana depășesc ''2<sup>N-1</sup>'' elementul de start '''nu se ajustează'''.
  
Line 639: Line 641:
 
  <math>L' = \begin{cases} L, & \mbox{dacă }  L \leq 2^{N-1}  \\L-2^{N-1},  & \mbox{în caz contrar }. \end{cases}</math>
 
  <math>L' = \begin{cases} L, & \mbox{dacă }  L \leq 2^{N-1}  \\L-2^{N-1},  & \mbox{în caz contrar }. \end{cases}</math>
 
  <math>C' = \begin{cases} C, & \mbox{dacă }  C \leq 2^{N-1}  \\C-2^{N-1},  & \mbox{în caz contrar }. \end{cases}</math>
 
  <math>C' = \begin{cases} C, & \mbox{dacă }  C \leq 2^{N-1}  \\C-2^{N-1},  & \mbox{în caz contrar }. \end{cases}</math>
  <math>S' = \begin{cases} S, & \mbox{dacă }  L \leq 2^{N-1} \mbox{și } C \leq 2^{N-1} \mbox{sau } L > 2^{N-1} \mbox{și } C > 2^{N-1} \\S+N/2 ,  & \mbox{în caz contrar }. \end{cases}</math>
+
  <math>S' = \begin{cases} S, & \mbox{dacă }  L \leq 2^{N-1} \mbox{și } C \leq 2^{N-1} \mbox{sau } L > 2^{N-1} \mbox{și } C > 2^{N-1} \\S+2^{N-1} ,  & \mbox{în caz contrar }. \end{cases}</math>
  
 
În aceste condiții avem relația:
 
În aceste condiții avem relația:
  
  ''E(N, L, C, S) = E(N/2, L', C', S')''
+
  ''E(N, L, C, S) = E(N-1, L', C', S')''
  
 
'''Observații''':
 
'''Observații''':
* La fiecare pas ''N'' se înjumătățește.
+
* La fiecare pas ''N'' scade cu 1.
 
* ''E(1, 1, 1, S) = S''.
 
* ''E(1, 1, 1, S) = S''.
  

Latest revision as of 22:18, 13 February 2020

Fulgerică - rezolvare

Problema cere să se reordoneze cifrele hexa nenule astfel încît să minimizați maximul subnumerelor de K cifre.

Comentarii

  • Algoritmul era banal. De clasa a șasea cel mult.
  • Majoritatea v-ați prins de prima cifră corectă.
  • Mulți ați dat explicații foarte încîlcite.
  • Mulți nu ați dat exemple. Erau importante. Un exemplu bun valora cît patru pagini de explicații.
  • Mulți nu v-ați prins că numărul lui Gigel nu este întotdeauna P123...(k-1), pentru k suficient de mare nu avem destule cifre la rînd.
  • Mulți nu v-ați prins că cele mai mari k-1 cifre trebuie puse la coadă în ordine crescătoare.

Clasament

Nr. Nume F1 F2 F3 Total
1 Petrescu 100 80 75 255
2 Ghica 85 95 50 230
3 Ipate 100 50 70 220
4 Rebengiuc 10 100 100 210
5 Tatomir 90 45 70 205
6 Mușat 0 95 95 190
6 Voicu M 100 15 75 190
8 Dobre 95 15 70 180
9 Iordache 100 10 50 160
10 Voicu T 0 80 65 145
11 Rughiniș 15 20 100 135
12 Petcu 5 14 100 119
13 Asgari 0 10 100 110
13 Mocanu 0 15 95 110
15 Burac 0 0 95 95
16 Nicu 0 90 0 90
17 Badea 10 15 50 75
18 Cojocariu 0 absent 70 70
19 Ilie 0 15 50 65
20 Fares 0 45 10 55
21 Nicola 0 50 0 50
21 Ștefănescu 0 15 35 50
23 Aizic 0 10 35 45
23 Calotă 0 10 35 45
25 Benescu 0 5 35 40
25 Dimulescu 0 10 30 40
27 Popescu 0 0 35 35
28 Marcu 5 10 5 20
28 Stancu 0 20 0 20
30 Grecu 0 18 0 18
31 Cadîr 0 10 0 10
31 Teodorescu 0 10 0 10
33 Chivu 0 5 0 5
34 Hossu 0 motivat 0 0
34 Togan 0 0 0 0

Soluție

Pentru reordonarea numărului X setam ca primă cifră pe 16-K. Apoi așezam restul cifrelor, în ordine. Numărul lui Gigel era format din primele K cifre ale acestei reordonări.

Iată programul (14 linii de cod efectiv):

char cf[] = "0123456789ABCDEF";

// afisam numarul lui Gigel
fputc( cf[16 - k], fout );
kc = i = 0;
while ( kc < k - 1 ) // mai avem de afisat cifre
  if ( ++i != 16 - k ) {
    fputc( cf[i], fout );
    kc++;
  }
fputc( '\n', fout );

// afisam reordonarea numarului X
fputc( cf[16 - k], fout );
for ( i = 1; i < 16; i++ )
  if ( i != 16 - k )
    fputc( cf[i], fout );
fputc( '\n', fout );

Demonstrație de funcționare corectă

Care va fi prima cifră a numărului lui Gigel, din K cifre? Dacă plasăm K-1 cele mai mari cifre la coada lui X îl putem împiedica pe Gigel să ia un număr care începe cu acele cifre. Dar nu îl putem împiedica să formeze un număr care începe cu a Ka cea mai mare cifră, deoarece ea rămîne expusă.

Știm că numărul lui Gigel începe cu cifra 16-K. Cum facem să minimizăm restul numărului? Este clar că vom așeza restul cifrelor în ordine crescătoare. Nu putem forma un număr mai mic.

Tema - rezolvări

Latin

Problema latin este un exerciţiu introductiv de divide et impera, în scop didactic.

Comentarii generale

  • Unii din voi nu au folosit divide et impera. Acesta era scopul temei. Divide et impera este, în principiu, recursiv. Dacă ați scris un program iterativ, nu era ceea ce se cerea. Dacă ați scris un program recursiv dar care se poate transforma ușor în iterativ, nu era ceea ce se cerea. Dacă ați completat matricea de sus-stînga și apoi ați copiat-o în celelalte trei matrice, nu era ceea ce se cerea. Cine nu a rezolvat cu divide et impera: Aizic, Benescu, Chivu, Cojocariu, Dobre, Hossu, Ipate, Popescu, Teodorescu.
  • Avertismente: Ghica (nici o sursă), Stancu (nici o sursă).
  • Total: 11 copii din 35 nu au exersat cerința.

Soluție

Ideea este să împărţiţi pătratul de latură 2n în patru pătrate de latură 2n-1. Pătratele rezultate sînt pătrate latine la care se adună o constantă fiecărui număr. De asemenea, pătratele rezultate sînt egale în pereche, pe diagonale.

Putem, deci, defini problema:

Latin(LAT, L, C, S) = pătratul latin de latură LAT, ce începe în matrice la coordonatele (L, C) cu un element egal cu S.

Pentru a completa un pătrat latin vom completa cele patru sferturi ale sale. În fiecare sfert vom trimite latura ca fiind jumate din latura curentă, coordonatele corecte (L, C) și primul element.

Mai exact, vom apela:

Latin( LAT / 2, L, C, S )
Latin( LAT / 2, L, C + LAT / 2, S + LAT / 2 )
Latin( LAT / 2, L + LAT / 2, C, S + LAT / 2 )
Latin( LAT / 2, L + LAT / 2, C + LAT / 2, S )

Ne vom opri din recursivitate atunci cînd 'LAT devine 1, caz în care vom seta matricea latin[L][C] la valoarea S.

Iată o implementare simplă (31 linii de cod efectiv):

#include <stdio.h>

int latin[1024][1024];

// genereaza patratul latin de latura lat ce porneste la (l, c) cu start
void genereazaLatin( int lat, int l, int c, int start ) {
  if ( lat == 1 )
    latin[l][c] = start; // cazul de oprire, patrat latin de latura 1
  else {
    genereazaLatin( lat / 2, l, c, start ); // stinga-sus
    genereazaLatin( lat / 2, l, c + lat / 2, start + lat / 2 ); // dreapta-sus
    genereazaLatin( lat / 2, l + lat / 2, c, start + lat / 2 ); // stinga-jos
    genereazaLatin( lat / 2, l + lat / 2, c + lat / 2, start ); // dreapta-jos
  }
}

int main() {
  FILE *fin, *fout;
  int n, l, c, lat;

  fin = fopen( "latin.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  // calculeaza lat = 2^n
  lat = 1;
  while ( n-- > 0 )
    lat *= 2;
  // genereaza patratul latin de latura lat ce porneste la (0, 0) cu numarul 1
  genereazaLatin( lat, 0, 0, 1 );

  // afisare
  fout = fopen( "latin.out", "w" );
  for ( l = 0; l < lat; l++ ) {
    for ( c = 0; c < lat; c++ )
      fprintf( fout, "%d ", latin[l][c] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Pav

Problema pav a fost dată la Lot IS 2008. Cu toate acestea este, cred, destul de ușoară.

Comentarii generale

  • Mulți dintre voi au reușit o soluție. Bravo!
  • Majoritatea dintre voi ați duplicat mult cod: ați scris circa 16 apeluri la funcția recursivă.
  • Nu vă complicați viața. Programul poate fi foarte scurt și simplu.

Soluție

Am discutat soluția la oră. Piața se împarte în patru sferturi. Unul din ele conține pomul, deci se reduce la o problemă mai mică. Celelalte trei pot fi și ele reduse la probleme mai mici, dacă plasăm artificial pomi fictivi: vom plasa o piesă L peste pătratele lor de la centru.

Iată o implementare simplă (42 linii de cod efectiv):

#include <stdio.h>

#define MAXN 9
#define MAXLAT 512

int nrdala;
int piata[MAXLAT][MAXLAT];

// coordonatele pomului sint relative la startl, startc - e mai simplu asa
void pavare( int startl, int startc, int n, int lpom, int cpom ) {
  int l, c, lcad, ccad, curent;

  if ( n > 1 ) {
    curent = nrdala++; // tinem minte dala de asezat pe centru
    n /= 2; // nu mai avem nevoie decit de dimensiunea pe jumate
    lcad = lpom / n; // coordonata linie cadran pom - 0 sau 1
    ccad = cpom / n; // coordonata coloana cadran pom - 0 sau 1
    for ( l = 0; l < 2; l++ ) // parcurgem cele 4 cadrane
      for ( c = 0; c < 2; c++ )
        if ( l == lcad && c == ccad )
          // problema care contine pomul
          pavare( startl + l*n, startc + c*n, n, lpom % n, cpom % n );
        else {
          // problema generala, nu contine pom, pavam cu 'curent'
          piata[startl + n - 1 + l][startc + n - 1 + c] = curent;
          pavare( startl + l*n, startc + c*n, n, (n-1)*(1-l), (n-1)*(1-c) );
        }
  }
}

int main() {
  FILE *fin, *fout;
  int n, l, c, lat;

  fin = fopen( "pav.in", "r" );
  fscanf( fin, "%d%d%d", &n, &l, &c );
  fclose( fin );

  lat = 1;
  while ( n-- > 0 )
    lat *= 2;
  nrdala = 1;
  pavare( 0, 0, lat, l-1, c-1 );
  
  fout = fopen( "pav.out", "w" );
  for ( l = 0; l < lat; l++ ) {
    for ( c = 0; c < lat; c++ )
      fprintf( fout, "%d ", piata[l][c] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Forma

Problema forma a fost data la olimpiada locală 2012, clasa a 8a.

Comentarii generale

  • Pare că v-a dat multă bătaie de cap.
  • Mulți ați scris cod lung și încîlcit.
  • Unii din voi au folosit quicksort pentru a determina forma de bază a numărului! E o exagerare, codul devine mai lung și mai ineficient. Codul scris normal, cu vectori de frecvență, are circa 19 linii.
  • Avertismente: Aizic (nici o sursă)

Soluție

Soluția este clară, implementarea poate da mici bătăi de cap. Avem două părți distincte:

  • Calculul formei de bază pentru un număr de la intrare.
  • Sortarea formelor de bază și calculul secvenței maxime de numere identice.

Calculul formei de bază este similar cu problema siruri1 pe care am discutat-o în clasa a cincea. O idee foarte simplă este următoarea:

  • Construim vectorul de frecvență al cifrelor. Dacă dăm peste dubluri ne oprim, numărul nu are formă de bază.
  • Parcurgem în ordine crescătoare vectorul de frecvență al cifrelor și, peste tot unde găsim 1 setăm o valoare contor, mereu crescătoare. Astfel vom avea, pentru fiecare cifră, a cîta este ea în ordine crescătoare.
  • Descompunem numărul original în cifrele sale și, pe baza vectorului de frecvență, construim forma de bază. Forma de bază este formată din aceleași cifre ca și numărul original și în aceeași ordine, însă în care înlocuim fiecare cifră cu valoarea ei din vectorul de frecvență.

Iată o implementare posibilă (72 linii de cod efectiv):

#include <stdio.h>

int v[10000];

int fbaza( int a ) {
  int cf[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  int ret_val, i, p10, ac = a;

  while ( ac && ++cf[ac % 10] == 1 ) // construim vect frecv cifre
    ac /= 10;

  ret_val = 0;
  if ( ac == 0 ) { // daca toate cifrele sint distincte
    // calculeaza pozitia fiecarei cifre in vectorul ordonat
    for ( i = 0; i < 10; i++ )
      if ( cf[i] )
        cf[i] = ++ac;

    // compunem forma de baza
    p10 = 1;
    while ( a ) {
      ret_val += cf[a % 10] * p10;
      a /= 10;
      p10 *= 10;
    }
  }

  return ret_val;
}

void myqsort( int st, int dr ) {
  int aux, p = v[(st + dr) >> 1], s = st, d = dr;

  while ( v[s] < p )
    s++;
  while ( v[d] > p )
    d--;

  while ( s < d ) {
    aux = v[s];
    v[s] = v[d];
    v[d] = aux;

    do
      s++;
    while ( v[s] < p );

    do
      d--;
    while ( v[d] > p );
  }

  if ( st < d )
    myqsort( st, d );
  if ( d + 1 < dr )
    myqsort( d + 1, dr );
}

int main() {
  FILE *fin, *fout;
  int a, b, n, i, na, bb, ne, max, nmax;

  fin = fopen( "forma.in", "r" );
  fscanf( fin, "%d%d", &b, &n );
  bb = fbaza( b );
  ne = na = 0;
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &a );
    if ( (v[na] = fbaza( a )) > 0 ) { // are cifre distincte
      if ( v[na] == bb ) // am mai gasit un numar echivalent cu b
        ne++;
      na++;
    }
  }
  fclose( fin );

  myqsort( 0, na-1 ); // sortam vectorul de numere in forma de baza
  // calculam numarul maxim de elemente identice
  max = nmax = 1;
  for ( i = 1; i < na; i++ )
    if ( v[i] == v[i-1] ) {
      if ( ++max > nmax )
        nmax = max;
    } else
      max = 1;

  fout = fopen( "forma.out", "w" );
  fprintf( fout, "%d\n%d\n", ne, nmax );
  fclose( fout );

  return 0;
}

Tema opțională - rezolvări

Rezolvări aici [1]

Lecţie - divide et impera, continuare

ZParcurgere

Problema zparcurgere a fost dată la concursul Grigore Moisil by net 2006.

Soluție

Cum o rezolvăm?

În problemele pe care încercăm să le rezolvăm cu tehnica divide et impera vom încerca să definim problema de rezolvat. Astfel, în acest caz, definim:

E(N, L, C) = elementul din matricea de latură 2N aflat la poziția (L, C)

Observăm că putem descompune problema în patru subprobleme, în care matricele sînt un sfert din matricea originală. Dar există o diferență: valorile din matrice nu pornesc de la 1. De aceea trebuie să introducem un nou parametru, elementul de start:

E(N, L, C, S) = elementul din matricea de latură 2N aflat la poziția (L, C) cu elemente care încep cu S

Ce observăm?

  • Putem împărți problema în patru subprobleme, cele patru pătrate de latură 2N-1.
  • Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
  • Trebuie să ajustăm elementul de start pentru subproblema mai mică.

Mai exact:

  • Dacă linia L ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi de sus.
  • Altfel, vorbim de cele două sferturi de jos, linia L se ajustează scăzînd 2N-1, iar elementul de start crește cu jumate din elementele matricei, adică 2N-1·2N.
  • Similar, dacă coloana C ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
  • Altfel, vorbim de cele două sferturi din dreapta, coloana C se ajustează scăzînd 2N-1, iar elementul de start crește cu un sfert din elementele matricei, adică 2N-1·2N-1.

Astfel:





În aceste condiții avem relația:

E(N, L, C, S) = E(N-1, L', C', S'')

Observații:

  • La fiecare pas N scade cu 1.
  • E(1, 1, 1, S) = S.

Tabela

Problema tabela este preluată de la infoarena.

Soluție decrease and conquer

Pentru a observa regula completăm matricea pînă la latură 8:

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

Acum este mai ușor să observăm reguli:

  • O matrice de dimensiune 2N va conține elemente între 0 și 2N-1.
  • Dacă împărțim matricea în sferturi, două din sferturi conțin jumate din numere, celelalte două sferturi conțin cea de-a doua jumate din numere.

Să definim problema de rezolvat:

E(N, L, C) = elementul din matricea de latură 2N aflat la poziția (L, C)

Observăm că putem descompune problema în patru subprobleme, în care matricele sînt un sfert din matricea originală. Dar există o diferență: valorile din cele patru matrice nu pornesc mereu de la 0. De aceea trebuie să introducem un nou parametru, elementul de start:

E(N, L, C, S) = elementul din matricea de latură 2N aflat la poziția (L, C) cu elemente care încep cu S

Ce observăm?

  • Putem împărți problema în patru subprobleme, cele patru pătrate de latură 2N-1.
  • Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
  • Trebuie să ajustăm elementul de start pentru subproblema mai mică.

Mai exact:

  • Dacă linia L ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi de sus.
  • Altfel, vorbim de cele două sferturi de jos, linia L se ajustează scăzînd 2N-1, iar elementul de start crește cu 2N-1.
  • Similar, dacă coloana C ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
  • Altfel, vorbim de cele două sferturi din dreapta, coloana C se ajustează scăzînd 2N-1, iar elementul de start crește cu 2N-1.
  • Dacă atît linia cît și coloana depășesc 2N-1 elementul de start nu se ajustează.

Astfel:




În aceste condiții avem relația:

E(N, L, C, S) = E(N-1, L', C', S')

Observații:

  • La fiecare pas N scade cu 1.
  • E(1, 1, 1, S) = S.

Ziua regelui

Un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă cîți sclavi mor, dar îi pasă cîți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?

Problema are mai multe soluții. Să vedem cum am putea să folosim divide et impera.

Să împărțim sticlele în două jumătăți, 500 și 500. Să rezolvăm problema pentru 500. Să presupunem că vom avea nevoie de x sclavi și vom afla cu siguranță sticla. Să presupunem că sticlele sînt numerotate de la 1 la 500. Cînd adăugăm încă 500 de sticle le vom numerota și pe ele de la 1 la 500, dar ținînd cont că sînt în grupa 2.

Cum vom proceda? Dacă un sclav dintre cei x bea din sticla y din grupa originală (să-i spunem 1), el va bea, acum și din sticla y din grupa 2. La final vom putea identifica o sticlă posibil otrăvită din grupa 1 și una posibil otrăvită din grupa 2. Dar noi știm că doar una din sticle poate fi otrăvită.

Pentru a diferenția între cele două sticle vom mai folosi un sclav, numărul x+1, care va bea din toate sticlele din grupa 1. Astfel, la final, vom putea afla care din cele două sticle este cea otrăvită: dacă sclavul x+1 moare sticla otrăvită e cea din grupa 1, altfel e cea din grupa 1.

Fulgerică (test fulger)

Găsiți un algoritm la următoarea problemă și explicați-l pe o foaie de hîrtie. Dacă nu vă descurcați să îl explicați puteți scrie cod. Sau formule matematice. Sau puteți scrie din toate trei. Important este ca algoritmul să se înțeleagă și să fie corect. Atenție! Spre deosebire de varena, vi se cere un algoritm corect, echivalentul unei rezolvări care să treacă toate testele. Nu gîndiți la modul "cum fac să iau cît mai multe puncte". Nu se acceptă "mînăreli". Voi corecta lucrările personal. Nu vă concentrați pe citire, sau scriere.

Problema tabel

Problema cere să memorați valori asociate cu numere și să afișați răspunsuri la întrebări de forma "ce valoare este asociată cu un număr?"

Mai exact: se dau T teste la intrare. Un test constă din:

  • N - numărul de operații
  • Apoi N operații. Operațiile pot fi:
    • S x y - cu semnificația că numărului x îi asociem numărul y
    • V x - cere să se afișeze valoarea asociată lui x (sau -1 dacă x nu are valoare asociată)

Restricții

  • 1 ≤ T ≤ 10
  • 0 ≤ N ≤ 100 000
  • Din cele N operații maxim 65535 sînt de tip S
  • 0 ≤ x < 50 milioane
  • 0 ≤ y ≤ 65535
  • Unei valori îi putem asocia cel mult o valoare la un moment dat. Dacă asociem o nouă valoare, ea va fi cea reținută.

Restricții program

  • Timp de executare: 0.2s (puteți considera că faceți parsingul intrării, deci citirea nu este o problemă)
  • Memorie disponibilă: 100MB
  • Nu folosiți structuri de date pe care nu le-am predat!

Exemplu

tabel.in tabel.out Explicații

2
5
S 10 0
V 9
V 10
S 9 100
V 9
4
V 10
S 10 15
V 9
V 10

-1
0
100
-1
-1
15

T=2 deci avem două teste la intrare.

Primul test are N=5, deci va avea cinci operații.
Prima operație asociază lui 10 valoarea 0.
A doua operație cere valoarea asociată lui 9. Nu avem valoare asociată, deci afișăm -1.
A treia operație cere valoarea asociată lui 10. Vom afișa 0.
A patra operație asociază lui 9 valoarea 100.
A cincea operație cere valoarea asociată lui 9. Vom afișa 100.

Al doilea test are N=4, deci va avea patru operații.
Prima operație cere valoarea asociată lui 10. Fiind vorba de un test nou, nu avem valoare asociată, deci vom afișa -1.
A doua operație asociază lui 10 valoarea 15.
A treia operație cere valoarea asociată lui 9. Nu avem valoare asociată, deci vom afișa -1.
A patra operație cere valoarea asociată lui 10. Vom afișa 15.

Temă

Rezolvări aici [2]