Clasa a VII-a lecția 20 - 6 feb 2020

From Algopedia
Jump to navigationJump to search

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

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.

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.

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ă)

Tema opțională - rezolvări

Rezolvări aici [1]

Lecţie - divide et impera, continuare

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-02-06-clasa-7-lectie-info-20-720p.mp4</html5media>

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]