Încercați-vă puterile

PROBLEME propuse pentru rezolvare

Între 26 iulie - 9 august, la Constanța s-a desfășurat a doua tabără de antrenament a lotului olimpic național de informatică. La sfârșitul primei săptămâni membrii lotului lărgit au primit șase probleme de concurs, la sfârșitul celei de a doua săptămâni au fost șapte probleme. Adresându-ne tuturor celor care iubesc algoritmica, vă propunem să vă încercați puterile! Rezolvările voastre se vor evalua și vă vom anunța punctajul obținut.

P069801: Măsurătoare

problemă propusă de prof. Eugen Ionescu, Liceul de Informatică, Cluj-Napoca

Fie două canistre având volumul A, respectiv B litri. Inițial amândouă canistrele sunt goale. Trebuie să punem n litri de apă în cea de a doua canistră efectuând următoarele operații permise:

UA se umple prima canistră de la robinet;

UB se umple a doua canistră de la robinet;

GA se golește prima canistră;

GB se golește cea de a doua canistră;

AB se toarnă apa din prima canistră în a doua, astfel încât dacă se poate turna toată cantitatea de apă, se toarnă tot, altfel atât cât încape, restul rămânând în A;

BA se toarnă apa din a doua canistră în prima, astfel încât dacă se poate turna toată cantitatea de apă, se toarnă tot, altfel atât cât încape, restul rămânând în A;

Să se determine (cunoscând volumele canistrelor și cantitatea de apă dorită n în cea de a doua canistră) secvența de operații care efectuate una după alta conduc la cantitatea cerută de apă în cea de a doua canistră. Se cere secvența de operații de lungime minimă.

Date de intrare:

În prima linie a fișierului de intrare CANA.IN este scris numărul n (cantitatea de apă dorită în canistra a doua) (1ŁNŁ1000000), iar în cea de a doua linie sunt scrise volumele canistrelor: două numere întregi A și B, despărțite printr-un spațiu (1ŁA,BŁ1000000).

Date de ieșire:

În fișierul de ieșire CANA.OUT se va scrie secvența de operații, o singură operație pe o linie. Dacă problema nu are soluție, atunci pe singura linie a fișierului se va scrie cuvântul 'NU'. Dacă soluția este corectă, dar secvența nu are lungime minimă, se acordă 20% din punctaj.

Exemplu:

CANA.IN CANA.OUT

2 UA

3 7 AB

UA

AB

UA

AB

GB

AB

Timp maxim de executare/test: 1 secundă

P069802: Nuclee

problemă propusă prof. Ioan Maxim,

Liceul de Informatică, Cluj-Napoca

Fie S un șir de n numere naturale (1ŁnŁ1000000). Un nucleu de ordin k (1ŁkŁ32000) centrat în mÎS se definește ca fiind un subșir K al șirului S format din k elemente (nu neapărat consecutive) cele mai apropiate de m ( | x-m | este minim "xÎK).

Să se determine un nucleu al șirului S de ordin k centrat într-un element m din S.

Date de intrare

Fișierul de intrare NUC.IN conține pe prima linie numerele naturale k, reprezentând numărul de elemente ale subșirului K și valoare elementului m din șir, iar pe următoarele linii sunt scrise elementele șirului S (câte cel mult 50 de numere naturale pe o linie; valorile elementelor șirului sunt din intervalul [1,65000]).

Date de ieșire

În fișierul de ieșire NUC.OUT se vor scrie pe una sau mai multe linii elementele nucleului K.

Exemplu:

NUC.IN:

13 7

2 1 6 7 6 8 9 6 3 6 4 5 7 6 7 8 1 2 4 7 9 6 8 6

NUC.OUT:

6 7 6 8 6 7 6 7 8 7 6 8 6

Timp maxim de executare/test: 16 secunde

P069803: Electrotehnică

problemă propusă student Ovidiu Gheorghioiu, Universitatea Politehnică, București

Unii dintre voi au probabil intenția să meargă la facultate și au ales deja o Universitate Politehnică. Una dintre principalele materii din primul an va fi electrotehnica. Printre multele lucruri interesante pe care le veți învăța în cadrul acestei discipline va fi rezolvarea circuitelor. Nu ar strica să aveți un program care să vă ajute la această muncă, nu tocmai ușoară, nu? Să detaliem puțin.

Un circuit este alcătuit din noduri (numerotate de la 1 la N) și laturi (numerotate de la 1 la L). Fiecare latură leagă două noduri (posibil egale!) într-un anumit sens (sensul este doar convențional și ajută la stabilirea semnelor). Pot exista mai multe laturi care leagă aceleași noduri. Pe laturi se află elemente de circuit de diverse tipuri. Vom considera doar două tipuri de elemente: rezistoare și surse de t.e.m. (tensiune electromotoare). În funcție de configurația circuitului, pe fiecare latură se stabilește un curent. Rezolvarea circuitului constă în stabilirea intensităților acestor curenți.

Dacă notăm cu Ri valoarea rezistorului de pe latura i (rezistoarele nu au un sens, deci Ri ł 0), cu Ei valoarea t.e.m. (cu semn) și cu Ii valoarea intensității curentului (de asemenea cu semn), cele 3L valori verifică Legile lui Kirchhoff:

Legea I: În fiecare nod, suma algebrică a intensităților adiacente este 0 (intensitățile se iau cu - (minus) dacă latura respectivă "intră" în nod, respectiv cu + (plus) dacă latura "iese" din nod).

Legea II: Pe fiecare buclă (ciclu) din circuit, suma algebrică a căderilor de tensiune pe rezistoare (cădere de tensiune = produsul RiIi) este egală cu suma algebrică a t.e.m.

Atenție: o buclă poate conține și laturi luate în sens invers, caz în care intensitatea și tensiunea respectivă se iau cu semn schimbat (nu și valorile rezistoarelor!).

Firește, este greu să aplicăm legile în forma de mai sus (mai ales legea II care poate conduce la L! ecuații). Este ușor de demonstrat că una (oricare!) dintre ecuațiile legii I poate fi eliminată (cele N ecuații nu sunt liniar independente). De asemenea, în legea II este suficient să considerăm L-N+1 bucle independente (adică orice buclă să aibă o latură care nu apare în nici o altă buclă). Avem deci în total L ecuații cu L necunoscute.

În electrotehnică însă apar și sursele de t.e.m. comandate. Acestea au valoarea variabilă, dependentă de alte valori din circuit. Vom considera doar surse care depind liniar de valorile unor intensități (sub forma Ei = kIj, i, j fiind laturi, iar k o valoare dată oarecare). Problema nu se complică însă prea mult, deoarece avem, pentru fiecare "extra" necunoscută, și o "extra" ecuație.

Dându-se valorile (respectiv relațiile) rezistoarelor și t.e.m de pe fiecare latură, să se calculeze valorile intensităților de pe toate laturile.

Date de intrare:

Pe prima linie a fișierul ELTH.IN se dau N și L (1ŁNŁLŁ100). Pe fiecare dintre următoarele L linii se găsește descrierea laturii respective: vârfurile pe care le leagă, urmate de valoarea rezistorului și de două numere: dacă sursa este simplă, primul număr reprezintă valoarea ei, iar al doilea este 0. Dacă sursa este comandată, cele două numere corespund lui k și j din relația Ei = kIj (i este numărul de ordine al laturii curente).

Date de ieșire:

Fișierul ELTH.OUT va conține L linii. Pe fiecare linie i se va afla valoarea intensității curentului de pe latura i.

Observații:

Toate circuitele date sunt conexe și rezolvabile (există soluție unică);

Toate valorile (intrările și ieșirile, exceptând bineînțeles valorile rezistoarelor) sunt numere reale în intervalul [-1000, 1000];

La ieșire se cer două zecimale exacte.

Exemplu:

ELTH.IN

2 3

1 2 1 5 0

1 2 1 2 3

2 1 1 0 0

Sistemul:

I1+I2-I3 = 0

R1I1-R2I2 = E1-E2

R2I2+R3I3 = E2

E2 = 2I3

ELTH.OUT

0.00

5.00

5.00

-5.00

Timp maxim de executare/test: 2 secunde

P069804: Perechi stabile

problemă propusă prof. Emil Onea, Liceul "Unirea", Focșani

La o petrecere sunt invitați N bărbați și N femei. Atât bărbații cât și femeile sunt numerotați de la 1 la N. Organizatorii doresc ca toți cei 2*N invitați să se simtă cât se poate de bine (să danseze cu o persoană preferată) și solicită din partea fiecărui invitat lista preferințelor sale. Această listă cuprinde numerele de ordine ale tuturor persoanelor de sex opus, ordonată descrescător în funcție de preferințe.

Numim cuplare lista formată din cele N perechi (bărbat, femeie) desemnate pentru dans. Spunem că o pereche arbitrară (b, f) dintr-o cuplare oarecare este stabilă dacă respectă condiția: orice femeie f'aflată înaintea lui f în lista preferințelor lui b și cuplată cu b' în cuplare, îl preferă pe b' lui b. Întreaga cuplare este stabilă dacă toate cele N perechi sunt stabile.

Exemplu:

Fie N=3 și următoarele liste ale preferințelor:

Barbat Lista

preferintelor

1 3 1 2

2 2 3 1

3 2 3 1

Femeie Lista

preferintelor

1 2 3 1

2 1 3 2

3 1 2 3

Fie în continuare următoarele două cuplări:

(1)

Barbat Femeie

1 2

2 1

3 3

(2)

Barbat Femeie

1 3

2 1

3 2

Cuplarea (1) nu este stabilă, deoarece perechea (1 2) nu este stabilă. Într-adevăr, bărbatul 1 preferă femeia 3 în fața partenerei sale (2), iar femeia 3 îl preferă pe bărbatul 1 înaintea partenerului ei (3). În schimb, cuplarea (2) este stabilă.

Cunoscând numărul N și listele de preferințe întocmite de cele 2*N persoane, să se determine (dacă este posibil) o cuplare stabilă.

Date de intrare:

Pe prima linie a fișierului PAIRS.IN este scris numărul natural N, N<=250.

Pe următoarele N linii se află listele de preferințe ale bărbaților sub forma unor permutări ale mulțimii {1,2,...,N}; numerele de pe linia i+1 reprezintă lista preferințelor bărbatului i în ordinea descrescătoare a preferințelor acestuia. Următoarea linie din fișier este vidă. Pe următoarele N linii sunt scrise preferințele femeilor în același format. Numerele scrise pe o linie sunt despărțite printr-un singur spațiu.

Date de ieșire:

Rezultatele se vor scrie în fișierul PAIRS.OUT pe N linii. O linie va conține o pereche de numere naturale din mulțimea {1,2,?,N} reprezentând un element din cuplarea stabilă determinată. Primul număr al fiecărei perechi este numărul de ordine al bărbatului iar cel de al doilea este al partenerei sale de dans. Dacă nu există soluție, în fișier se va scrie mesajul ?Imposibil'. În cazul în care există mai multe soluții, în fișier se va scrie una singură

Timp maxim de executare /test: 1 secundă

P069805: Wilhelm Tell

problemă propusă de studentul Cătălin Frâncu, Universitatea Politehnică, București

Se dă un măr de forma unui poligon convex cu N Ł 3000 laturi în planul xOy. În acest măr, Wilhelm Tell trage M Ł 5000 săgeți. Săgețile descriu o traiectorie reprezentabilă printr-o dreaptă în planul xOy. Din păcate pentru el și pentru voi, Wilhelm Tell a îmbătrânit și nu mai vede chiar așa de bine, astfel că nu toate săgețile lovesc mărul. Să se spună câte săgeți își ating ținta și care este suma abaterilor pentru cele care nu își ating ținta.

Se consideră că o săgeată își atinge ținta dacă traiectoria ei are cel puțin un punct comun cu mărul. Abaterea unei săgeți de la țintă este egală cu distanța de la dreapta ei suport (D) la poligon (P): d(D,P)=min (d(A,B) symbol 124 \f "Symbol" \s 12

Asymbol 206 \f "Symbol" \s 12

symbol 68 \f "Symbol" \s 12

, Bsymbol 206 \f "Symbol" \s 12

P symbol 125 \f "Symbol" \s 12

Date de intrare

Fișierul de intrare TELL.IN conține următoarele date:

N

X1 Y1

...

XN YN

M

A1 B1 C1

...

AM BM CM

unde:

Xi și Yi sunt coordonatele reale ale vârfurilor poligonului care întruchipează mărul.

Atenție ! Punctele sunt date în ordine trigonometrică (în caz că vă servește la ceva). Poligonul este strict convex, în sensul că toate unghiurile sunt cuprinse în intervalul deschis (0,p).

Ai, Bi și Ci sunt numere reale reprezentând parametrii dreptelor suport ale săgeților. Astfel, traiectoria săgeții cu numărul i este dreapta de ecuație

Date de ieșire

Fișierul de ieșire TELL.OUT va conține două numere. Primul din ele reprezintă numărul de săgeți care și-au atins ținta, iar al doilea reprezintă suma abaterilor (cu două zecimale exacte) pentru săgețile care nu și-au atins ținta. Pentru fiecare din cele două numere se acordă 50% din punctaj.

Exemplu:

TELL.IN: TELL.OUT

5 3

2.0 4.0 3.41

-2 4

-4 2

-1 -2

3 0

5

0 1 0

1 -1 6

2 1 -8

1 0 -5

1 -1 -5

În acest exemplu, prima dreaptă "înțeapă" poligonul, a doua se află în prelungirea unei laturi a poligonului, a treia îl atinge într-un singur punct, iar a patra și a cincea trec la distanțe de 2 și respectiv Ö2.

Timp maxim de executare/ test: 2 secunde.

P069806: Călătorie cu bucluc

problemă propusă de prof. Roxana Tâmplaru, Liceul de Informatica, Craiova

Imaginați-vă că puteți călători în timp și puteți să vă transpuneți în ČpieleaČ altor personaje. Presupuneți așadar că sunteți căpitanul unei corăbii care din păcate eșuează pe o insuliță izolată în mijlocul oceanului. Nici nu apucați să faceți câțiva pași și sunteți imediat înconjurat de băștinași care nu par nicidecum bucuroși de oaspeți. Sunteți apoi condus la căpetenia lor și deduceți, după o obositoare ČdiscuțieČ, că nu aveți o altă șansă de a scăpa cu viață decât să rezolvați o mică problemă sau un fel de joc de logică. Vă gândiți că totuși șansa vă surâde, doar vă considerați o minte ageră și nu credeți că niște ČsălbaticiČ ar putea ČinventaČ ceva cu adevărat inteligendet, care să vă pună în încurcătură. Oricum nu aveți altă șansă, așa că cereți mai multe amănunte referitoare la jocul respectiv. În fața dumneavoastră este adus un bătrân băștinaș care începe să vă ČexpliceČ ce aveți de făcut ca să vă salvați viața.

În ce din urmă, deduceți următoarele: în căsuțele unui caroiaj dreptunghiular sunt plasate grămăjoare formate din boabe de cafea (un bob de cafea nu poate aparține simultan mai multor căsuțe), iar alături de caroiaj se găsește o grămadă mare de boabe de cafea. Două căsuțe se consideră vecine dacă au o latură comună (asta înseamnă că orice căsuță din caroiaj poate avea cel mult patru vecini). Există două tipuri de operații pe care le puteți efectua asupra grămăjoarelor de boabe de cafea din căsuțele caroiajului:

- să adăugați un același număr de boabe (luate din grămada mare) la două grămăjoare plasate în căsuțe vecine;

- să luați același număr de boabe din două căsuțe vecine (boabele astfel extrase se pun în grămada mare), putând astfel chiar goli (elibera) anumite căsuțe din caroiaj.

De fapt, chiar acesta este scopul ČjoculuiČ: folosindu-vă doar de cele două operații specificate mai sus, pornind de la o configurație impusă a caroiajului, să eliberați complet căsuțele de grămăjoarele de boabe de cafea plasate inițial în ele. Grămada de boabe plasată alăturat caroiajului este suficient de mare, astfel încât să permită în orice moment efectuarea unei operații de tipul 1).

Bătrânul vă ČconstruieșteČ apoi o configurație a caroiajului și vă dă de înțeles că soluția trebumăie furnizată până la apusul soarelui. Întrucât este foarte târziu, vă apucați imediat de treabă. Nimic mai potrivit în aceste momente decât laptop-ul dumneavoastră de care nu vă despărțiți niciodată. Practic, trebuie să decideți dacă există o succesiune astfel de operații care să vă permită eliberarea tuturor căsuțelor, și dacă da, să generați o astfel de succesiune.

Date de intrare:

Fișierul IN.TXT conține datele de intrare:

- pe prima linie, separate printr-un spațiu, se găsesc dimensiunile caroiajului (2Łm,nŁ150);

- pe următoarele m linii se găsește configurația caroiajului: fiecare astfel de linie conține n valori (numere naturale mai mici decât 1000), separate între ele printr-un singur spațiu, reprezentând, pentru fiecare linie a caroiajului, nullrul de boabe pentru fiecare căsuță în parte.

Date de ieșire

Rezultatul se va scrie în fișierul OUT.TXT, fiecare linie a sa fiind de forma: L1,C1 L2,C2->Nb unde:

- L1 și C1, respectiv L2 și C2 reprezintă liniile și coloanele aferente căsuțelor vecine asuăra cărora se efectuează operația specificată anterior prin numărul Nb. Valorile L1, respectiv C1 sunt despărțite prin caracterul vgulă, valorile C1 și L2 printr-un singur spațiu, valorile L2, respectiv C2 prin virgulă, iar valoarea Nb este precedată de cpparacterele ?->'. Căsuța din colțul stânga sus este identificată prin (1,1), căsuța din dreapta jos este identificată prin (m,n), notația fiind cea uzuală de la lucrul cu matrice.

- Nb reprezintă numărul de boabe care se adaugă sau se extrage la / din do căsuțe vecine; Nb este număr întreg, pozitiv dacă se face o operație de tipul 1), respectiv negativ, în cazul unei operații de tipul 2);

Exemplu:

IN.TXT OUT.TXT

3 3 1,1 2,1->-1

1 2 2 2,1 3,1->-2

4 3 2 2,1 2,2->-1

2 1 1 1,2 2,2->-2

3,2 3,3->-1

1,3 2,3->-2

Succesiunea operațiilor specificate în OUT.TXT are ca efect următoarele configurații intermediare (numerele ČboldateČ identifică celulele asupra cărora se efectuează operația indicată deasupra semnului ČȚČ) :

1 2 2 -1 0 2 2 -2

4 3 2 Ț 3 3 2 Ț

2 1 1 2 1 1

0 2 2 -1 0 2 2 -2

1 3 2 Ț 0 2 2 Ț

0 1 1 0 1 1

0 0 2 -1 0 0 2 -2 0 0 0

0 0 2 Ț 0 0 2 Ț 0 0 0

0 1 1 0 0 0 0 0 0

Observație:

În cazul unor configurații ce nu se pot elibera complet, în fișerul OUT.TXT se va scrie valoarea 0.

Timp maxim de executare/test: 1 secundă

Așteptăm soluții pe adresa redacției (numai prin e-mail), până la data de 1 noiembrie 1998.

[cuprins]