Clasa a VI-a lecția 15 - 17 ian 2019

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Problema robinson

Comentarii generale

  • Mulți dintre voi ați trimis surse vechi, scrise înainte să învățați bordarea matricelor și vectori de direcție, sau nu ați folosit aceste instrumente: Benescu, Cadîr, Coman, Dragomir, Mocanu, Mușat, Petcu, Ștefănescu, Togan). Acesta era scopul temei, să aplicăm cele învățate.

Rezolvare

Problema robinson a fost dată la ONI 2005 clasa a 6a. Pentru o rezolvare frumoasă vom folosi cele două tehnici standard:

  • Vom folosi vectori de direcție pentru a calcula ușor noua poziție a lui Robinson.
  • Vom borda matricea cu o bordură inițializată cu -1, valoarea ce semnifică faptul că acea căsuță a mai fost vizitată.

Apoi, pentru punctul a) vom calcula valorile din matrice conform formulei descrise în enunț. Pentru punctul b) vom avansa poziția lui Robinson pînă ce dăm peste o valoare -1.

Iată programul:

#include <stdio.h>

int teren[22][22];
int ldif[4] = { -1, 0, 1, 0 };
int cdif[4] = { 0, 1, 0, -1 };

int main() {
  FILE *fin, *fout;
  int m, n, l, c, i, j, dir;

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

  // bordam matricea cu -1
  for ( i = 0; i <= m+1; i++ )
    teren[0][i] = teren[i][0] = teren[m+1][i] = teren[i][m+1] = -1;

  // pregatim matricea cu valorile recoltei
  teren[1][1] = n;
  for ( i = 2; i <= m; i++ )
    teren[i][1] = teren[1][i] = teren[1][1] + i - 1;
  for ( i = 2; i <= m; i++ )
    for ( j = 2; j <= m; j++ )
      teren[i][j] = (teren[i-1][j] + teren[i][j-1]) % 1000;

  fout = fopen( "robinson.out", "w" );
  fprintf( fout, "%d\n", teren[m][m] ); // afisam punctul a)

  // incepe simularea
  while ( teren[l][c] != -1 ) { // nu am mai fost aici, continuam
    // avem coordonate valide, deci le afisam
    fprintf( fout, "%d %d\n", l, c );
    dir = teren[l][c] % 4; // calculam restul
    teren[l][c] = -1;      // marcam faptul ca am mai fost aici
    l += ldif[dir]; // calculam noua linie
    c += cdif[dir]; // calculam noua coloana
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Completarea matricei este O(m2). Simularea cere timp proporțional cu numărul de parcele vizitate. Deoarece el se oprește cînd iese din matrice sau cînd se întoarce la o parcelă deja vizitată rezultă că numărul maxim de parcele vizitate este numărul total de parcele, adică tot O(m2) (în realitate va fi mult mai mic, dar nu modifică complexitatea totală din cauza completării matricei). Rezultă o complexitate totală de O(m2).

Cîtă memorie folosim? Precum se vede O(m2).

Problema joc 3

Problema joc3 a fost dată la ONI 2011 clasa a 6a. Este o problemă tipică de simulare, simplă, neavînd contribuții creative: ceea ce trebuie să calculăm este descris direct în enunțul problemei. Într-adevăr, o problemă descriptivă.

Vom folosi indici de la zero și nu de la unu. În acest fel noile poziții ale copiilor se pot calcula ușor cu aritmetică modulo n. La final vom afișa pozițiile plus unu.

Am putea folosi doi vectori de frecvență pentru a afla atunci cînd unul din copii sare pe o căsuță unde a mai sărit. Acest lucru nu este necesar. Dacă unul din copii va sări pe o căsuță unde a mai sărit ea va fi neapărat căsuța numărul unu. De aceea putem testa doar indicele copiilor. Drept pentru care vom folosi un vector de frecvență comun celor doi copii doar pentru a contoriza căsuțele pe care s-a sărit.

Iată programul:

#include <stdio.h>

int calcat[40000];

int main() {
  FILE *fin, *fout;
  int n, x, y, b, r, t, sarituri;

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

  // incepe simularea
  b = r = 0;
  t = n - 1; // n - 1 sectoare necalcate
  calcat[0] = 1; // sector calcat de macar unul din copii
  sarituri = 0;
  do {
    b = (b + x) % n;     // il avansam pe Bogdan
    r = (r - y + n) % n; // il avansam pe Rares
    sarituri++; // am mai avansat o saritura pina la pozitia curenta
    if ( calcat[b] == 0 ) // scadem numar sectoare calcate de bogdan
      t--;
    if ( r != b && calcat[r] == 0 ) // scadem numar sectoare calcate de rares
      t--;
    calcat[b] = calcat[r] = 1; // marcam sectoare calcate
  } while ( b != 0 && r != 0 && b != r );

  fout = fopen( "joc3.out", "w" );
  fprintf( fout, "%d %d %d %d\n", t, sarituri, b + 1, r + 1 );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Ea este proporțională cu numărul de sărituri ale unuia din copii. Dar numărul de sărituri nu poate depăși numărul de sectoare, deoarece copiii se opresc atunci cînd ajung într-un sector unde au mai sărit. Rezultă complexitatea O(n). Memoria folosită este, de asemenea, O(n).

Problema furnica

Comentarii generale

Comentariile lui Mihai la această problemă sînt:

  • Felicitari celor care au facut problema cu punctaj maxim si solutia optimă: Badea, Ilie, Nicu, Rebengiuc, Voicu.
  • De remarcat si cei care au obtinut punctaj maxim, insa cu mici abateri de la solutia optima: Cojocariu, Grecu, Petcu, Tatomir. De mentionat si cei din afara concursului: Mocanu si Nicola.
  • Cei care au obtinut punctaje insa nu au folosit vectori de directie: Musat, Stefanescu, Togan, Benescu.
  • Abaterea cea mai intalnita de la solutia optima a fost calculul la inceput al matricei de valori, cu care au lucrat ulterior. Nu s-au prins ca pot genera valoarea atunci cand ajung in pozitia respectiva.
  • Au fost cativa elevi care au declarat vectorii de directie cu 9 pozitii in loc de 8: Aizic, Burac.
  • Cativa elevi au pierdut puncte din neatentie: Asgari, Fares, Hossu, Ipate, Stoian.
  • Unii elevi nu au înțeles vectorii de direcție.
  • Unii din elevi trimit surse cu 'printf' de depanare, foarte periculos.
  • Au fost o parte care nu au urcat rezolvarile in timpul concursului temă: Benescu, Cadîr, Mocanu, Nicola, Rughinis. Îi scuzăm căci știu că unii din ei au motive solide.
  • Cei care nu au trimis nici o sursa: Coman, Chivu, Cojocaru, Iordache, Stancu.

Comentarii individuale

Comentariile individuale ale lui Mihai sînt:

Grupa de dimineață

  • Aizic Albert (72) vectorii de directie sunt declarati cu 9 pozitii, prima fiind inutila. Mai multa atentie. Imi este greu sa urmaresc ce a incercat sa faca, face calcule multe la nivel de valori care nu cred ca sunt corecte;
  • Badea Lucian Andrei (100) rezolvare exacta, felicitari!
  • Benescu Alexandru Andrei (100) nu foloseste vectori de directie, a folosit un switch;
  • Burac Alexandru (95) vectorii de directie sunt declarati cu 9 pozitii, prima fiind inutila. Mai multa atentie. Are o solutie mai intortocheata, in sensul in care isi calculeaza matricea de valori pe care si-o majoreaza de la inceput cu 2. Dar tot acolo ajunge.
  • Calota Andrei (75) Rezolvare optima la cea de-a cincea incercare. Se pare ca a inteles mai greu cum sa isi calculeze valorile din matrice din mers. Mi-a placut consecventa in schimb :)
  • Chivu Andreea Ana (0) Nu a incercat deloc problema
  • Cojocariu Dragos (100) foloseste o matrice 3D, pentru a avea o matrice de valori si una de frecventa. Solutie de punctaj maxim, dar nu cred ca era necesar acest artificiu.
  • Cojocaru Ioana-Amalia (0) Nu a incercat deloc problema
  • Coman Mihai (0) Nu a incercat deloc problema
  • Dragomir Denisa Elena (9) din ce imi pare mie, nu prea a inteles cum functioneaza vectorii de directie. Desi i-a declarat, tot foloseste multe conditii de if ca sa simuleze deplasarea furnicii...
  • Grecu Tudor (100) rezolvarea optima cu punctaj maxim, doar ca isi calculeaza matricea de valori
  • Hossu Alexandru (95) se apropie de solutia optima. Atat doar ca nu lucreaza cu o matrice asociata ci o calculeaza si apoi o prelucreaza. Chiar si asa, codul este destul de direct. A reusit din a doua submisie;
  • Iordache Rares Mihai (0) Nu a incercat deloc problema
  • Mocanu Mihai (100) cumva acelasi cod cu cel optim. Operatiile le face la nivel de indici in cadrul vectorului de directie si apoi le aplica matricei pentru miscare. Ultima parte a codului este identica cu cea din cel optimizat
  • Musat Tudor (100) nu foloseste vectori de directie si nici macar switch. Mai multe conditii if cu conditii compuse.
  • Nicola Victor Teodor (100) foloseste structuri si isi generaza matricea de valori. Algoritmul este corect si se apropie de forma optima.
  • Petcu Ana-Maria (100) rezolvarea optima cu punctaj maxim, doar ca isi calculeaza matricea de valori
  • Rebengiuc Mircea (100) rezolvare exacta, felicitari!
  • Rughinis Remus (90) si-a generat matricea de valori si a lucrat pe ea. Codul este complicat si nu trateaza toate testele. Am incercat sa il urmaresc insa mi-a fost foarte dificil sa gasesc problema
  • Stefanescu Ecaterina (81) nu a folosit vectori de directie, a folosit switch. Chiar si asa, nu a reusit sa rezolve toate testele;
  • Stoian Daria (60) isi creeaza matricea de valori; La ultima sursa trimisa care a punctat, nu a comentat printf. Problema codului ei este ca in cazul limita, cand furnica nu calca de doua ori pe nici o patratica, contorul trebuie sa porneasca de la 1 pentru ca nu numare originea. Am testat mica modificare si puncteaza maxim. Mai multa atentie!
  • Togan Teodor (85) nu a folosit vectori de directie, a folosit switch.
  • Voicu Tudor (100) rezolvare exacta, felicitari!

Grupa de după-amiază

  • Asgari Armin (95) isi creeaza matricea de valori si face o verificare care nu este necesara si anume daca furnica merge in matrice. La final putea optimiza codul, prin a pune conditiile intr-o singura parcurgere a matrice. Mai multa atentie!
  • Cadir Timur (0) exista o intentie, dar implementarea nu cred ca poate fi facuta asa...
  • Dobre Radu (95) isi genereaza matricea cu valori inca de la inceput. A preferat sa calculeze cu valori foarte mari drumul pe care l-a batatorit furnica, in aceiasi matrice. Imi pare usor complicat si inutil. Intuitia imi spune ca se poate gresi destul de usor in aceasta solutie. Dar se pare ca nu a avut alta idee, a tot incercat
  • Fares Yusuf (95) rezolvare exacta, insa din a doua incercare;
  • Ilie Luca Mihai (100) rezolvare exacta, felicitari!
  • Ipate Elisa (95) are solutia optima, insa are o penalizare de o submisie. In prima submisie, eroarea consta in faptul ca numarul maxim este declarat de la 0. Mai multa atentie!
  • Marcu Ilinca (85) la a treia iteratie se apropie de varianta optima. Genereaza matricea de valori;
  • Nicu Alexandru (100) rezolvare exact, felicitari;
  • Stancu Andrei (0) Nu a incercat deloc problema
  • Tatomir Teodor (100) rezolvare buna, insa genereaza matricea de valori initial si lucreaza pe ea;
  • Teodorescu Nicolas (95) rezolvare buna, doar ca isi creeaza mai intai matricea de valori; A doua submisie.

Rezolvare

Problema furnica a fost dată la OJI 2007 clasa a 6a. Pentru rezolvarea frumoasă vom folosi vectori de direcție. Nu avem nevoie de bordare deoarece se garantează că drumul furnicii nu va ieși din matrice.

Rezolvarea este destul de directă. Aș vrea să menționez două aspecte interesante:

  • Nu este nevoie să stocăm valorile firimiturilor. Ele sînt ușor calculabile pe baza poziției curente. În acest fel scăpăm nu numai de o inițializare, ci și de tratamentul special al unei căsuțe în care a mai fost furnica (poate ar trebui să o facem negativă și crescătoare, sau, alternativ, să pornim de la un număr mai mare ca 5). Vom stoca, în schimb, o matrice de frecvență care memorează pentru fiecare poziție de cîte ori a trecut furnica prin acea poziție.
  • Latura matricei, n, nu este necesară. Într-adevăr, din deplasarea furnicii vom ști coordonatele ei minime și maxime. La final putem căuta în matricea de frecvență între acele coordonate. În fapt, acest lucru ne-ar proteja împotriva testelor greșite. În primul test, cel original, furnica depășea coordonata n, ceea ce face un program care ține cont de n să greșească. Un program care ignoră n va funcționa. Pe vianuarena testul a fost însă corectat. Programul de exemplu, de mai jos, folosește și el n.

Iată programul:

#include <stdio.h>

int trec[100][100];
int dlin[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dcol[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int main() {
  FILE *fin, *fout;
  int n, k, l, c, i, dir, suma, max, nrmax;

  fin = fopen( "furnica.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  trec[l = 0][c = 0] = 1;
  suma = 2;
  // incepe simularea
  nrmax = max = 1;
  for ( i = 0; i < k; i++ ) {
    fscanf( fin, "%d", &dir ); // citim directia
    dir--;                     // ajustam directia (vector de la zero)
    l += dlin[dir];      // calculam noua linie
    c += dcol[dir];      // calculam noua coloana
    if ( trec[l][c] == 0 )
      suma += (l + c + 2) % 6; // adunam firimiturile
    trec[l][c]++;              // marcam ca am trecut pe aici
    // calcul casute prin care s-a trecut de un numar maxim de ori
    if ( trec[l][c] > max ) { // daca este mai mare
      max = trec[l][c];       // vedem prima oara un astfel de maxim
      nrmax = 1;
    } else if ( trec[l][c] == max ) // daca este egal
      nrmax++;                      // marim nr. de aparitii ale maximului
  }
  fclose( fin );

  fout = fopen( "furnica.out", "w" );
  fprintf( fout, "%d %d\n", suma, nrmax );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Simularea mișcărilor furnicii este O(k), incluzînd testele pentru găsirea numărului de maxime, deci complexitatea totală este O(k). Memoria folosită este O(n2).

Rezolvări aici [1]

Lecţie

Am discutat probleme de simulare care vă rămîn ca temă: bile2, ouă, turn.

Problema bile 2

Problema bile 2 a fost dată la concursul .campion 2005. Ea poate fi considerată o problemă de simulare, deoarece avem un sistem "real" similar cu sistemul Loto și ni se cere să executăm o serie de comenzi asupra acestui sistem pentru a obține o anumită ordine a bilelor.

Problema poate părea descurajantă, la prima vedere. Însă cu ordine și disciplină ea devine ușoară. Să observăm următoarele:

  • La fiecare pas avem doar două operații pe care le putem face:
    • I - introdu o bilă în zona B
    • O - scoate o bilă din zona B afară
  • Nu putem scoate bile afară decît din zona B, folosind operația O

Drept care rezultă că nu avem prea multe de gîndit. La fiecare pas vom proceda astfel:

  • Dacă în zona B avem la vîrf bila ce se cere la ieșire, apăsăm O și scoatem bila din zona B
  • În caz contrar apăsăm I pentru a introduce o bilă de la intrare în zona B.

Cînd se termină simularea?

  • Fie cînd am extras toate bilele, respectiv am apăsat O de n ori. Acesta este cazul de succes, am reușit.
  • Fie cînd vrem să mai introducem o bilă din zona A în zona B și nu mai avem bile, adică am apăsat I de n ori și am mai dori să apăsăm o dată. Acesta este cazul de eșec.

Sfatul meu este să folosiți o buclă standard de simulare, cu bucla de forma:

  while ( !gata ) {
    // ...
    // cod care execută simularea și schimbă variabila gata 
    // atunci cînd trebuie oprită simularea
    // ...
  }

Problema ouă

Problema ouă a fost dată la ONI 2007, clasa a 6a. Este o problemă tipică de simulare. Vom memora coordonatele iepurașilor în doi vectori de coordonate în matrice. De asemenea vom memora direcția fiecărui iepuraș, un număr între 0 și 3; precum și suma ouălor colectate de fiecare iepuraș. Vom folosi și o matrice în care vom memora valorile ouălor neculese încă. Atunci cînd un iepuraș ajunge în matrice peste un ou el va colecta acel ou și va reseta elementul din matrice la zero.

Vom folosi tehnicile deja cunoscute:

  • Vom borda matricea cu -1 pentru a testa ușor ieșirea iepurașilor de pe pajiște.
  • Vom folosi cei doi vectori de direcție pentru deplasarea iepurașilor

Pentru a nu mai deplasa iepurașii care au ieșit de pe pajiște vom seta direcția lor la -1. Vom memora numărul de iepurași încă activi și ne vom opri atunci cînd avem zero astfel de iepurași. Dacă codificăm corect cele patru direcții vom putea face schimbarea de direcție adunînd unu modulo 4:

dir = (dir + 1) % 4;

Problema turn

Problema turn a fost dată la ONI 2007, clasa a 6a.

Forța brută

Soluția directă este să simulăm eliminările de cuburi. Vom căuta prima secvență de numere identice de lungime cel puțin k. Apoi vom elimina acea secvență. Putem face eliminarea deplasînd elementele vectorului, sau înlocuind valorile cu o valoare care nu este cifră, de exemplu -1. Odată ce am eliminat o secvență ne vom deplasa înapoi pînă la începutul secvenței anterioare, pentru a verifica și lungimea acesteia. Astfel vom verifica și elimina toate secvențele posibile.

Aceasta este soluția comisiei. Deoarece există posibilitatea să parcurgem pe medie n/2 elemente din vector de n/2 ori această soluție este pătratică, O(n2). Există, însă, o soluție mai bună.

Soluția optimă

Putem memora vectorul de cuburi într-o forma "compactată": vom memora pentru fiecare cub din turn de cîte ori apare. Vom memora doi vectori, unul cu valorile cuburilor și unul cu numărul lor de apariții consecutive. Astfel, vectorul:

1 1 5 5 5 2 3 3 3 3 2 2 4 5

va fi memorat astfel:

vectorul cub: 1 5 2 3 2 4 5
vectorul nr:  2 3 1 4 2 1 1

Vom construi acești vectori pe măsură ce citim cuburile la intrare. În momentul cînd primim un cub identic cu cel din-nainte vom incrementa elementul nr[i]. Dacă primim un cub diferit vom verifica dacă putem elimina ultima pereche, dacă nr[i] este mai mare decît k. Apoi, fie adăugăm noul cub cu număr de apariții unu, fie îl adăugăm la perechea din vîrf dacă el este egal cu cubul care a rămas la vîrf. Continuăm algoritmul în acest fel pînă ce terminăm cuburile de la intrare.

Această metodă face un număr constant de operații pentru fiecare cub. De aceea are complexitate O(n). Iată un program bazat pe aceste idei:

Temă

Tema 15 clasa a 6a

  • bile2 dată la .campion 2005
  • ouă dată la ONI 2007 clasa a 6a
  • turn dată la ONI 2007 clasa a 6a

Rezolvări aici [2]