Clasa a VI-a lecția 13 - 25 nov 2013

Tema - rezolvări

Rezolvări aici [1]

Problemă în clasă

Am rezolvat împreună problema bile1 dată la ONI 2012 clasa a 7^a. Avem mai multe variante de rezolvare:

• Forță brută: putem dimensiona o matrice m × n în care să simulăm căderea bilelor. Putem marca obstacolele cu -1, iar bilele cu un număr pozitiv sau zero. Această soluție este O(m × n) atît ca timp cît și ca memorie. Din păcate ea nu se încadrează în memoria de 8MB, deoarece vom avea nevoie de 2000 × 2000 de elemente întregi, adica 16 milioane de octeți.
• Soluția cu ordonare: putem memora obstacolele ca perechi de coordonate. Apoi vom sorta aceste perechi după coordonata linie. În cadrul unei linii ordinea perechilor nu contează, deoarece obstacolele nu pot fi lipite unul de altul, deci nu se pot influența. După ordonare vom parcurge obstacolele în ordine și vom ajusta corespunzător vectorul de bile. Complexitatea acestei soluții este dată de ordonarea obstacolelor. Cu select sort vom avea aproximativ 10000 × 5000 de operatii, adica 50 de milioane. Puțin riscant pentru 0.1s. Cu toate acestea soluția se va încadra în timp, deoarece acela este numărul maxim de operații, care în practică nu se atinge. Aceasta este și soluția comisiei.
• Există, însă, și o soluție mai simplă. E drept că nu putem stoca tabla cu bile. Dar putem stoca harta 2D a obstacolelor. De ce? Deoarece în acest caz elementele sînt zero sau unu, ceea ce înseamnă că putem folosi tipul char. Avem nevoie de 4MB, mult sub cei 8MB acordați. Astfel, vom citi obstacolele și le vom plasa pe această tablă. Apoi parcurgem această tablă pe linii. La întîlnirea unui obstacol vom actualiza vectorul de bile. Această soluție este mai simplu de implementat.

Rezolvare aici [2] și aici [3] (cu liste)

Temă

• Terminați de rezolvat problema bile1, rezolvare aici [4]
• Tema 13:
  • Problema puzzle: interval
  • Alarma

Rezolvări aici [5]