PROBLEME propuse pentru rezolvare

În perioada 14-30 aprilie s-a desfăşurat la Liceul de Informatică din Cluj tabăra de antrenament a lotului lărgit (informatică) având ca scop pregătirea şi selecţionarea echipelor participante la CEOI'98 şi Balcaniada de Informatică.

P049801: Funcţii surjective

problemă propusă de prof. Doina Rancea, Liceul "Tiberiu Popoviciu", Cluj-Napoca

Enunţ:

Să se determine numărul funcţiilor surjective f:A?B, unde A şi B sunt două mulţimi formate din litere mici ale alfabetului.

Date de intrare:

Pe prima linie a fişierului de intrare FUNCTII.IN sunt scrise literele aparţinând mulţimii A, iar pe a doua linie literele aparţinând mulţimii B.

Date de ieşire:

În fişierul de ieşire FUNCTII.OUT se va scrie numărul funcţiilor surjective f:A?B.

Exemplu:

FUNCTII.IN FUNCTII.OUT

ab 1

x

P049802: Fractal

problemă propusă de Cătălin Frâncu, student,Universitatea Politehnică, Bucureşti

Enunţ:

Se consideră în plan mulţimea A₀=[0,1)´[0,1). Remarcaţi că A₀ este un pătrat de latură 1 care îşi conţine latura din stânga şi pe cea de jos, dar nu şi le conţine pe cea din dreapta şi pe cea de sus. Mulţimea A₀ se împarte în 3´3 pătrate egale de latură 1/3. Pătratele formate au aceeaşi proprietate cu A₀, adică îşi conţin laturile din stânga şi de jos, dar nu şi pe cea din dreapta şi pe cea de sus. Numerotăm aceste pătrate în ordinea indicată de figura 1:

n Pătrate care nu fac parte din mulţimea A_z

o Pătrate care fac parte din mulţimea A_z

Aşadar P₁=[0,1/3)´[0,1/3), P₂=[1/3,2/3)´[0,1/3) etc. Din mulţimea A₀ se elimină un set prestabilit de pătrate (indicat printr-o submulţime a mulţimii {1,2,3,4,5,6, 7,8,9,10}), obţinând astfel o mulţime A₁. Pentru fiecare pătrat de latură 1/3 care a rămas în mulţimea A₁, se aplică acelaşi procedeu: se împarte pătratul în 3´3 pătrăţele cu latura de trei ori mai mică (1/9); aceste pătrăţele se numerotează în aceeaşi ordine, apoi acelaşi set prestabilit de pătrate se elimină. În felul acesta se obţine mulţimea A₂. Figura 2 prezintă mulţimea A₂ în cazul în care setul de pătrate eliminate la fiecare pas este {1,4,6,8,10}. Operaţia de împărţire şi eliminare se face la infinit, păstrând însă mereu acelaşi set de indici de pătrate eliminate. Notăm mulţimea rămasă după repetarea de o infinitate de ori a eliminării cu A_Ą. Observaţi că mulţimea A_Ą nu este vidă. De exemplu, dacă pătratul numerotat cu 1 nu se află în setul de pătrate eliminate la fiecare pas, atunci punctul de coordonate (0,0) se află în mulţimea A_Ą.

Se dau patru numere naturale, P_X, Q_X, P_Y, Q_Y, astfel încât 0ŁP_X<Q_XŁ1000 şi 0ŁP_Y<Q_YŁ1000. Aceste numere reprezintă un punct de coordonate raţionale din mulţimea A₀, M(P_X/Q_X,P_Y/Q_Y). Să se determine dacă punctul M aparţine sau nu mulţimii A_Ą.

Date de intrare:

Fişierul text FRACTAL.IN conţine cel mult cinci seturi de date de test de forma:

P_X Q_X // Coordonata X a punctului M

P_Y Q_Y // Coordonata Y a punctului M

NE // Numărul pătratelor eliminate

(0<NE<9)

E₁ E₂ ? E_NE // Indicii pătratelor eliminate (indicii

sunt în ordine strict crescătoare)

Date de ieşire: Pentru fiecare set de date de intrare se va afişa pe ecran o linie conţinând mesajul 'DA' sau 'NU', după cum punctul M aparţine sau nu mulţimii A_Ą. Pe ecran nu se vor afişa alte date de ieşire!

Exemplu:

FRACTAL.IN Răspunsul pe ecran:

1 2 DA

1 2 NU

8

1 2 3 4 6 7 8 9

1 3

2 3

1

1

P049803: Cuvinte încrucişate

Problemă propusă de prof. Ion Maxim, Liceul de Informatică, Suceava

Enunţ:

Într-un careu pătratic de cuvinte încrucişate de dimensiune n sunt plasate p puncte negre.

Din fişierul de intrare CAREU.IN se citesc poziţiile (li ci) ale celor p puncte negre şi cuvinte de lungime cel mult n formate numai din literele mari ale alfabetului englez. Se cere să se completeze careul astfel încât toate cuvintele date să se regăsească în careu (pe orizontală sau pe verticală), eventual separate prin puncte negre.

Într-un careu, numerotarea liniilor şi coloanelor se face de la 1 la n începând din colţul din stânga-sus, în jos şi spre dreapta.

Date de intrare:

Pe prima linie a fişierului de intrare CAREU.IN sunt scrise cele două numere naturale n (3ŁnŁ10) şi p (0ŁpŁ25), despărţite printr-un spaţiu. Pe următoarele p linii sunt scrise perechi de numere naturale, reprezentând poziţiile punctelor negre. În următoarele linii ale fişierului sunt cuvintele care trebuie plasate în careu.

Date de ieşire:

Fişierul de ieşire CAREU.OUT va conţine n linii, fiecare conţinând n caractere, reprezentând careul completat. Punctele negre se reprezintă prin caracterul '@'. În calculul lungimii unei linii sau coloane se includ şi punctele negre, dacă acestea există pe acea linie sau coloană. Între caracterele din fişierul de ieşire nu există spaţii.

Exemplu:

CAREU.IN CAREU.OUT

4 2 C@RA

1 2 ANOD

4 3 SALA

AS AS@S

ROL

C

RA

S

CASA

SALA

ADAS

NAS

ANOD

P049804: Comerţ interplanetar

Problemă propusă de prof. Maria Niţă, Liceul "Emanoil Gojdu", Oradea

Enunţ:

Datorită revoluţiei ştiinţei şi tehnicii, în anul 8991, a devenit posibil comerţul dintre Pământ şi cele mai îndepărtate galaxii din Univers. Pământul doreşte să importe produse din câteva din galaxiile sectorului Napoca. Planetele cuprinse în aceste galaxii exportă produse valoroase, de care omenirea are nevoie. Rapoartele preliminare au evidenţiat următoarele date:

- numărul de planete din fiecare galaxie este cuprins între unu şi 26. Planetele sunt identificate printr-o majusculă.

- fiecare planetă este specializată în producerea şi exportul unui singur produs. Planete distincte exportă produse distincte.

- unele perechi de planete sunt conectate prin linii de transport hiperspaţiale. Dacă planetele A şi B sunt conectate, ele pot face comerţ fără taxe. Dacă planeta C este conectată cu planeta B, dar nu şi cu planeta A, atunci A şi C pot face comerţ prin intermediul lui B, dar B îşi va reţine 5% din întregul transport ca şi taxă. (Deci A va primi doar 95% din ce a trimis C, iar C va primi doar 95% din ce a trimis A). În general, oricare două planete pot face comerţ, cu condiţia de a fi conectate printr-un set de linii de transport, dar fiecare planetă intermediară de pe parcursul drumului îşi va reţine 5% din întregul transport (ceea ce nu este neapărat echivalent cu 5% din cantitatea originală de produs).

- cel puţin o planetă dintr-o galaxie e dispusă să deschidă o linie de transport care să fie conectată cu Pământul. O astfel de linie cu Pământul, este identică cu oricare linie din galaxie, în materie de comerţ. De exemplu, dacă o planetă K deschide o linie pentru a se conecta cu Pământul, atunci planeta K va face comerţ fără taxe cu Pământul, sau poate face comerţ cu orice planetă conectată cu K, cu condiţia să plătească taxele planetelor intermediare.

Există o standardizare prin care s-a asociat o valoare relativă (un număr real pozitiv, mai mic decât 10) produsului de bază al fiecărei planete. Cu cât numărul este mai mare, cu atât este produsul mai valoros. Mai multe produse de valoare pot fi revândute cu un profit mai mare.

Să se determine planeta care are exportul cel mai mare spre Pământ, atunci când taxele sunt luate în considerare.

Date de intrare:

Fişierul de intrare IMPORT.IN, conţine descrierea uneia sau mai multor galaxii. Fiecare descriere a unei galaxii începe cu o linie care conţine un număr întreg N ce reprezintă numărul planetelor din galaxie. Următoarele N linii conţin descrierea fiecărei planete sub următoarea formă: O literă (pentru identificarea planetei), un spaţiu, valoarea relativă a exportului planetei, sub forma d.dd, un spaţiu, un string care conţine litere şi/sau caracterul '*'; o literă indică o linie de transport către acea planetă, şi '*' indică o linie de transport către Pământ.

Date de ieşire:

În fişierul de ieşire, IMPORT.OUT, pentru fiecare descriere a unei galaxii, trebuie listată o singură linie de forma "Import din P", unde P este litera planetei cu cel mai mare export, după ce taxele de transport au fost luate în considerare. (Dacă mai multe planete au aceeaşi valoare de export, atunci se va lista planeta care are prioritate alfabetică).

Exemplu:

IMPORT.IN IMPORT.OUT

1 Import din F

F 0.81 * Import din A

5 Import din A

E 0.01 *A

D 0.01 A*

C 0.01 *A

A 1.00 EDCB

B 0.01 A*

10

S 2.23 Q*

A 9.76 C

K 5.88 MI

E 7.54 GC

M 5.01 OK

G 7.43 IE

I 6.09 KG

C 8.42 EA

O 4.55 QM

Q 3.21 SO

P049805: Aeroport

problemă propusă de asistent Simona Motogna, Universitatea Babeş-Bolyai, Cluj-Napoca şi prof. Clara Ionescu, Liceul "Tiberiu Popoviciu", Cluj-Napoca

Enunţ:

Pe un aeroport de tranzit sunt n terminale şi m porţi pe fiecare terminal. Călătorii aterizează cu un avion şi vor decola - în scopul de a ajunge la destinaţie - cu un alt avion. Aterizarea are loc la un anumit terminal, la o anumită poartă, iar decolarea la altă poartă, eventual de pe alt terminal. În consecinţă, toţi călătorii au de traversat un drum în interiorul aeroportului de la poarta de aterizare la poarta de decolare. Distanţele dintre porţi, terminale, respectiv prima poartă de pe terminal la coridorul central, sunt identice (x=1).

Realizaţi o planificare a aterizărilor şi decolărilor astfel încât suma lungimilor drumurilor pe care o vor străbate călătorii în aeroport să fie minimă.

Atenţie: un avion aterizat nu poate fi programat pentru decolare!

Date de intrare:

Pe prima linie a fişierului AERO.IN se află două numere întregi n şi m, reprezentând numărul de terminale, respectiv numărul de porţi de pe fiecare terminal (1<=n<=10, 1<=m<=10). Pe următoarele linii se află date cu privire la călătoriile care trebuie planificate sub forma:

loc1 loc2 nr_pasageri

unde loc1 şi loc2 sunt şiruri de caractere având cel mult 30 de caractere, reprezentând denumirile localităţilor, nr_pasageri este un număr întreg (1Łnr_pasageriŁ100). Prima localitate reprezintă locul de unde vin călătorii, cea de a doua reprezintă localitatea unde se duc. Datele sunt despărţite printr-un spaţiu.

Date de ieşire:

Rezultatele se vor scrie în fişierul text AERO.OUT care va conţine pe prima linie un număr întreg, reprezentând suma lungimilor drumurilor pe care o vor parcurge călătorii. Pe liniile care urmează se vor scrie date cu privire la planificarea zborurilor:

localitate poarta

Datele vor fi despărţite prin câte un spaţiu.

Exemplu:

AERO.IN AERO.OUT

2 4 75

Bucuresti Washington 27 Bucuresti 2

Budapesta New_York 13 Washington 3

Bucuresti Chicago 30 Budapesta 5

Praga Washington 5 New_York 6

Chicago 1

Praga 4

P049806: Asemănare

problemă propusă de lector Vasile Prejmerean, Universitatea Babeş-Bolyai, Cluj-Napoca

Enunţ:

Se dau poligoanele P=(P₁,P₂,...,P_n) şi Q=(Q₁,Q₂,... ,Q_n) situate în plan, prin coordonatele reale ale vârfurilor succesive P_i(x_i,y_i), şi Qj(,), i,jÎ{1,...,n} (3ŁnŁ100).

Se cere sa se determine daca cele doua poligoane P şi Q sunt asemenea, caz în care se va specifica succesiunea vârfurilor din Q corespunzătoare vârfurilor P₁,P₂,...,P_n din P.

Date de intrare:

Fişierul de intrare POL.IN conţine:

n - numărul de vârfuri

x₁ y₁ - coordonatele primului vârf al poligonului P

...

x_n y_n - coordonatele vârfului n al poligonului P

, - coordonatele primului vârf al poligonului Q

...

, - coordonatele vârfului n al poligonului Q

Date de ieşire:

Fişierul de ieşire POL.OUT va avea forma:

i₁ i₂ . . . i_n - numerele de ordine ale vârfurilor din Q

sau

0 - dacă cele două poligoane nu sunt asemenea

Exemple:

POL.IN

5

0 0

0 4

4 4

6 2

4 0

0 0

2 2

0 4

4 4

4 0

POL.OUT

0

POL.IN

5

0 0

0 4

2 6

4 4

4 0

0 1

0 3

2 3

2 1

1 0

POL.OUT

3 4 5 1 2

sau

2 1 5 4 3

[cuprins]