Olimpiada Națională de Informatică, Oradea, 1998

Soluțiile problemelor propuse

Primăvara prevestește olimpiadele școlare... sau olimpiadele prevestesc primăvara? Anul acesta cei mai buni elevi informaticieni s-au întrecut într-o competiție extrem de dificilă, perfect organizată și desfășurată la Oradea. Vom publica problemele și rezolvările lor în câteva numere ale revistei noastre, și vă adresăm o chemare de a le studia și de a căuta să le rezolvați conform stilului propriu, pe baza unor idei originale pentru a vă verifica puterile și talentul.

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ă xi trebuie să apară la numitor și 0 dacă xi 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

Enunț:

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

Clasa a XI-a: Critici

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 .

[cuprins]