Din GInfo 6:
SOLUȚIILE problemelor propuseP069801: MăsurătoareProblemă propusă de prof. Eugen Ionescu, Liceul de Informatică, Cluj-Napoca Rezolvarea propusă se bazează pe următoarele observații: 1. În cazul în care cantitatea care trebuie obținută nu este multiplu al celui mai mare divizor comun al capacităților celor două canistre, nu există soluție. Rezultă că n trebuie să dividă cmmdc(a, b); 2. Vom obține o soluție în cazul în care turnăm apa doar din prima canistră în cea de a doua; 3. Vom obține o soluție în cazul în care turnăm apa numai din a doua canistră în prima. Soluția va fi aleasă dintre cele două soluții obținute pe baza observațiilor 2. și 3. Vom alege evident, soluția care implică cel mai mic număr de transferuri. P069802: NucleeProblemă propusă de prof. Ioan Maxim, Liceul de Informatică, Suceava Pentru început vom număra de câte ori apare fiecare număr cuprins între 1 și 65000 în șirul dat. Se observă că am avea nevoie de un tablou care să conțină 65000 de numere, fiecare număr necesitând o reprezentare pe 4 bytes. Cum limbajele Pascal și C nu permit declararea unei structuri de date de acest fel suntem nevoiți să alegem o altă reprezentare pentru această structură de date. Vom reprezenta șirul ca o matrice A de dimensiuni 256*256, fiecare linie a matricei fiind alocată dinamic. Celui de-al i-lea termen din șir îi va corespunde elementul [i div 256, i mod 256] din matrice. Vom alege acum cei k termeni ai subșirului cerut. Pentru aceasta vom număra câte elemente care trebuie să aibă o anumită valoare trebuie să conțină acest subșir. Vom începe cu valoarea m și apoi, cât timp nu avem destule elemente vom căuta la stânga și la dreapta lui m, respectiv valorile: m-1, m+1, m-2, m+2 etc. Trebuie să fim atenți ca numerele m-i sau m+i să fie în intervalul [1..65000]. Pentru a afișa cei k termeni ai subșirului trebuie să mai parcurgem o dată șirul dat și, de fiecare dată când întâlnim un număr pentru care nu avem în subșir suficiente elemente cu acea valoare, îl adăugăm în subșir. P069803: ElectrotehnicăProblemă propusă de Ovidiu Gheorghioiu, student, Universitatea Politehnică, București Din punct de vedere algoritmic problema este destul de simplă, singura dificultate fiind legată de determinarea unui sistem de bucle independente pentru ecuațiile Kirchhoff 2. Metoda cea mai simplă de obținere a acestor L-N+1 bucle independente se bazează pe construirea unui arbore parțial al grafului dat. Acest arbore conține N-1 laturi și deci în afara lui rămân L-N+1 laturi. Fiecărei laturi exterioare îi putem atașa o buclă formată din latura respectivă și drumul între vârfurile ei prin interiorul arborelui. Buclele astfel obținute sunt într-adevăr în număr de L-N+1 și sunt independente deoarece fiecare conține o latură care nu se regăsește în nici una din celelalte bucle (vezi problema cu polițiștii dată la ONI Timișoara ?97). Sistemul este rezolvat prin metoda Gauss, astfel: matricea a memorează ecuațiile sistemului, fiecare linie conținând pe poziția 0 termenul liber (considerat în partea stângă a ecuației) iar pe celelalte poziții coeficienții intensităților corespunzătoare (exemplu: 2*I1+3*I2+5=0 se memorează sub forma: [5,2,3,0,0,....]). Rezolvarea constă în efectuarea pentru fiecare linie a următoarelor operații: 1) găsirea unui element diferit de 0, exclusiv termenul liber; există totdeauna un astfel de element deoarece în caz contrar, s-ar ajunge la o ecuație de forma 0+tl=0. Dacă tl (termenul liber) este 0, înseamnă că am "pierdut" o ecuație, deci sistemul nu poate fi determinat. 2) reducerea coloanei pe care se găsește acest element în celelalte ecuații (linii ale matricei). Sistemul rezultat în urma acestor operații este foarte simplu, fiind format din ecuații de forma I[x]*a[i,x]+tl=0 cu soluțiile evidente I[x]=-tl/a[i,x] cu A[i,x]<>0. Pentru ușurință vom reține c[x]=i. Sistemul se construiește destul de simplu pentru primele N-1 ecuații (Kirchhoff I). Pentru ecuațiile Kirchhoff II se procedează ca mai sus. P069804: Perechi stabileProblemă propusă de prof. Emil Onea, Liceul "Unirea", Focșani Schițăm pașii algoritmului propus: © variabila b, inițializată cu valoarea 1, denumește bărbatul pentru care se va stabili perechea în momentul curent; © se parcurg descrescător preferințele bărbatului b; să presupunem că s-a ajuns la femeia f: š dacă aceasta este necuplată, se cuplează b cu f și b se incrementează cu 1 (trecem la următorul bărbat); š dacă aceasta este cuplată: - dacă ea preferă bărbatul b în locul actualului ei bărbat, se cuplează b cu f și b se setează pe valoarea fostului bărbat al femeii f; - altfel, se continuă baleierea preferințelor bărbatului b. Trebuie demonstrat că algoritmul este finit și că produce un rezultat corect. Să observăm că o femeie, odată cuplată, nu va mai fi niciodată liberă, eventual își schimbă perechea. Astfel, constatăm că la fiecare pas, fie o nouă femeie este cuplată, fie o femeie deja cuplată își schimbă partenerul cu unul aflat mai în față în lista preferințelor ei. Deci la fiecare pas, configurația generală se "îmbunătățește". Este evident că acest proces nu se poate continua la infinit, iar în situația cea mai avantajoasă se ajunge la o configurație în care fiecare femeie este cuplată cu primul bărbat în ordinea preferințelor ei. Rezultă deci că algoritmul este finit; mai mult, deducem limita superioară a complexității sale: deoarece o femeie își poate schimba bărbatul de cel mult N-1 ori, iar numărul femeilor este N, tragem concluzia că algoritmul efectuează cel mult N*(N-1) pași; complexitatea sa este deci O(N^2). Să demonstrăm acum că algoritmul produce un rezultat corect. Considerăm "tabela" cuplărilor, produsă după execuția algoritmului și perechea arbitrară (b,f). Să presupunem că ar exista o femeie f', pe care b o preferă față de f, și care la rândul ei îl preferă pe b în fața bărbatului ei; fie acesta b'. Vom demonstra că acest lucru este însă imposibil. Într-adevăr, atunci când am făcut alegerea femeii care devine perechea lui b, f' a fost tratată înaintea lui f, conform presupunerii făcute. Apar 2 cazuri: - dacă f' era necuplată în acel moment, atunci b s-ar fi cuplat cu f'; b fiind, după preferințele lui f', în fața lui b', acesta n-ar fi ajuns niciodată să se cupleze cu f' (am observat că o femeie își "îmbunătățește" alegerea sau o lasă constantă) - contradicție, deoarece în tabela finală b' este cuplat cu f'; - dacă f' era cuplată în acel moment, atunci era cuplată cu b' sau cu un alt bărbat, b", aflat, după preferințele ei, după b'; oricum, în "clasamentul" lui f', b era în fața bărbatului din acel moment al lui f', deci, conform algoritmului, f' s-ar fi despărțit de bărbatul ei, cuplându-se cu b. Din nou, b fiind, după f', în fața lui b', b' nu s-ar mai fi putut cupla cu f' - contradicție. Cum alegerea perechii (b, f) a fost făcută arbitrar, este clar că tabela finală nu poate cuprinde decât perechi stabile. Observație Soluția în general nu este unică. Exemplu: Fie 6 bărbați și 6 femei pentru care avem următoarele preferințe: Preferințele bărbaților : Preferințele femeilor : 1: 4 5 2 3 1 6 1: 4 2 3 6 5 1 2: 3 5 2 4 6 1 2: 3 2 4 5 6 1 3: 3 4 6 5 1 2 3: 1 5 4 6 2 3 4: 5 4 2 3 1 6 4: 1 3 2 4 6 5 5: 6 3 1 4 5 2 5: 5 3 4 6 1 2 6: 1 2 3 6 5 4 6: 4 5 1 6 2 3 O soluție ar fi: O altă soluție: (1, 4); (1, 4); (2, 3); (2, 2); (3, 5); (3, 5); (4, 2); (4, 3); (5, 6); (5, 6); (6, 1); (6, 1); P069805: Wilhelm TellProblemă propusă de Cătălin Frâncu, student Universitatea Politehnică, București Se observă că pot exista două situații: 1. dreapta atinge poligonul, caz în care abaterea este 0; 2. dreapta nu atinge poligonul, caz în care distanța de la poligon la dreaptă este practic minimul distanței de la unul din vârfurile poligonului la dreaptă. De aceea, o soluție banală ar fi un algoritm de complexitate O(M*N) care face testul pentru fiecare dreaptă în O(N): dacă există vârfuri ale poligonului situate de ambele părți ale dreptei (sau chiar pe dreaptă), distanța este 0, altfel se află minimul distanței de la vârfurile poligonului la dreaptă. Un algoritm de complexitate O(M*log N) face testul pentru fiecare dreaptă în O(log N) și se bazează pe următoarea observație: dacă divizăm poligonul în două lanțuri poligonale între vârfurile cu coordonata x minimă și maximă, atunci pentru fiecare lanț funcția "distanța de la vârf la dreaptă" este întâi descrescătoare, apoi crescătoare, ca în imaginea următoare: Deducem că vârful situat cel mai aproape se determină prin bisecția intervalului. Tot în timpul bisecției verificăm dacă nu se sare dincolo de dreaptă, caz în care dreapta este secantă. Programul caută extremele pe ambele lanțuri poligonale. În figură vârfurile descoperite sunt marcate cu săgeată. Dacă aceste puncte se află de o parte și de alta a dreptei, dreapta este secantă. Altfel, unul dintre ele trebuie să fie cel mai apropiat de dreaptă din tot poligonul. Merită remarcat că dacă un vârf este mai aproape de dreaptă decât ambii săi vecini, atunci el este punctul cel mai apropiat de dreaptă din întregul poligon. P069806: Călătorie cu buclucProblemă propusă de prof. Roxana Tâmplaru, Liceul de Informatică, Craiova Inițial trebuie să determinăm dacă problema admite soluție. Pentru acest lucru folosim următorul artificiu: caroiajul se colorează în alb/negru analog unei table de șah; notăm cu SA suma boabelor de pe pătratele colorate în alb și cu SN suma boabelor de pe pătratele colorate în negru. Este evident că în urma unei operații SA și SN se vor modifica cu aceeași valoare (numărul de boabe adăugate sau eliminate). Din propoziția anterioară și din faptul că în final caroiajul va fi gol, rezultă că existența soluției este garantată de egalitatea SA=SN. De asemenea dacă există soluție, în urma oricărei succesiuni de operații SA va fi egal cu SN. Deci vom calcula sumele SA și SN și dacă ele diferă, rezultă că nu există soluție (funcția Posibil) și se va scrie 0 în fișierul de ieșire. Dacă rezultă că există soluție trebuie găsită succesiunea de operații care să elimine toate boabele de cafea. Pentru a o determina vom parcurge căsuțele caroiajului în următoarea ordine: (1,1)(1,2)(1,3)...(1,n)(2,n)(2,n-1)...(2,1)(3,1)(3,2)... Observații: - fiecare căsuță este vizitată o singură dată; - oricare două căsuțe vizitate succesiv sunt vecine (adică deplasarea se face pe linie sau coloană); - ultima căsuță vizitată este (m,1) dacă n este par sau (m,n) în caz contrar (n impar). Se parcurg primele m*n-2 căsuțe (în ordinea amintită) și se elimină, din fiecare, toate boabele, astfel: - dacă numărul de boabe este 0, atunci se trece la următoarea căsuță; - dacă numărul de boabe din căsuța curentă este mai mic sau egal decât cel din căsuța următoare (în ordinea parcurgerii) atunci se va elimina din căsuța curentă și din următoarea un număr de boabe egal cu cel din căsuța curentă (astfel se va goli căsuța curentă); - dacă numărul de boabe din căsuța curentă este mai mare decât cel din căsuța următoare, numărul de boabe din căsuța următoare se va mări astfel încât să ajungă egal cu cel din căsuța curentă (se adaugă boabe la căsuța următoare și succesoarei acesteia). Se va elimina din căsuța curentă și din cea următoare un număr de boabe egal cu cel din căsuța curentă; astfel se vor goli cele două căsuțe. După aceste operații vor mai exista cel mult două căsuțe nevide (ultimele două). Cum cele două căsuțe sunt vecine, ele sunt colorate diferit. Din faptul că în orice moment SA=SN rezultă că în cele două căsuțe vor exista același număr de boabe, care se vor elimina. [cuprins] |