Soluţiile problemelor propuse

Clasa a IX-a: Scuturi

Problemă propusă de prof. Rodica Pintea, Liceul "Grigore Moisil", Bucureşti

Enunţ:

Pe o linie orizontală, la distanţe egale, se află n obiective punctiforme, numerotate de la 1 la n, înzestrate fiecare cu un scut.

Pe o linie paralelă cu aceasta se deplasează, într-o mişcare de "du-te vino" două dispozitive de tragere care încearcă să distrugă obiectivele considerate.

Primul dispozitiv porneşte din dreptul obiectivului 1, se deplasează succesiv în dreptul obiectivelor 2,3,...,n-1,n,n-1,... etc. Al doilea dispozitiv porneşte din dreptul obiectivului n şi se deplasează în dreptul obiectivelor n-1,n-2,...,2,1,2,3,... etc.

Ambele dispozitive parcurg distanţa din dreptul unui obiectiv până în dreptul obiectivului următor într-o secundă. Pentru fiecare dispozitiv se cunoaşte un număr p1, respectiv p2, reprezentând numărul de secunde dintre două trageri consecutive. Cele două dispozitive pot să tragă doar asupra obiectivului în dreptul căruia se află. În momentul pornirii, ambele dispozitive trag.

Pentru fiecare obiectiv i se cunoaşte un număr ri (i<=n) reprezentând rezistenţa scutului, acesta însemnând că obiectivul i este distrus după ri+1 trageri asupra sa.

Observaţii:

- dispozitivele se deplasează şi trag independent unul de celălalt (astfel încât ele pot trage asupra aceluiaşi obiectiv în acelaşi moment; în acest caz scutul este atacat de două ori);

- timpul unei trageri este neglijabil;

- un dispozitiv continuă să tragă şi asupra obiectivelor deja distruse.

Să se afişeze pe ecran:

a) numărul maxim de obiective care pot fi distruse, considerând mişcarea dispozitivelor şi resurselor de muniţie infinite;

b) timpul minim după care se reuşeşte distrugerea obiectivelor numărate la punctul a).

Date de intrare:

Datele de intrare se citesc din fişierul SCUT.IN având următorul format:

- pe prima linie este scris numărul întreg n, reprezentând numărul de obiective (2<=n<=30);

- pe linia a doua se află n numere naturale având cel mult 6 cifre, reprezentând rezistenţa scuturilor;

- pe a treia linie se găsesc două numere naturale reprezentând perioada de tragere a primului, respectiv a celui de-al doilea dispozitiv (0<p1,p2<=n).

Exemplu:

SCUT.IN Pe ecran se vor afişa numerele:

5 3

2 1 8 13 2 34

2 4

Observaţii:

- pentru exemplul de mai sus obiectivele distruse sunt cele cu numerele de ordine: 1, 3 şi 5;

Timp maxim de executare/test: 3 secunde.

Rezolvare:

Pentru această problemă există o rezolvare banală prin simularea mişcării şi decrementarea rezistenţei scuturilor până la distrugerea acestora. Din păcate o asemenea simulare este mare consumatoare de timp în executare.

În scopul de a obţine un timp de executare mai bun, se simulează câte o "perioadă" completă de tragere pentru fiecare dispozitiv (până când acesta trage din nou, aflându-se în poziţia iniţială). Obiectivele atinse în fiecare dintre "perioadele" ambelor dispozitive sunt cele ce vor fi, in final, distruse.

Se calculează o "perioadă" comună k (după care evoluţia sistemului se va relua) ca fiind cel mai mic multiplu comun al valorilor "perioadelor" celor două dispozitive. Se mai calculează numărul de atacuri c(i) executat asupra fiecărui scut i de ambele dispozitive într-o astfel de "perioadă comună".

Numărul de "perioade comune" necesare este dat de cel mai mare dintre rapoartele r(i)/a(i). Se consideră acest număr de perioade mai puţin una (calculându-se direct timpul necesar), ultima perioadă urmând a fi simulată, deoarece ea nu este (decât în cazurile particulare) o perioadă completă.

Listing SCUTURI.PAS

Clasa a IX-a: Fracţii

Problemă propusă de conf. dr. Henri Luchian, Universitatea "A. I. Cuza", Iaşi

Enunţ:

Se consideră primele N (1<=N<=26) litere mari din alfabetul englezesc care reprezintă nume de variabile. Aceste litere se scriu succesiv în ordine alfabetică, delimitate prin operatorul de împărţire ?:?, formând o expresie algebrică. Prin eventuala adăugare la această expresie a unor perechi de paranteze rotunde, se obţine o fracţie etajată. Fracţia poate fi scrisă, în urma eliminării etajelor, sub forma unei fracţii simple (care are la numărător, respectiv numitor, câte un produs de variabile). Cunoscând setul de litere care formează produsul de la numărător, se cere să se indice o modalitate de a aşeza parantezele.

Date de intrare:

Fişierul text FRACTIE.IN conţine două linii. Pe prima linie se află N (numărul de litere folosite), iar pe a doua se află un şir de litere mari, distincte, ordonate alfabetic, fără spaţii, reprezentând variabilele de la numărător. Datele de intrare sunt corecte.

Date de ieşire:

Fişierul text FRACTIE.OUT conţine pe o singură linie expresia cu paranteze fără nici un spaţiu.

Observaţii:

- Expresia trebuie să fie corect parantezată.

- Dacă nu există soluţie, fişierul de ieşire va fi format dintr-o singură linie conţinând mesajul: NU

- Dacă există mai multe soluţii, se va scrie una singură.

Exemplu:

FRACTIE.IN FRACTIE.OUT

5 A:(B:(C:D):E)

ACE

Timp maxim de executare/test: 5 secunde.

Rezolvare:

Este o problemă nestandard, inspirată de o problemă dată la o olimpiadă rusă de matematică. Pentru a găsi ideea de rezolvare, se poate căuta o regulă de ... ne-asociativitate, astfel ca, parcurgând o expresie cu paranteze, să se decidă de care parte a liniei de fracţie se va afla fiecare variabilă; se observă efectul unei paranteze închise/deschise asupra a două variabile succesive, apoi efectul parantezelor multiple. Fiecare variabilă poate ajunge fie la numărător, fie la numitor, în funcţie de modul în care se pun parantezele; singurele excepţii sunt x1, care nu poate apărea decât la numărător, şi x2, care nu poate apărea decât la numitor (este uşor de demonstrat - dar problema noastră nu cere acest lucru - că numărul de fracţii diferite ce se pot obţine este 2^(n-2), n fiind numărul de variabile.

Desigur, o fracţie din cele 2^(n-2) poate fi obţinută prin mai multe feluri de a pune parantezele ")". O idee de rezolvare poate fi scrierea unui şir de n biţi, bitul i fiind 1 dacă x_i trebuie să apară la numitor şi 0 dacă x_i trebuie să apară la numărător. Se parcurge şirul, deschizând şi închizând paranteze conform observaţiilor rezultate mai sus, iar apoi se adaugă perechile eventualelor paranteze incorect deschise/închise la prima trecere, şi anume pe nivelul pe care ele apar.

Implementarea pe care v-o prezentăm a fost realizată de Cătălin Frâncu, membru în subcomisia clasei a IX-a.

Listing FRACTII.PAS

Clasa a X-a: La monetărie

Problemă propusă de conf. dr. Radu Mârşanu, Academia de Studii Economice, Bucureşti

Enunţ:

Într-un depozit al monetăriei statului sosesc n saci cu monezi. Şeful depozitului cunoaşte numărul de monezi din fiecare sac şi ar vrea să modifice conţinutul sacilor, prin mutări de monezi dintr-un sac în altul, astfel încât în final, în fiecare sac să fie acelaşi număr de monezi. Ajutaţi şeful depozitului să obţină acelaşi număr de monezi în fiecare sac, prin efectuarea unui număr minim de mutări.

Date de intrare:

În fişierul Text MONEZI.IN se va scrie pe prima linie un număr întreg n (2<=n<=2000), reprezentând numărul de saci. Pe următoarele n linii sunt scrise numere întregi, reprezentând numerele de monezi din fiecare sac (numărul total de monezi din toţi sacii <=1.000.000.000).

Date de ieşire:

Rezultatele se vor scrie în fişierul text MONEZI.OUT sub următoarea formă:

• pe prima linie se scrie un număr întreg m, reprezentând numărul minim de mutări necesare;
• pe următoarele m linii se vor scrie triplete de numere întregi:

a b c

unde:

• a reprezintă numărul de ordine al sacului din care se mută monezi;
• b reprezintă numărul de ordine al sacului în care se mută monezi;
• c reprezintă numărul de monezi care se mută din sacul a în sacul b.

Observaţie:

În cazul în care problema nu are soluţie, se va scrie în fişier cuvântul: ?NU?.

Exemplu:

MONEZI.IN MONEZI.OUT

3 2

35 2 1 5

48 2 3 3

37

Timp maxim de executare/test: 8 secunde.

Rezolvare:

Subcomisia clasei a X-a a propus un algoritm greedy pe care îl prezentăm într-o variantă uşor îmbunătăţită.

Facem următoarele observaţii:

1) Dacă media aritmetică a numerelor de monede din saci nu este număr întreg, problema nu are soluţie.

2) În cazul în care există soluţie, se vor "pune deoparte" sacii care conţin exact atâtea monede cât este media aritmetică.

3) Cu o mutare se pot "rezolva" cel mult doi saci.

4) Cum nu este indiferentă ordinea în care se "rezolvă" câte un sac, prima dată se vor căuta perechi de saci pentru care există o mutare care "rezolvă" amândoi sacii. Aceştia, de asemenea se consideră "rezolvaţi" şi astfel numărul de saci din nou este posibil să se micşoreze.

În cele ce urmează, se ordonează sacii în ordine descrescătoare după numărul de monede. Se mută atâtea monede din primul sac în ultimul câte sunt necesare pentru a putea pune deoparte ultimul sac. Deoarece, în funcţie de numărul de monede rămase în primul sac, este posibil ca acesta să poată forma pereche cu un alt sac, se reia pasul descris la punctul 2) din observaţie pentru acesta şi restul sacilor. În cazul în care nu se găseşte un asemenea sac, acestuia trebuie să i se găsească noul loc în şirul ordonat după numărul de monede.

Listing MONEDE.PAS

Clasa a X-a: La monetărie... în ziua a doua

Problemă propusă de prof. Clara Ionescu, Liceul de Informatică, Cluj

Enunţ:

Şeful depozitului are trei saci cu monede, niciunul gol. Prietenul lui îi cere un sac gol, deci şeful depozitului va trebui să elibereze unul din saci. Dorind să nu se încurce în evidenţa monedelor din saci, va muta dintr-un sac în altul un număr de monede egal cu numărul de monede aflate în sacul în care face mutarea. Sacii sunt suficient de mari pentru orice astfel de mutare. Cum va proceda pentru a goli un sac efectuând un număr minim de mutări?

Date de intrare:

Fişierul de intrare SACI.IN are o singură linie de forma:

x y z

unde x,y,z reprezintă numărul de monede din fiecare sac (1<=x,y,z<10000 şi x+y+z<=10000);

Date de ieşire:

Fişierul de ieşire SACI.OUT va conţine pe prima linie numărul n reprezentând numărul de mutări, iar pe următoarele n linii se vor scrie două numere naturale:

a b

unde:

• a reprezintă numărul de ordine al sacului din care se face mutarea;
• b reprezintă numărul de ordine al sacului în care se face mutarea.

Observaţie:

Datele de intrare sunt corecte, nu necesită validare. Problema are soluţie întotdeauna.

Exemplu:

SACI.IN SACI.OUT

5 7 3 3

1 3

3 1

1 3

Timp maxim de executare/test: 3 secunde.

Rezolvare:

Rezolvarea problemei propusă de comisie - implementată de Valentin Gheorghiţă se bazează pe implementarea metodei Branch and Bound pentru fiecare stare posibilă a conţinutului sacilor. Se observă imediat că totdeauna există un sac din care se pot muta monede în doi saci, există unul din care se pot muta monede într-unul şi există unul din care nu se pot muta monede respectând restricţiile problemei. Se vor genera la fiecare pas toate mutările posibile şi se va păstra de fiecare dată adresa stării predecesoare pentru a putea reconstitui "drumul" care conduce la rezultatul căutat.

Listing SACI.PAS

Clasa a XI-a: Un Excel de jucărie

O foaie de calcul (spreadsheet) este un tablou dreptunghiular de celule rectangulare. Fiecare celulă poate conţine date sau expresii, care pot fi evaluate obţinându-se date. Liniile din foaia de calcul sunt numerotate, începând cu 0, iar coloanele se denumesc cu litere majuscule ale alfabetului englez (primele 26 de linii), apoi folosind combinaţii de litere (AA, AB etc). O celulă poate fi referită specificând coloana şi linia corespunzătoare (de exemplu, prima celulă este A0).

O foaie de calcul de jucărie conţine cel mult 26 de coloane (denumite de la A la Z) şi cel mult 10 linii (numerotate de la 0 la 9). Fiecare celulă poate conţine date de tip întreg sau expresii aritmetice în care se folosesc doar operatorii binari +,-,*,/, cu semnificaţia de adunare, scădere, înmulţire, respectiv împărţire întreagă. Operanzii pot fi valori întregi sau referinţe de celule.

Problema constă în a evalua, dacă este posibil, o foaie de calcul de jucărie dată. Prin evaluarea unei foi de calcul înţelegem înlocuirea tuturor expresiilor cu valorile lor.

Date de intrare:

Pe prima linie a fişierului de intrare EXCEL.IN sunt scrise două numere întregi n (reprezentând numărul de linii din foaia de calcul) şi m (reprezentând numărul de coloane), separate prin spaţiu.

Fişierul conţine în continuare n*m linii de date, câte una pentru fiecare celulă. Conţinutul celulelor (valoarea sau expresia) este specificat în ordinea crescătoare a liniilor, iar pe fiecare linie în ordinea alfabetică a coloanelor.

Date de ieşire:

Fişierul de ieşire EXCEL.OUT va conţine mesajul EVALUARE IMPOSIBILA sau foaia de calcul evaluată (n linii în ordinea dată, fiecare linie conţinând cele m valori ale celulelor componente, în ordinea dată a coloanelor, separate prin spaţiu).

Observaţii:

• Expresiile pot conţine paranteze rotunde.
• Expresiile nu conţin spaţii.
• Prioritatea operatorilor este cea uzuală.
• Datele şi valorile absolute ale expresiilor din foaia de calcul de jucărie sunt numere întregi mai mici decât 2.0E+9.
• Fiecare expresie conţine cel mult 100 de caractere.
• Expresiile date în foaia de calcul de jucărie sunt sintactic corecte (din punctul de vedere al sintaxei Pascal/C).

Exemplul 1:

EXCEL.IN EXCEL.OUT

1 2 EVALUARE IMPOSIBILA

1+B0

2+A0

Exemplul 2:

EXCEL.IN EXCEL.OUT

2 2 1 6

1 5 18

A1+A0

5

B0*3

Timp maxim de executare/test: 0.5 secunde

Rezolvare:

Vom reprezenta o foaie de calcul de jucărie sub forma unei matrice cu 10 linii şi 26 de coloane. Fiecare componentă a matricei este un articol având 3 câmpuri:

data expresia conţinută în celulă, citită din fişierul de intrare;

x câmp "flag", care poate avea doar valorile 0, 1 şi 2, cu semnificaţia:

• expresie neevaluată;
• expresie în curs de evaluare;
• expresie evaluată;

v valoarea calculată a expresiei, dacă x=2, sau nedefinit în rest.

Unei foi de calcul de jucărie îi putem asocia un digraf astfel:

• fiecare celulă constituie un vârf al digrafului;
• există arc de la un vârf v1 al digrafului la un alt vârf v2 dacă şi numai dacă în expresia din celula corespunzătoare lui v1 intervine o referinţă la celula corespunzătoare lui v2.

Evaluarea foii de calcul este posibilă dacă şi numai dacă digraful asociat nu conţine circuite.

Pentru rezolvarea problemei, vom parcurge foaia de calcul în ordinea crescătoare a liniilor, iar pe fiecare linie în ordinea crescătoare a coloanelor. Pentru fiecare celulă neevaluată (câmpul x corespunzător setat pe valoarea 0), vom seta câmpul x pe valoarea 1 (celulă în curs de evaluare) şi vom apela o funcţie de evaluare a expresiei din celulă. La revenirea din funcţia de evaluare setăm câmpul x pe valoarea 2. Dacă pe parcursul evaluării unei expresii apare o referinţă la o celulă a cărei expresie este de asemeni în curs de evaluare, afişăm mesajul EVALUARE IMPOSIBILA şi întrerupem executarea programului (deci nu este necesară detectarea prealabilă a eventualelor circuite în digraf, aceasta realizându-se pe parcursul evaluării).

Evaluarea unei expresii presupune analizarea sa sintactică, în scopul identificării unităţilor sintactice elementare ce intervin în definirea noţiunii de expresie aritmetică (termen, respectiv factor) şi evaluarea fiecărei unităţi sintactice. Evaluarea unei expresii implică evaluarea expresiilor corespunzătoare tuturor celulelor referite în cadrul expresiei (practic, o parcurgere în postordine a arborescenţei cu rădăcina în celula ce conţine expresia de evaluat).

Listing EXCEL.PAS

Problemă propusă de conf. dr. Henri Luchian, Universitatea "Al. I. Cuza", Iaşi

Enunţ:

Un număr de c critici literari şi-au spus, fiecare, părerea în chestiunea: "Care din cele r romane cu succes de public sunt de fapt, capodopere?" Opţiunile lor au stârnit discuţii aprinse în masele largi de cititori. Momentul este speculat de cele p=c div 2 posturi de televiziune care decid să organizeze, simultan şi separat talk-show-uri având ca invitaţi câte doi critici. Televiziunile plătesc criticilor exclusivitatea - deci nici un critic nu poate apărea la două posturi diferite - dar cu sume atât de mari, încât nici una nu-şi permite să "deţină", dacă poate, decât exact doi critici.

Cum însă sponsorii şi clienţii la spaţiile publicitare ale televiziunilor cer insistent ca înainte şi după reclamele lor, în emisiuni să nu mai existe certuri sau momente tensionate, fiecare post de televiziune este obligat să invite critici cu păreri apropiate, dar nu identice, asupra romanelor -capodopere. Condiţia este ca pentru oricare doi critici invitaţi la acelaşi post opţiunile să difere pentru exact un roman.

Dându-se c şi r, 1<=c<=100, 1<=r<=20, precum şi listele de romane considerate capodopere de fiecare critic, ajutaţi, dând una din soluţiile posibile, cât mai multe posturi de televiziune să realizeze talk-show-uri.

Date de intrare:

Pe prima linie a fişierului CRITICI.IN este scris numărul de critici c şi numărul de romane r separate printr-un spaţiu. Pe a i+1-a linie (i=1,...,c) este scrisă lista capodoperelor propuse de criticul i, sub forma unui şir de cel mult r numere naturale, diferite între ele, cuprinse între 1 şi r şi separate prin spaţiu.

Datele de intrare sunt corecte.

Date de ieşire:

Pe prima linie a fişierului CRITICI.OUT se va scrie un număr t, reprezentând numărul de posturi de televiziune care pot realiza talk-show-uri. Pe următoarele t linii se vor scrie numerele de ordine ale celor doi critici invitaţi de câte un post de televiziune dintre cele ce pot organiza talk-show-uri.

Exemplul 1:

CRITICI.IN CRITICI.OUT

4 4 1

1 3 2 1 3

4 2 1

1 2

3 4 1

Exemplul 2:

CRITICI.IN CRITICI.OUT

4 4 2

1 1 4

3 1 4 2 3

4 1

2 1

Timp maxim de executare/test: 2 secunde.

Rezolvare:

Fie luând direct listele criticilor, fie lucrând cu şiruri de câte r biţi (în al i-lea şir, poziţia j este 1 dacă criticul i crede că romanul j este capodoperă, altfel poziţia j este 0), se creează graful ataşat problemei; graful are c noduri şi muchie de la nodul k la nodul q dacă criticii k şi q diferă prin opinia asupra unui singur roman.

- În cazul modelării cu şiruri de biţi, proprietatea se exprimă prin "cel de-al k-lea şir de biţi diferă pe o singură poziţie de cel de-al q-lea şir de biţi".

- În cazul modelării pe liste, proprietatea cerută se exprimă astfel: "fie lista k include lista q (în termenii teoriei mulţimilor) şi mai are exact un element în plus, fie lista q include lista k şi mai are exact un element în plus".

Problema necesită construirea unui graf în care orice circuit este de lungime pară (de fapt, la un graf bipartit). Cuplajul maximal se poate afla elegant - cu flux, cu drumuri alternate -, euristic - greedy, - sau cu backtracking. Soluţia greedy este destul de tare: cazurile în care această metodă nu conduce la rezultat optim se descoperă relativ dificil; astfel de cazuri se pot obţine în cazul în care numărul de noduri (c) este relativ mare.

Implementarea realizată de Dan Podeanu din Bucureşti a fost pusă la punct în timpul concursului:

Listing CRITICI.PAS

Clasa a XI-a: Drumul cât mai lung

Problemă propusă de prof. Emil Onea, Liceul "Unirea", Focşani

Enunţ:

Doi îndrăgostiţi se află într-un oraş k şi au la dispoziţie p ore (p<=150), timp în care să se plimbe cu maşina şi apoi să ajungă fiecare la el acasă, fata în oraşul i, iar băiatul în oraşul j.

Ei doresc să se plimbe cât mai mult timp împreună, dar să ajungă în cel mult p ore, fiecare în oraşul său. Maşina se deplasează cu viteză constantă (cea legal admisă).

Cei doi au la dispoziţie o hartă cu n oraşe (3<=n<=200) printre care se află, evident, oraşul de plecare k şi oraşele destinaţie i şi j. Harta indică oraşele legate prin şosele şi durata exprimată în ore a parcurgerii cu viteză constantă (legal admisă) a distanţei dintre două oraşe. Să se determine traseul comun pe care îl vor parcurge cei doi îndrăgostiţi astfel încât timpul petrecut împreună să fie maxim şi să ajungă amândoi la propria destinaţie în cel mult p ore de la plecare.

Observaţii:

• cronometrarea duratei plimbării se face începând cu momentul 0 din oraşul de plecare k.
• în orice oraş unul dintre ei pot continua drumul separat, cu o altă maşină; (despărţirea nu necesită timp suplimentar);
• pe fiecare şosea se circulă în ambele sensuri;
• după plecarea din oraşul k nu se staţionează nici un moment;
• nu sunt permise întoarceri pe şosea sau parcurgeri incomplete ale unei şosele.

Date de intrare:

• Pe prima linie a fişierului de intrare MASINA.IN se află două numere naturale n şi m despărţite printr-un spaţiu, reprezentând numărul de oraşe de pe hartă şi numărul de şosele ce leagă aceste oraşe.
• Pe cea de a doua linie se află două numere naturale k şi p, despărţite printr-un spaţiu, reprezentând numărul de ordine al oraşului de plecare şi numărul de ore pe care îl au la dispoziţie cei doi îndrăgostiţi.
• Pe cea de a treia linie sunt scrise două numere naturale i şi j despărţite printr-un spaţiu, reprezentând numerele de ordine ale oraşelor de destinaţie pentru cei doi.
• Pe următoarele m linii sunt scrise triplete de numere naturale a b d, despărţite prin câte un spaţiu, reprezentând faptul că între oraşele a şi b există şosea directă, respectiv durata d în ore a parcurgerii acesteia.

Date de ieşire:

Rezultatele se vor scrie în fişierul MASINA.OUT structurate pe două linii:

• pe prima linie este scris numărul natural dmax, reprezentând durata maximă (în ore) în care cei doi se vor plimba împreună;
• pe linia a doua sunt scrise numerele naturale: k x1,x2,..., reprezentând oraşele pe care le vor vizita împreună, în ordine, începând cu oraşul k de plecare (datele vor fi despărţite prin câte un spaţiu).

În cazul în care soluţia optimă nu este unică se va afişa una singură.

Exemplu:

MASINA.IN MASINA.OUT

8 9 6

7 8 7 6 5 4 3

1 2

1 3 1

3 4 1

4 2 1

4 5 1

4 6 2

5 6 3

6 8 1

7 8 1

7 6 1

Timp maxim de executare/test: 4 secunde.

Listing DRUM.PAS

Clasa a XII-a: Bomboane

Problemă propusă de prof. Dana Lica, Liceul "I. L. Caragiale", Ploieşti

Enunţ:

La o fabrică de bomboane, sunt puse pe un stand n (n<=100) cutii de bomboane. Fiecare din cele n cutii conţin câte m (m<=1000) bomboane dintr-un singur sortiment. Toate cele n sortimente sunt distincte. Un angajat mai distrat începe să se amuze şi amestecă bomboanele din cutii. Spre a nu fi observată modificarea, el are grijă ca în fiecare cutie să rămână câte m bomboane.

Necazul apare când şeful său îi cere să-i aducă câte o bomboană din fiecare cutie, deci din fiecare sortiment. Fiind urmărit de către acesta, muncitorul nu va avea voie să extragă decât o bomboană din fiecare cutie.

Muncitorul acordă fiecărei extrageri un grad de risc. Astfel, la extragerea unei bomboane din sortimentul cu numărul i din cutia care conţinea iniţial sortimentul cu numărul j, gradul de risc va fi valoarea absolută a diferenţei dintre i şi j. Gradul de risc al tuturor celor n extrageri va fi egal cu suma riscurilor fiecăreia.

Să se determine ce sortiment de bomboană va trebui să extragă muncitorul din fiecare cutie pentru ca gradul de risc total să fie minim.

Date de intrare:

Pe prima linie a fişierului BOMBON.IN sunt scrise numerele n şi m despărţite printr-un spaţiu. Pe următoarele n linii se găsesc câte m numere despărţite printr-un spaţiu. Cele m numere reprezintă sortimentele bomboanelor ce se regăsesc în fiecare cutie după amestecare, în ordine, începând cu cutia având numărul de ordine 1 până la cutia având numărul de ordine n.

Date de ieşire:

Fişierul de ieşire BOMBON.OUT conţine două linii:

- pe prima linie se va scrie un număr natural reprezentând gradul total minim de risc;

- pe a doua linie sunt scrise n numere despărţite printr-un spaţiu reprezentând numărul de ordine al cutiei din care va fi scoasă bomboana din fiecare sortiment, în ordine, începând cu sortimentul 1 până la sortimentul n.

În cazul în care există mai multe posibilităţi de extragere cu risc total minim, se va afişa una singură.

Exemplu:

BOMBON.IN BOMBON.OUT

7 3 10

1 2 7 1 5 3 4 7 2 6

6 6 4

4 7 3

4 2 3

2 1 3

7 5 1

5 5 6

Timp maxim de executare/test: 6 secunde.

Rezolvare:

Abordarea rezolvării problemei printr-un algoritm poliminial ne conduce la modelarea ei cu ajutorul reţelelor de flux.

Se consideră un nod sursă şi un nod destinaţie (artificial). Reţeaua va avea în afară de aceste două noduri încă 2n noduri, deci dublul numărului de sortimente distincte de bomboane. Vom uni pe rând fiecare dintre primele n noduri (reprezentând sortimentele distincte de bomboane, numerotate de la 1 la n), considerând că aceste arce au capacitatea 1 şi costul 0. Vom uni apoi celelelalte n noduri (reprezentând cele n cutii, numerotându-le de la n+1 la 2n) cu nodul destinaţie, prin arce de capacitate 1 şi cost 0. Apoi vom pune arce între nodul i (1<=i<=n) şi nodul j (n+1<=j<=2n) dacă bomboana din sortimentul i se regăseşte în cutia j-n după amestecare. Acest arc va avea capacitatea 1 şi costul egal cu valoarea absolută dintre j-n-i (datorită numerotării cutiilor începând cu n+1). Reţeaua fiind modelată, problema revine la calculul fluxului de valoare maximă şi de cost minim.

Algoritmul constă în mărirea continuă a fluxului cu valoarea dată de drumul de cost minim între nodul sursă şi nodul destinaţie, (drum format doar din arce nesaturate).

Determinarea drumului minim se va face cu algoritmul lui Roy-Floyd întrucât el acceptă costuri negative pe arce.

Listing BOMBOANE.PAS

Programe Sursă:

Puteţi descărca listingurile prin Internet de la adresa http://www.ginfo.ro .

Paginile soluţii au fost realiza de Clara Ionescu, e-mail cionescu@ginfo.ro .