Clasa a VI-a lecția 15 - 17 ian 2019: Difference between revisions

From Algopedia
Jump to navigationJump to search
 
(No difference)

Latest revision as of 10:32, 19 March 2021

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.

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.

Rezolvări aici [1]

Lecţie

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-01-17-clasa-6-lectie-info-15-720p.mp4</html5media>

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]