Din GInfo 1: SOLUȚIILE problemelor propuseMihai Stroe Cum se poate obține "aur absolut", adică premiul I cu punctaj maxim la Olimpiada Internațională de Informatică? După performanța de vârf a lui Radu Lupșa din 1993 (Argentina), România se poate mândri din nou cu o asemenea medalie datorită lui Mihai Stroe din București. Mihai a reușit (în septembrie1998, în Portugalia) să demonstreze că forța lui intelectuală, puterea de analiză și sinteză sunt la același nivel cu talentul necesar pentru a urca în top-ul clasamentului. Îl felicităm! P019901: CamelotTrebuie observat faptul că în majoritatea cazurilor nu este avantajos ca regele să se deplaseze "pe jos", ci ar trebui să călătorească "călare". Pentru a pregăti "terenul" în scopul mutării cavalerilor, vom calcula, pentru fiecare cavaler i costul deplasării lui din poziția în care se află inițial în oricare din celelalte poziții ale tablei. Aceste valori se păstrează în șirul de matrice FC. Punctul de întâlnire nu este cunoscut, rezultă că vom presupune, pe rând, că oricare poziție (x,y) de pe tablă este un punct de întâlnire posibil. Pentru fiecare poziție posibilă de întâlnire ((x,y), x=1,2,...,8, y=1,2,...,8) vom calcula (în matricele FFIN) numărul minim de pași în care un cavaler oarecare ar putea să ajungă din pozițiile de pe tablă în poziția (x,y) respectivă. Considerând că atât cavalerii, cât și regele se deplasează pe cel mai scurt drum spre poziția (x,y), se calculează numărul total de mutări și se determină acea poziție (x,y) pentru care acest număr este minim. Revenim la observația referitoare la faptul că probabil este mai avantajos ca regele să se deplaseze împreună cu un cavaler. Presupunem, pe rând, pentru toate pozițiile (i,j) posibile că ar putea să fie loc de întâlnire între oricare cavaler și rege. Calculăm numărul total de mutări necesare, folosind valorile din matricele determinate anterior și îl comparăm cu optimul găsit în prima fază a algoritmului. Implementarea nu necesită alte "artificii" de optimizare deoarece numărul posibilităților este relativ mic. P019902: ContactSingura dificultate o constituie mărimea fișierului de intrare, care nu poate fi citit și stocat în memorie, dar nici prelucrarea caracter cu caracter nu este posibilă. Analizând problema, se observă că inițial ar trebui citite A caractere (lungimea minimă a unei secvențe posibilă de depistat ca semnal care se repetă). Ar urma prelucrarea acesteia respectiv contorizarea ei, apoi prelucrarea secvenței obținute prin adăugarea la secvența de lungime A a următorului caracter citit ș.a.m.d. până la prelucrarea secvenței de lungime B. Datorită faptului că prelucrarea secvențelor după fiecare adăugare a unui caracter nou, prelucrarea subsecvențelor de lungime A, A+1, ..., B din care face parte acest ultim caracter citit, am preferat o citire general valabilă și nu am tratat separat cazul citirii unei secvențe având lungime mai mică decât A. De asemenea, se observă că astfel, după prelucrarea secvenței de lungime B, citirea continuându-se, caracterul cel mai "bătrân" devine inutil și este eliminat. Frecvențele sunt păstrate într-o matrice x de dimensiuni 12Ž212=12Ž4096. De fapt se folosesc valorile de la x[i,0] până la x[i,2i-1] pentru i între A și B. Valoarea lui x[i,j] este egală cu frecvența unui șir de lungime i care este reprezentarea binară a numărului j. Matricea x are elemente de tip Longint deoarece numărul maxim posibil pentru frecvența de apariție a unei secvențe de caractere are limita superioară 2.000.000. P019903: Orgă de luminiSe observă că nu contează ordinea operațiilor și că apăsarea unui buton de N ori are același efect cu apăsarea lui de (N mod 2) ori. Astfel, din orice secvență se obține una simplificată prin cel mult patru apăsări de butoane diferite. Există 24=16 astfel de secvențe simplificate. Pentru a obține o secvență validă cu C apăsări este necesar să existe o secvență simplificată cu numărul de apăsări M de aceeași paritate cu C. Secvența de C apăsări se obține apăsând butonul 1 de încă M-C ori. Programul generează cele 16 secvențe și testează validitatea lor. O secvență validă are numărul de acționări mai mic sau egal cu C, de aceeași paritate cu C, iar rezultatul aplicării ei respectă resticțiile precizate prin datele de intrare. Programul este foarte simplu: se citesc datele de intrare, se generează cele 16 secvențe simplificate, iar procedura TRY verifică dacă secvența curentă este bună. În caz afirmativ, se scrie în fișier rezultatul aplicării ei. P019904: DreptunghiuriPentru siguranța că programul va rula în timp pe orice test, se impune complexitatea maximă n2 și o implementare fără prea multe operații. Numărul cerut este suma lungimilor unor segmente orizontale și verticale. Am elaborat un algoritm O(n2) pentru calcularea sumei lungimilor segmentelor paralele cu Ox, care se aplică din nou după o transformare a figurii pentru celelalte segmente (paralele cu Oy). Procedurile FINDX și FINDY găsesc valorile pentru x și y care corespund coordonatelor vârfurilor unor dreptunghiuri. Prin punctele x se duc paralele la Oy. Procedura SORTPOLY ordonează dreptunghiurile după valoarea coordonatei verticale a colțului stânga jos. Pentru fiecare două paralele consecutive la Oy se determină suma lungimilor segmentelor care aparțin intersecției conturului figurii cu zona din plan mărginită de cele două paralele. Algoritmul de determinare a acestei sume are ordinul de complexitate O(n). Se parcurg dreptunghiurile (în prealabil sortate) și pentru fiecare dreptunghi "activ" (care intersectează zona respectivă), se actualizează "intervalul curent". La început limitele intervalului vor fi determinate de marginea superioară și marginea inferioară a primului dreptunghi găsit. Dacă un dreptunghi activ este cuprins în "intervalul curent", acest interval va fi extins până la limitele noului dreptunghi. Dacă dreptunghiul activ nu este cuprins în "intervalul curent", vom deschide un nou interval. Ceea ce ne interesează este de fapt numărul intervalelor. Acesta, înmulțit cu dublul distanței dintre cele două paralele la Oy, reprezintă suma lungimilor segmentelor din zona respectivă. P019905: PoligonProblema este similară altor probleme în care se cere parantezarea unei expresii și se rezolvă prin metoda programării dinamice. Pentru fiecare eliminare a unei laturi, obținem o expresie aritmetică, în care întâlnim numere întregi și operatorii + și *. Această expresie trebuie parantezată astfel încât rezultatul obținut să fie maxim. În matricele MIN și MAX se calculează valorile minime, respectiv maxime pentru subexpresii ale expresiei inițiale; MIN[i,j], de exemplu, reprezintă minimul subexpresiei cu operanzii de la i la j din expresia inițială. Valorile care se cunosc inițial sunt MIN[i,i] și MAX[i,i], care sunt chiar operanzii respectivi. Rezultatul este dat de MAX[1,n]. Procedura INIT generează, pe rând, expresiile cărora li se va calcula maximul. Minimul și maximul pentru o expresie se obțin din subexpresiile ei. Să presupunem că am ales cele două subexpresii. Dacă între ele este semnul "+", MIN[i,j] și MAX[i,j] se obțin prin suma minimelor, respectiv maximelor subexpresiilor. Pentru înmulțire, apar mai multe cazuri; se justifică astfel păstrarea valorii pentru MIN (de exemplu, un maxim pozitiv se poate obține înmulțind două minime negative, dar mari în modul). P019906: Cer înstelatGrupările de stele se memorează ca liste de puncte în care fiecărei stele i se asociază coordonate relative astfel încât coordonatele minime vor fi x=1 și y=1. În cadrul listei, stelele sunt ordonate după linii, iar în cadrul aceleiași linii după coloane. Testarea egalității a două liste devine astfel liniară. O grupare se determină cu ajutorul procedurii FILL, introducând steaua curentă în listă, marcând-o pentru a nu fi vizitată a două oară și apelând procedura FILL pentru pozițiile vecine. Procedurile pentru translatare, ordonare, rotație și oglindire sunt rapide și relativ ușor de înțeles. Practic, fiecare grupare nouă este căutată în lista "claselor" de grupări. Apoi se caută și celelalte 7 reprezentări posibile (obținute prin rotații și/sau oglindiri). În cazul în care o grupare nu este regăsită, ea este memorată în listă; în caz contrar, gruparea se marchează cu litera care îi revine. S-a ales reprezentarea cu liste de stele (în locul celei cu matrice) pentru a obține un timp mai bun (de exemplu, cu 101 stele se poate obține o matrice 50*50, mult mai mare decât o listă, deci egalitatea a două grupări, rotația și oglindirea durează mai mult).
Mihai Stroe este student la Universitatea Politehnică din București; poate fi contactat prin e-mail la adresa: mstroe@pcnet.pcnet.ro [cuprins] |