Încercați-vă puterile...

PROBLEME propuse pentru REZOLVARE

Olimpiada Națională de Informatică, anul acesta a fost organizată la Mediaș. S-au acordat 11 premii I, 24 premii II, 33 premii III și 45 mențiuni. Mai ales pentru cei care nu au participat la olimpiadă, iată enunțurile problemelor!

CLASA IX

P059901: Expresie

prof. Marinel Șerban, Liceul de Informatică "Grigore Moisil", Iași

Prima linie a fișierului text EX.IN conține o expresie aritmetică fără paranteze având cel mult 255 caractere. Caracterele care pot să apară sunt:

- cifrele de la 0 la 9;

- literele mici a, b, c, d și e reprezentând variabile;

- operatorii aritmetici binari + și -

Pe următoarele linii din fișier pot să apară linii de forma:

<variabilă>=<întreg>

reprezentând atribuiri de valori pentru variabilele care apar în expresie. Valorile care pot fi atribuite sunt cuprinse în intervalul (-1000000000,1000000000). O variabilă poate interveni într-o atribuire cel mult o dată.

Scopul programului pe care trebuie să-l scrieți este evaluarea și afișarea valorii expresiei pe prima linie a fișierului text EX.OUT.

Semnificația caracterelor care apar în expresie este cea obișnuită într-o expresie aritmetică. Orice succesiune de cifre formează o constantă naturală cuprinsă între 0 și 1000. Între o constantă și o variabilă consecutive, ca și între două variabile consecutive se consideră operația de înmulțire. Astfel, expresia 235aeae+c-12bb conține constantele 235 și 12 și are semnificația aritmetică:

235aeae+c-12bb

Dacă valoarea expresiei nu poate fi calculată, programul va afișa mesajul NEDEFINITA pe prima linie a fișierului de ieșire EX.OUT.

Exemple

EX.IN EX.OUT

abc NEDEFINITA

a=1

b=2

EX.IN EX.OUT

235aeae+c-12bb 93981

b=1

c=-7

a=10

e=2

P059902: Nasturi

Stelian Ciurea, cadru didactic la Universitatea "Lucian Blaga", Sibiu

În fiecare pătrat al unei table de șah, de dimensiuni nŽn, unde n este număr par, 3<n<31) avem câte un nasture. Știind că urmează să luăm x nasturi de pe tablă, programul vostru trebuie să precizeze dacă putem face această operație astfel încât, pe fiecare linie și pe fiecare coloană, să rămână un număr par de nasturi.

Date de intrare

Fișierul text NASTURI.IN conține pe prima linie numerele n și x separate print-un spațiu.

Date de ieșire

Rezultatele se vor scrie în fișierul text NASTURI.OUT care va avea formatul:

- dacă problema are soluție, pe linia i (i=1,2,…,n) a fișierului va fi descrisă linia i a tablei: pentru un pătrat cu nasture se va scrie litera 'o' iar pentru pătrat liber, caracterul '.' (punct). Între aceste caractere nu se vor afla spații sau alte caractere;

- dacă problema nu are soluție, pe prima linie a fișierului se va scrie textul 'fara solutie' (cu litere mici!).

Exemplu

NASTURI.IN NASTURI.OUT

4 4 oo..

oooo

oo..

oooo

P059903: Partide și coaliții

Valentin Gheorghiță, student, Universitatea Politehnică, București

În țara lui Papură Vodă s-au organizat alegeri anticipate la care participă n partide numerotate de la 1 la n (nŁ20). La încheierea acestora, se cunoaște numărul de voturi obținute de fiecare partid. Pe baza acestor voturi se va calcula, pentru fiecare partid, "puterea" acestuia, defnită astfel: "puterea" unui partid reprezintă numărul de coaliții nemajoritare în care pătrunzând, acestea devin majoritare.

O coaliție poate fi formată din unul sau mai multe partide.

O coaliție de partide este majoritară atunci când totalul voturilor obținute de partidele ce o formează este strict mai mare decât jumătate din totalul voturilor exprimate la alegeri.

Cunoscându-se numărul n de partide și numărul de voturi obținute de fiecare dintre ele, să se determine "puterea" fiecărui partid.

Date de intrare

Fișierul text partide.in are următorul format:

Pe prima linie este scris un număr natural n, reprezentând numărul de partide participante la alegeri.

Pe următoarea linie se găsesc n numere naturale separate printr-un spațiu:

v1 v2...vn unde vi (0ŁviŁ3000) reprezintă numărul de voturi obținut de partidul i (1ŁiŁn). Avem SviŁ5000, adică totalul voturilor exprimate la alegeri nu depășește 5000.

Datele de ieșire:

În fișierul text partide.out pe o singură linie se vor scrie n numere: p1 p2...pn unde pi reprezentă puterea partidului i (1ŁiŁn); numerele vor fi despărțite între ele printr-un singur spațiu.

Exemplu

partide.in partide.out

3 3 1 1

2 1 1

Pentru lămurirea rezultatului din exemplu specificăm că partidul 1 are puterea 3 deoarece poate intra în trei coaliții care vor deveni astfel majoritare:

- în coaliție cu partidul 2;

- în coaliție cu partidul 3;

- în coaliție cu coaliția formată din partidele 2 și 3.

P05994: Furtună în Balcani

Valentin Gheorghiță, student, Universitatea Politehnică, București

Taberele militare de pe teritoriul Yugoslaviei, amplasate în interiorul țării se pregătesc pentru un eventual atac terestru din partea forțelor NATO. Taberele nu ating marginea hărții și nu sunt lipite unele de altele.

Soldații sârbi trebuie să înconjoare toate taberele cu câte un câmp de mine plasate pe direcțiile N, S, E sau V față de sârma ghimpată ce împrejmuiește fiecare tabără.

Ajutați-i pe soldații sârbi să plaseze corect minele.

Date de intrare

Fișierul text NATO.IN conține harta taberelor sârbe sub forma unei matrice cu m linii și n coloane (m,nŁ100), cu elemente caracterele '.' și 'X';

- '.' (punct) reprezintă teren (din interiorul sau exteriorul unei tabere);

- 'X' reprezintă sârma ghimpată care înconjoară taberele.

Pe prima linie a fișierului se găsesc dimensiunile matricei m și n, numere naturale separate printr-un spațiu. Pe următoarele m linii se găsește descrierea hărții:

c[1,1] c[1,2] ... c[1,n]

c[2,1] c[2,2] ... c[2,n]

...

c[m,1] c[m,2] ... c[m,n]

unde c[i,j] (1ŁiŁm, 1ŁjŁn) sunt caractere din cele permise ('.' și 'X'). Prima și ultima linie, respectiv coloană, reprezintă marginea hărții, deci conțin numai caracterul '.'.

Obervație

Taberele sunt bine delimitate și conțin cel puțin un punct în interior.

Date de ieșire

Fișierul text NATO.OUT conține matricea de intrare completată cu caracterul M pe pozițiile de amplasare a minelor.

Exemplu

NATO.IN NATO.OUT

5 11 .MMM...M...

........... MXXXM.MXM..

.XXX...X... MX.XXMX.XM.

.X.XX.X.X.. MXXXM.MXMXM

.XXX...X.X. .MMM...M.M.

...........

P059905: Semne

Prof. Eugen Ionescu, Liceul de Informatică "Tiberiu Popoviciu", Cluj

Fie n numere naturale consecutive, așezate unul după altul: 1,2,3,...,n. Să se scrie un program care stabilește semnul (+, - sau *) care trebuie pus în fața fiecărui element al șirului, astfel încât, evaluând expresia rezultată, să obținem valoarea 0. Există o singură excepție și anume în fața primului element trebuie pus fie +, fie -.

Ordinea în care se efectuează operațiile este conform regulilor aritmetice.

Date de intrare

Numărul n (1<n<1000000) se va citi de pe prima linie a fișierului text ZERO.IN.

Date de ieșire

Secvența de semne care trebuie scrise între numerele naturale 1,2,3,...,n se va scrie în fișierul text ZERO.OUT. Între oricare două semne (+, -, *) nu se va scrie nici număr, nici virgulă, nici spațiu.

În cazul în care nu se poate obține o expresie având valoarea 0, în fișier, pe prima linie se va scrie 'NU'.

Exemple:

ZERO.IN ZERO.OUT

11 ++--++--++-

(Echivalent cu +1+2-3-4+5+6-7-8+9+10-11=0)

ZERO.IN ZERO.OUT

5 -*++-

(Echivalent cu -1*2+3+4-5=0)

P059906: Teancul de farfurii

Prof. Dana Lica, Colegiul Național "I. L. Caragiale", Ploiești

În bucătăria unei gospodine se află un teanc de farfurii, care așteaptă să fie spălate. Gospodina care urmează să le spele este pusă în fața unei probleme: trebuie să spele un număr cât mai mare de farfurii într-un anumit timp. Ea cunoaște câte minute durează spălarea fiecărei farfurii; de asemenea ea poate să renunțe la spălarea ei și să o spargă, spargerea necesitând exact un minut, pentru orice farfurie.

Farfuriile sunt numerotate cu numere de la 1 la n, începând cu farfuria din vârful teancului spre cea de la baza teancului, ca în figura alăturată.

Farfuria care poate fi spălată la un moment dat este cea situată în vârful teancului. Inițial gospodina poate spăla sau sparge farfuria cu numărul 1, după care poate spăla sau sparge cu farfuria numărul 2, ș.a.m.d. Gospodina va trebui să decidă dacă spală o anumită farfurie sau o sparge, știind că are la dispoziție un timp t exprimat în minute.

Determinați care este numărul maxim nmax de farfurii pe care le poate spăla gospodina în timpul t dat.

Determinați de asemenea și timpul minim tmin (tminŁt) în care se spală cele nmax farfurii.

Date de intrare

Fișierul text farfurii.in are următorul format:

Pe prima linie sunt scrise două numere naturale separate printr-un spațiu: n t, reprezentând numărul de farfurii, (nŁ75) respectiv timpul t (tŁ1000) pe care îl are la dispoziție gospodina.

Pe următoarea linie se găsesc n numere naturale separate printr-un spațiu: t1 t2 ... tn, tiŁ100, reprezentând timpul de spălare al farfuriei i, în minute, (1ŁiŁn).

Date de ieșire

Rezultatele (nmax tmin) se vor scrie în fișierul text farfurii.out pe o singură linie. Cele două numere reprezintă numărul maxim de farfurii spălate și timpul efectiv de spălare (tminŁt).

Exemplu

farfurii.in farfurii.out

4 4 2 3

1 4 1 3

CLASA X

P059907: Gaze la vile

Prof. Ioan Maxim, Liceul de Informatică, Suceava

Proprietarii a n (2ŁnŁ50) vile din zona rezidențială a municipiului Mediaș au solicitat Regiei ROMGAZ instalarea de cisterne cu metan. ROMGAZ dispune de cisterne care asigură consumul pentru k vile pe o periodă acceptabilă de timp (k este divizor al lui n, 2ŁkŁn).

Pentru a i se asigura securitatea, fiecare cisternă este instalată lângă o vilă. Costul conectării unei vile este egal cu lungimea conductei până la cisternă sau până la o altă vilă conectată.

Să se determine grupe de k vile astfel încât costul conectării tuturor vilelor să fie minim.

Observații

Există vile între care nu se poate instala conductă de conectare. Distanța între acestea nu este specificată. Costul conectării vilei de lângă cisternă este nul.

Date de intrare

Fișierul de intrare gaze.in conține pe prima linie:

n k - numărul total de vile și numărul de vile care pot fi conectate la o cisternă, urmată de un număr de linii de forma:

i j1 d1 j2 d2 ... jm dm - vila i se poate conecta la una dintre vilele j1,j2,...,jm, și se află respectiv, la distanța d1,d2,...,dm de acestea (ij1,ij2,..., ijm). Distanțele d1,d2,...,dm sunt numere naturale (1Łd1,d2,...,dmŁ50).

Datele de ieșire

Fișierul de ieșire gaze.out conține pe prima linie:

t - costul total al conectării celor n vile, urmat de (n div k) linii de forma:

j1 j2 ... jk c - vilele j1 j2 ... jk sunt conectate la aceeași cisternă, iar costul conectării lor este c, dacă cele n vile pot fi conectate câte k și

0 - în situația în care problema nu are soluție.

Exemple

gaze.in gaze.out

9 3 20

1 6 1 8 3 9 5 2 4 6 6

2 4 4 6 2 1 8 9 8

3 5 3 7 3 3 5 7 6

4 9 6

5 7 3

gaze.in gaze.out

4 2 0

1 2 1 3 1 4 1

P059908: Rețea

Prof Dorin Mânz, Liceul de Informatică, Timișoara

Se dorește legarea în rețea a n calculatoare (nÎ[2,100]). Problema constă în obținerea unei rețele liniare în care fiecare calculator este legat exact de alte două calculatoare, exceptând calculatoarele din capete, care au o singură legătură. De exemplu, în desenul de mai jos calculatoarele sunt identificate prin coordonatele lor (relativ la un sistem de axe neprecizat).

Scopul problemei constă în minimizarea lungimii cablului folosit; se cere deci un mod optim de reconectare al calculatoarelor în linie, astfel încât cablul folosit să aibă lungimea minimă. Necesarul de cablu pentru a lega direct două calculatoare este egal cu distanța dintre acestea, la care se adaugă 10 metri de cablu, utilizați pentru conexiuni anexe.

Date de intrare

Fișierul de intrare cu numele RETEA.IN va conține pe prima linie un singur număr n (numărul de calculatoare). În continuare, pe linii succesive, se dau coordonatele fiecărui calculator sub forma unei perechi de numere întregi (din intervalul [0,100]). Pentru exemplul prezentat avem:

5

8 11

8 16

12 16

13 8

24 10

Date de ieșire

Ieșirea constă din n linii. Pe prima linie a fișierului RETEA.OUT se va scrie lungimea totală a cablului. Fiecare din celelalte linii este formată din trei numere l, s și e, unde: l este lungimea cablului necesar legării directe a calculatoarelor date la intrare pe liniile s respectiv e. Ordinea de parcurgere a rețelei este arbitrară.

Pentru rețeaua optimă din exemplu, ieșirea va fi:

66.01

14 3 2

15 2 1

15.83 1 4

21.18 4 5

Acest mod de conectare corespunde figurii de mai jos:

P059909: Zone

Prof. Adrian Niță, Liceul "Emanuil Gojdu", Oradea

Considerăm un set de n puncte, 0<nŁ100.

Centrul Geometric este un punct care are coordonatele x și y, media aritmetică a absciselor, iar y este media aritmetică a ordonatelor tuturor punctelor.

Se definesc următoarele noțiuni:

- Dreptunghi este cel mai mic dreptunghi care are laturile paralele cu axele de coordonate și care include toate punctele date;

- Zona este un cerc cu centru în Centrul Geometric care este inclus în Dreptunghi;

- Zona Moartă este cea mai mare Zonă care nu conține nici un punct, din cele n date, în interiorul său;

- Mega Zona este cea mai mare Zonă.

Pentru fiecare set de puncte din fișierul de intrare, va trebui să determinați:

- coordonatele colțurilor Stânga-Jos, Dreapta-Sus ale Dreptunghi-ului;

- diametrul Zonei Moarte;

- procentul punctelor care sunt în interiorul Mega Zonei. Se consideră că punctele de pe circumferința cercului fac parte din interior.

Date de intrare

Fișierul Zone.In conține n+1 linii. Pe prima linie este scris numărul n, reprezentând numărul de puncte, iar pe fiecare din următoarele n linii sunt scrise coordonatele reale x, y ale celor n puncte separate prin spații.

Date de ieșire

Rezultatele, (numere reale cu două zecimale, obținute prin rotunjire) se scriu în fișierul Zone.Out, care are structura:

- pe liniile unu și doi se vor scrie coordonatele Dreptunghi-ului, coordonatele x, y pentru Stânga-Jos și respectiv Dreapta-Sus;

- pe a treia linie se vor scrie coordonatele Centrului Geometric;

- pe a patra linie se scrie diametrul Zonei Moarte și procentul de puncte din Mega Zonă.

Pe fiecare linie, numerele vor fi separate prin câte un spațiu.

Exemplu

Zone.In Zone.Out

10 -2.00 -1.00

-1.6 1.8 2.00 2.00

1 2 0.00 0.40

2 0.6 0.80 40.00

1.6 -1

-1 -1

-2 0

-1 1

0 1

1 -0.4

0 0

P059910: Seamănă, dar nu răsare

Prof. Dorina Popa, Liceul "Mihail Eminescu", Botoșani

Un graf neorientat are proprietatea că gradul oricărui vârf este mai mare decât jumătatea numărului vârfurilor. Graful se dă prin matricea sa de adiacență. Afișați un ciclu hamiltonian al grafului dat. Dacă graful nu are nici un ciclu hamiltonian, se va afișa mesajul: SEAMANA, DAR NU RASARE.

Date de intrare

Fișierul de intrare HAM.IN conține pe prima linie:

n - numărul vârfurilor grafului (3ŁnŁ100), urmat de n linii de forma:

ai1 ai2 ... ain - cu semnificația aij=1 dacă nodurile i și j sunt adiacente și aij=0 în caz contrar.

Date de ieșire

Fișierul de ieșire HAM.OUT conține pe o singură linie vârfurile ciclului hamiltonian, în ordinea în care acestea apar în ciclu, separate printr-un spațiu. Se cere o singură soluție.

Exemplu

HAM.IN HAM.OUT

5 1 5 2 3 4

0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

1 1 1 0 0

1 1 1 0 0

P059911: La cules de zmeurică

Cătălin Frâncu, student, Universitatea Politehnică, București

O colonie de termite a ieșit la cules de zmeurică în tufa din apropierea mușuroiului. Consiliul Economic al Mușuroiului a hotărât că această tufă trebuie să asigure hrana mușuroiului atât anul acesta, cât și anul următor, după aceasta ea nemaiprezentând interes.

Tufa de zmeurică are un aspect arborescent: din pământ pornesc, una sau mai multe ramuri, care la rândul lor se ramifică în mai multe rămurele etc. În fiecare an, în vârful fiecărei crenguțe care nu se mai ramifică, crește câte un bob de zmeură. Pentru buna desfășurare a culesului, Consiliul de Supervizare a etichetat îmbinările rămurelelor și vârfurile crenguțelor cu numere naturale consecutive, începând de la 1. Rădăcina tufei (cea de la contactul cu solul) are numărul 1. În figura din stânga, fructele de zmeură cresc în nodurile 2, 5, 6 și 7. Bugetul mușuroiului se modifică astfel în timpul culesului:

1) Fiecare fruct cules aduce P unități de hrană în hambar.

2) Culegerea unui fruct "en detail" înseamnă trimiterea unei termite de la sol până la acel fruct pentru a-l tăia de pe crenguța lui. Termita consumă câte C unități de hrană din hambar pentru fiecare rămurică pe care o parcurge până la bobul de zmeură. În figura de mai sus, culegerea fructelor 2, 5 și 7 necesită consumarea a 2C unități de hrană, iar culegerea fructului 6 necesită C unități de hrană. Anul viitor, un nou bob va crește în locul celui cules.

3) Zmeurica poate fi culeasă și "en-gros", producând însă daune tufei. Este posibil ca un nod întreg să fie retezat, împreună cu tot subarborele său. Pentru aceasta va fi trimisă o termită de la sol până la nodul care va fi retezat, termita consumând câte C unități de hrană pentru fiecare ramură parcursă. După aceasta, fructele de pe creanga retezată cad pe sol și sunt culese cu cost 0. În figură, retezarea nodului 4 se face cu cost 1C și aduce un profit de 2P (datorită fructelor din nodurile 2 și 7). Dezavantajul este că anul viitor în nodul retezat va crește o singură zmeurică. Dacă nodul 1 este retezat (tufa este tăiată din rădăcină), anul viitor nu va mai crește nimic.

Se cere să se planifice o manieră de culegere a zmeurei în primul și în al doilea an, astfel încât în final hambarul să fie cât mai îmbelșugat.

Date de intrare

Fișierul text ZMEURICA.IN conține pe prima linie valorile N, P și C (2ŁNŁ100, 1ŁP, CŁ1000), separate prin spații. N este numărul total de noduri etichetate, iar P și C sunt numere întregi. Pe următoarele N linii se află descrierea tufei de zmeură. Linia k+1 conține numărul de noduri care se află imediat deasupra nodului k în tufă, apoi valorile acestor noduri în ordine crescătoare. Pentru figura de mai sus fișierul este:

7 5 1 % N=7, P=5, C=1

3 3 4 6 % După nodul 1 (rădăcina) urmează trei noduri, și anume 3, 4 și 6

0 % După nodul 2 nu mai urmează nimic

1 5 % După nodul 3 urmează un nod, și anume 5

2 2 7 % După nodul 4 urmează două noduri, și anume 2 și 7

0 % După nodul 5 nu mai urmează nimic

0 % După nodul 6 nu mai urmează nimic

0 % După nodul 7 nu mai urmează nimic

Date de ieșire

Fișierul text ZMEURICA.OUT trebuie să conțină trei linii. Pe prima se va afla cantitatea maximă de hrană (venit minus cheltuieli) care poate fi acumulată din exploatarea tufei de zmeurică. Pe linia a doua se vor indica, separate prin spații, în orice ordine, numerele nodurilor unde se vor face tăieturi în primul an (pentru a tăia fie un fruct, fie o creangă întreagă). Pe linia a treia se vor indica nodurile unde se fac tăieturi în al doilea an. Dacă în al doilea an nu mai există nici un nod de tăiat, linia a treia va fi lăsată goală. Pentru exemplul dat, ieșirea poate fi:

34

3 6 2 7

1

Într-adevăr, în anul I retezăm rămurica nodul 3, culegând fructul 5 (cost 1, venit 5), și culegem fructele 6 (cost 1, venit 5), 2 (cost 2, venit 5) și 7 (cost 2, venit 5). În anul II vor crește fructe în nodurile 3, 6, 2 și 7, pe care le culegem "en gros", tăind tufa din rădăcină (cost 0, venit 54). În total avem costul 6 și venitul 40, deci profitul net este 34, maximul care se poate "stoarce" din tufa dată.

P059912: Degrade

Prof. Ioan Maxim, Liceul de Informatică, Suceava

Un tablou pătratic, de dimensiuni nŽn (2ŁnŁ150) conține numere naturale din intervalul [0,99]. Aceste numere reprezintă nuanțe de "gri" (0 este alb, 99 este negru).

Se cere ca numai prin interschimbări de elemente alăturate (pe linie, coloană sau diagonală), să se realizeze în tablou un degrade cu raza pe diagonala principală (nuanța cea mai apropiată de alb va fi în colțul din stânga sus, iar cea mai apropiată de negru în colțul din dreapta jos).

Pe diagonala secundară și pe orice paralelă la aceasta, nuanțele mai închise sunt dispuse spre exterior, adică ai,jŁ min(ai,j+1,ai+1,j)Ł max(ai,j+1,ai+1,j)Łai+1,j+1 pentru orice i,j=1,n-1 și ai,j+1łai+1,j pentru iŁj și ai,j+1Łai+1,j pentru i<j.

Date de intrare

Fișierul de intrare degrade.in conține n linii cu câte n elemente, separate prin câte un spațiu.

Datele de ieșire

Fișierul de ieșire degrade.out va conține tabloul prelucrat (tot n linii cu câte n numere separate printr-un spațiu).

Exemple

degrade.in degrade.out

4 1 1 3

2 3 2 4

degrade.in degrade.out

4 1 2 3 1 2 3 5

2 3 9 5 2 3 4 7

3 4 6 7 3 4 4 9

5 6 9 4 5 6 6 9

CLASA XI-XII

P059913: Formă normală

Prof. Emanuela Cerchez, Liceul de Informatică "Grigore Moisil", Iași

Fie E o expresie care respectă următoarele condiții:

- poate conține numai operatorii + (adunare) și * (înmulțire);

- operanzii pot fi doar nume de variabile formate dintr-o singură literă mică a alfabetului englez;

- poate conține paranteze rotunde.

Știind că puteți aplica următoarele proprietăți:

1. Comutativitatea adunării: a+b=b+a,"a,b.

1'. Comutativitatea înmulțirii: a*b=b*a, "a,b.

2. Asociativitatea adunării: a+(b+c)=(a+b)+c = a+b+c, "a,b,c.

2'. Asociativitatea înmulțirii: a*(b*c)=(a*b)*c=a*b*c, "a,b,c.

3. Distributivitatea înmulțirii față de adunare: a*(b+c)= a*b+a*c, "a,b,c.

Aduceți expresia dată în formă normală.

Forma normală a unei expresii este o sumă de produse, echivalentă cu expresia dată, astfel încât atât termenii sumei, cât și factorii din fiecare termen al sumei sunt ordonați alfabetic.

Date de intrare

Fișierul de intrare EXP.IN conține pe prima linie o expresie având cel mult 100 de caractere, corectă în raport cu restricțiile enunțate mai sus. Expresia nu conține spații.

Date de ieșire

Expresia în formă normală (având lungimea maximă de 255 de caractere) va fi afișată pe prima linie a fișierului de ieșire EXP.OUT, fără spații.

Exemplu

EXP.IN EXP.OUT

x*a+c*(a+b*c*d) a*c+a*x+b*c*c*d

P059914: Împărțirea poligonului

Prof. Doru Popescu Anastasiu, Liceul "Radu Greceanu", Slatina

Se dă un poligon convex cu n vârfuri (4ŁnŁ50) prin coordonatele vârfurilor (numere întregi din intervalul [-2000, 2000]) date în sensul acelor de ceasornic.

a) Să se verifice dacă poligonul are centru de simetrie. Punctul S este centru de simetrie dacă simetricul oricărui punct de pe poligon față de S aparține poligonului.

b) Să se împartă poligonul (dacă are centru de simetrie) în paralelograme.

Date de intrare

Datele de intrare se citesc din fișierul de tip text POLIGON.IN având structura:

n

x1 y1

x2 y2

...

xn yn

Date de ieșire

Datele de ieșire se vor scrie în fișierul de tip text POLIGON.OUT având structura:

mesaj

px11 py11 px21 py21 px31 py31 px41 py41

px12 py12 px22 py22 px32 py32 px42 py42

...

px1k py1k px2k py2k px3k py3k px4k py4k

unde mesaj poate fi DA sau NU, în funcție de existența centrului de simetrie.

- dacă mesajul este 'NU', fișierul va conține doar prima linie;

- dacă mesajul este 'DA', fișierul va conține în plus atâtea linii câte paralelograme au rezultat în urma împărțirii poligonului inițial;

- un paralelogram este descris prin coordonatele vârfurilor sale în sensul acelor de ceasornic.

Exemple

POLIGON.IN POLIGON.OUT

8 DA

20 30 20 0 10 10 20 10 30 0

30 30 10 10 10 20 20 20 20 10

40 20 10 20 20 30 30 30 20 20

40 10 20 10 20 20 30 10 30 0

30 0 20 20 30 30 40 20 30 10

20 0 40 20 40 10 30 0 30 10

10 10

10 20

POLIGON.IN POLIGON.IN

4 NU

10 20

40 30

40 10

20 10

Restricție:

Dacă două paralelograme cu interioarele disjuncte au o latură comună și alte două laturi în prelungire (ca în figura alăturată paralelogramele ABED și BCFE) se va afișa un singur paralelogram (în figură ACFD).

P059915: Peisaje

Lect. univ. Clara Ionescu, Universitatea "Babeș Bolyai", Cluj

Linia orizontului dintr-un peisaj se poate desena pe un caroiaj, cu ajutorul caracterelor '/' și '\', aceasta conturându-se într-un "zig-zag" obișnuit. O linie a orizontului este corectă dacă este desenată cu același număr de caractere '/', respectiv '\' și fiecare coloană a caroiajului conține un singur caracter. De asemenea, această linie trebuie să pornească dintr-o celulă a caroiajului aflată la nivelul mării și se termină tot într-o celulă aflată la nivelul mării. Pe parcursul trasării, linia nu coboară niciodată sub nivelul mării. Linia orizontului începe cu caracterul '/' și se termină cu caracterul '\'. După caracterul '/' poate fi plasat pe coloana următoare caracterul '/' pe linia superioară sau caracterul '\' pe aceeași linie. Analog, după caracterul '\' poate fi plasat pe coloana următoare caracterul '\' pe linia inferioară sau caracterul '/' pe aceeași linie.

Știind că într-o celulă a caroiajului se desenează un singur caracter, definim înălțimea unui munte ca fiind egală cu numărul liniilor din caroiaj dintre nivelul mării și vârful muntelui (muntele /\ are înălțimea 1). Vârful muntelui se formează din două caractere /\ situate pe aceeași linie și pe coloane alăturate.

Scrieți un program care calculează numărul de posibilități de a trasa linii ale orizontului cu un număr precizat de perechi de caractere '/' și '\', astfel încât cel puțin un munte are o înălțime mai mare sau egală cu o anumită înălțime dată.

/ \

/ \ / \

/ \ / \

/ \

/ \

/ \ / \ / \

/ \ / \ / \

­ nivelul mării

Date de intrare

Din fișierul de tip text PEISAJ.IN se vor citi două numere naturale n și k (1n31, reprezentând numărul caracterelor '/', (acesta fiind același cu numărul caracterelor '\'). Numărul k (1ŁkŁn) reprezintă înălțimea minimă a cel puțin unui munte.

Date de ieșire

În fișierul de tip text PEISAJ.OUT se va scrie numărul liniilor de orizont "cu munți", ce pot fi desenate cu n perechi de caractere ('/', respectiv '\'), unde cel puțin un munte are o înălțime cel puțin egală cu k.

Exemplu

PEISAJ.IN PEISAJ.OUT

3 2 4

Corespunzător exemplului avem următoarele linii de orizont posibile:

/ \

/ \ / \ / \ / \ / \

/ \ / \ / \ / \ / \ / \

­ nivelul mării

P059916: Mutantul călător

Prof. Roxana Tâmplaru, Liceul de Informatică, Craiova

Se consideră NP planete (0<NPŁ60). Fiecare planetă este împărțită în două emisfere: una radiată (nivelul radiațiilor fiind un număr întreg din intervalul [1,1000]), și una neradiată (nivelul radiației este 0).

Un mutant vizitează pe rând toate planetele, în ordinea 1,2,...,NP, fiecare planetă fiind vizitată o singură dată.

Mutantul poate veni pe o planetă în oricare dintre emisfere și poate părăsi planeta prin oricare dintre ele.

De asemenea, el poate trece dintr-o emisferă în alta.

Pentru fiecare dintre planete, mutantul trebuie să treacă o singură dată prin emisfera radiată, și de zero sau mai multe ori prin cea neradiată.

Pe fiecare planetă, în emisfera radiată, mutantul suferă o singură transformare, iar în cea neradiată suferă una sau mai multe transformări succesive. În urma unei transformări, acesta poate lua una din formele posibile, în funcție de nivelul radiației și de forma sa curentă. Mutantul poate avea cel mult 250 forme distincte (F1,F2,...FNF), care se reprezintă prin valori întregi din intervalul [0,249]. Există și radiații pentru care mutantul este distrus, deoarece nu se poate transforma în altă formă.

Să se verifice dacă este posibil ca mutantul să ajungă, după ce a părăsit ultima planetă, într-una din formele FF1,FF2,...,FFM unde (0<MŁ250), prin cel mult 500 de transformări, pornind de la forma inițială F0 (una din formele posibile), în condițiile în care radiațiile pe cele NP planete sunt Ri, (1ŁiŁ NP).

În cazul în care problema poate fi soluționată se va afișa o singură soluție.

Date de intrare

Fișierul MUTANT.IN are următorul conținut:

Pe prima linie: NP

Pe a doua linie: NF F1 F2 ... FNF

Pe linia a treia: F0

Pe linia a patra: R1 R2 ... RNP

Pe linia a cincea: M FF1 FF2 ... FM

În continuare, până la sfârșitul fișierului, pe fiecare linie se află o transformare posibilă: F R A1 A2 ... unde F este forma curentă, R nivelul radiației, iar Ai sunt formele posibile în care se poate trece din F.

Fișierul conține doar transformările pentru care radiația nu distruge mutantul. Numărul maxim de transformări este 500. Fișierul conține doar numere întregi; cele care se află pe aceeași linie sunt separate printr-un spațiu.

Date de ieșire

Fișierul MUTANT.OUT va avea structura:

a) dacă problema are soluție:

Pe prima linie: DA

Pe a doua linie: B1 C1 B2 C2 ... BP

unde B1,...,BP este succesiunea de forme pentru care:

B1=F0

BP este una din formele FF1,...,FFM

Din forma Bi mutantul trece în forma Bi+1 printr-o singură transformare datorată unei radiații Ci, (zero sau diferită de zero) unde 1Łi<p.

b) dacă problema nu are soluție:

Pe prima linie: NU

Exemplu

MUTANT.IN MUTANT.OUT

2 DA

7 0 1 2 3 4 5 6 0 0 1 1 5 2 6

0

1 2

2 5 6

0 0 1 2

0 1 3

0 2 4

1 1 5

2 0 1

3 1 5

5 2 6

P059917: Oli' la Mediaș...

Prof. Maria Niță, Liceul "Emanuil Gojdu", Oradea

În vederea organizării Olimpiadei de Informatică, n firme de calculatoare doresc să trimită la Mediaș echipamente de tehnică de calcul. Organizatorii au nevoie de n tipuri de echipamente, numerotate de la 1 la n. Transportul echipamentelor presupune anumite cheltuieli, pe care fiecare firmă le prezintă organizatorilor. Știind că toate firmele pot acoperi fără probleme necesarul de tehnică de calcul și că fiecare firmă dispune de toate tipurile de tehnică de calcul, ajutați organizatorii să asigure dotarea tehnică necesară concursului, astfel încât:

- de la fiecare firmă se aduce un singur transport, conținând un singur tip de tehnică de calcul;

- cheltuielile totale pentru realizarea dotării pentru concurs să fie minime.

Date de intrare

Datele de intrare se citesc din fișierul MEDIAS.IN, având structura:

n

c11 c12 c13 ... c1n

c21 c22 c23 ... c2n

...

cn1 cn2 cn3 ... cnn

unde:

- n reprezintă numărul de firme, același cu numărul de tipuri de tehnică de calcul (0<n<100);

- cij reprezintă cheltuielile pentru transportul în Mediaș al tehnicii de calcul de tip i de la firma j (cij sunt numere naturale din intervalul [1,255]).

Date de ieșire

Rezultatele se scriu în fișierul MEDIAS.OUT sub forma:

1 i1 c1i1

2 i2 c2i2

...

n in cnin

min

unde:

- k reprezintă tipul de tehnică de calcul;

- ik reprezintă firma de la care se aduce tehnica de calcul având tipul k;

- ckik reprezintă cheltuielile de transport al tehnicii de tip k de la firma ik, (1ŁkŁn);

- min reprezintă cheltuielile totale necesare pentru dotare.

Exemplu

MEDIAS.IN MEDIAS.OUT

6 1 4 14

17 43 27 14 39 52 2 6 13

29 24 69 90 23 13 3 5 16

18 90 62 12 16 70 4 2 14

58 14 6 18 73 64 5 1 15

15 41 38 36 40 60 6 3 18

25 44 18 44 13 50 90

P059918: Telescaun

Prof. Emanuela Cerchez, Liceul de Informatică "Grigore Moisil", Iași

Un fermier montan dorește să construiască un telescaun în ferma proprie. În acest scop a prospectat terenul și a identificat o zonă de formă dreptunghiulară de maxim interes turistic. A construit apoi o hartă a zonei, a împărțit-o în pătrățele de latură 1 și a înscris în fiecare pătrățel cota porțiunii de teren corespunzătoare. Telescaunul va avea un traseu rectiliniu, care trebuie să unească un punct de cotă maximă (considerat în centrul pătrățelului respectiv) cu un punct de cotă minimă (considerat, de asemenea, în centrul pătrățelului respectiv). Pentru a nu face investiții suplimentare, cotele de-a lungul traseului trebuie să fie în ordine descrescătoare. În cazul în care există mai multe posibilități, fermierul va prefera, evident, un traseu de lungime minimă.

Exemple

Traseul de la maxim la minim parcurge cotele 9,8,6,4,2,1 și este soluție.

Traseul de la maxim la minim parcurge cotele 9,8,6,2,4,1, deci nu este soluție.

Traseul de la punctul de maxim la cel de minim parcurge cotele 9,6,4,1 deci este soluție.

Date de intrare

Datele de intrare se citesc din fișierul COTE.IN care are următoarea structură:

n m

c11 c12 ... c1m

c21 c22 ... c2m

...

cn1 cn2 ... cnm

cu următoarea semnificație:

n = lungimea hărții (nÎ N*, nŁ100),

m = lățimea hărții (mÎN*, mŁ100),

cij = cota porțiunii de teren de coordonate i, j, (ci,jÎN, ci,jŁ6000).

Date de ieșire

Dacă nu se poate găsi nici un traseu care să corespundă cerințelor, fișierul de ieșire COTE.OUT conține, pe prima linie mesajul IMPOSIBIL, sau, în cazul în care un asemenea traseu există, va conține:

L

xM yM xm ym

unde:

- L este număr real cu 2 zecimale (obținut prin rotunjire) și reprezintă lungimea traseului pe hartă;

- xM yM sunt coordonatele punctului de cotă maximă;

- xm ym sunt coordonatele punctului de cotă minimă.

Exemplu

COTE.IN COTE.OUT

4 4 3.61

1 2 2 2 3 4 1 1

2 2 3 3

3 3 3 4

2 3 2 2

BARAJ

P059919: Expoziție

Lect. univ. Clara Ionescu, Universitatea "Babeș Bolyai", Cluj

Într-o sală de expoziție se vor expune aparate de tehnică de calcul (se cunosc coordonatele lor în plan). În punctul de coordonate (0,0) se află o sursă de curent. Pentru alimentarea aparatelor, acestea vor fi legate cu cablu direct la sursa de curent, sau la aparate deja alimentate (direct sau indirect). Lungimea unui cablu este egală cu distanța în linie dreaptă între punctele pe care le conectează.

Organizatorii au inițiat un concurs pentru a stabili lungimea totală minimă a cablului necesar pentru alimentarea aparatelor. Se vor acorda trei premii pentru primele trei soluții diferite, în ordinea crescătoare a lungimii cablurilor. Trebuie respectate următoarele cerințe:

1) toate aparatele trebuie alimentate;

2) două soluții sunt considerate diferite dacă una dintre ele conține cel puțin două aparate conectate direct care în cealaltă soluție nu sunt conectate direct.

Date de intrare

Datele de intrare se citesc din fișierul de tip text EXPO.IN. Fișierul are următoarea structură:

Pe prima linie este scris numărul întreg n (3ŁnŁ50), reprezentând numărul aparatelor care necesită alimentare.

Pe următoarele n linii sunt scrise perechi de numere reale reprezentând coordonatele aparatelor amplasate în interiorul sălii:

x1 y1 // coordonatele aparatului 1

x2 y2 // coordonatele aparatului 2

...

xn yn // coordonatele aparatului n

Sursa de energie este considerată "aparatul" având numărul de ordine 0.

Date de ieșire

Rezultatele se vor scrie în fișierul EXPO.OUT.

Cele trei soluții de alimentare a aparatelor vor forma trei seturi de date, separate prin câte o linie vidă.

Un set este format din mai multe linii, unde pe o linie se specifică aparatele legate printr-un cablu având lungimea egală cu distanța dintre cele două aparate. Un aparat se identifică prin numărul său de ordine. Numerele de pe aceeași linie se vor separa printr-un singur spațiu. În cadrul unui set ordinea perechilor de numere este oarecare. De asemenea, nu contează ordinea în care sunt scrise numerele într-o pereche.

Exemplu

EXPO.IN EXPO.OUT

3 0 2

2.2 2.2 1 2

1.1 1.1 1 3

3.3 3.3

0 1

1 2

1 3

0 1

2 0

1 3

P059920: Camere luminate

Valentin Gheorghiță, student, Universitatea Politehnică, București

Într-o vilă sunt n camere (1ŁnŁ11) numerotate cu numere de la 1 la n, fiecare fiind luminate cu ajutorul unui singur bec. Pentru fiecare cameră k (1ŁkŁn) se cunoaște numărul camerelor vecine (nrk) precum și care sunt aceste camere. Două camere sunt vecine, dacă se poate trece din una în cealaltă direct.

În fiecare cameră k (1ŁkŁn) din vilă se găsesc două grupuri de întrerupătoare:

- un grup format din nr1k întrerupătoare pentru aprinderea luminilor în anumite camere;

- un grup format din nr2k întrerupătoare pentru stingerea luminilor în anumite camere.

Proprietarul vilei se întoarce seara târziu acasă și observă că singura cameră luminată este camera 1. El intră în casă numai prin camera 1 și dorește să ajungă în camera n, care este dormitorul său. Superstițios, el nu va intra niciodată într-o cameră neluminată, dar ajuns în final, în dormitor nu va putea dormi liniștit dacă în oricare din celelalte camere, în afara dormitorului, lumina este aprinsă.

Durata unui drum dintre camera 1 și dormitor este egală cu suma dintre numărul de deplasări dintr-o cameră în alta și numărul total de aprinderi și stingeri ale luminii, începând cu momentul în care proprietarul se află în camera 1

și până ajunge în dormitor.

Deoarece seara când vine acasă este foarte obosit, el dorește să determine un drum de durată minimă de la camera 1 la dormitor (camera n) astfel încât el să poată dormi liniștit. Prin orice cameră (inclusiv prin dormitor) se poate trece de mai multe ori.

Date de intrare

Fișierul VILA.IN are următorul format:

n

nr1 vec1[1] vec1[2] ... vec1[nr1]

nr2 vec2[1] vec2[2] ... vec2[nr2]

...

nrn vecn[1] vecn[2] ... vecn[nrn]

nr11 ap1[1] ap1[2] ... ap1[nr11]

nr12 ap2[1] ap2[2] ... ap2[nr12]

...

nr1n apn[1] apn[2] ... apn[nr1n]

nr21 st1[1] st1[2] ... st1[nr21]

nr22 st2[1] st2[2] ... st2[nr22]

...

nr2n stn[1] stn[2] ... stn[nr1n]

- n reprezintă numărul camerelor din vilă;

- nrk reprezintă numărul camerelor vecine cu camera k;

- veck[j] reprezintă cea de a j-a cameră vecină cu camera k;

- nr1k reprezintă numărul întrerupătoarelor din camera k care aprind lumini;

- apk[j] reprezintă cea de a j-a cameră în care se aprinde lumina din camera k;

- nr2k reprezintă numărul întrerupătoarelor din camera k care sting lumini;

- stk[j] reprezintă cea de a j-a cameră în care se stinge lumina din camera k.

Date de ieșire

Rezultatele se vor scrie în fișierul text VILA.OUT în următorul format:

dmin

ch1 cam1

ch2 cam2

...

chdmin camdmin

unde:

- dmin reprezintă durata minimă a drumului determinat;

- chk este unul din următoarele caractere:

‘a' dacă se aprinde becul în camera camk,

‘s' dacă se stinge becul în camera camk,

‘m' dacă se trece în camera camk;

- camk reprezintă numărul camerei în care se execută operația chk.

Numerele situate pe aceeași linie sunt separate printr-un singur spațiu atât în fișierul de intrare cât și în fișierul de ieșire.

În cazul în care nu există soluție, în fișierul de ieșire se va scrie: 'Nu exista solutie'.

Exemplu

VILA.IN VILA.OUT

3 6

2 2 3 a 2

2 1 3 m 2

2 1 2 a 3

1 2 m 3

1 3 s 1

0 s 2

0

1 3

2 1 2

P059921: Perechi

Prof. Marinel Șerban, Liceul de Informatică "Grigore Moisil", Iași

Se consideră șirul numerelor naturale prime:

2, 3, 5, 7, 11, 13, 17,...

Din acesta se construiește un al doilea șir astfel: fiecare număr prim de pe o poziție impară se concatenează cu numărul prim următor. Se obține șirul:

23, 57, 1113,...

Apoi, din acest șir se formează un al treilea șir care conține doar numerele prime:

23, 3137,...

Scrieți un program care pentru un număr oarecare n (50ŁnŁ200), citit de pe prima linie a fișierului text PERECHI.IN, furnizează al n-lea număr din acest al treilea șir, număr care va fi scris pe prima linie a fișierului text PERECHI.OUT.

Exemple

PERECHI.IN PERECHI.OUT

1 23

PERECHI.IN PERECHI.OUT

2 3137

P059922: Legenda

Cătălin Frâncu, student, Universitatea Politehnică, București

Printre concurenții Olimpiadei de Informatică circulă următoarea legendă. În timpul Turnirului Interfeudal de Informatică din anul 1299, infama vrăjitoare Exponentia, orbită de gelozie, l-a blestemat pe viteazul cavaler Algoritmus, a cărui inimă era dăruită prea nobilei Polinomia, cu următorul blestem (exprimat în cuvinte mieroase și perfide):

"O, preanobile Algoritmus! Iată aici NŁ100 suluri de papirus de diverse lungimi S1, S2,..., SN. Lungimea fiecărui papirus este un număr întreg de țoli, cel puțin unul și cel mult o sută de țoli. Pe fiecare țol al acestor papirusuri este gravat un număr cuprins între 1 și 100. Întrucât cunoști disprețul meu pentru numerele cu soț, vei ști, neînfricate cavaler, că suma lungimilor papirusurilor este un număr fără soț. Mai înainte ca Polinomia, pe care o iubești, să fie a ta, Algoritmus, îți cer să lipești aceste papirusuri cap la cap într-o asemenea ordine, încât numărul situat la jumătatea papirusului rezultat să fie cât mai mare cu putință. Să nu cutezi însă a rupe papirusurile ori a le întoarce cu josul în sus, căci Polinomia va fi pierdută pe veci."

Sărmanul Algoritmus, neavând altceva de făcut, s-a apucat cu răbdare să încerce fel de fel de modalități de a așeza papirusurile, și se spune că asta face și astăzi, cufundându-se pe niveluri din ce în ce mai adânci în mrejele vrăjitoarei Exponentia. Între timp anii au trecut, papirusurile s-au cam ferfenițit, frumusețea Polinomiei s-a cam dus și există zvonuri că s-ar fi măritat. Legenda spune însă că "Vrăjitoarea poate fi nimicită, iar cavalerul salvat, numai de un program scris în cetatea Mediașului, care să dezlege misterul în nu mai mult de două secunde. Autorul acestui program va avea mult de agonisit". Nu știm cât, dar credem legenda pe cuvânt.

Pentru comoditatea voastră, am cules informații despre mărimile și conținutul papirusurilor în fișierul text PAPIRUS.IN, care are formatul:

N

S1 X(1,1) X(1,2) ... X(1,S1)

S2 X(2,1) X(2,2) ... X(2,S2)

...........................

SN X(N,1) X(N,2) ... X(N,SN)

În acest fișier, N este numărul de papirusuri, Si este lungimea celui de-al i-lea papirus, iar X(i,j) este valoarea celui de-al j-lea număr de pe al i-lea papirus.

Răspunsul trebuie să-l dați în fișierul PAPIRUS.OUT, indicând numerele papirusurilor în ordinea în care trebuie ele lipite pentru a obține un element cât mai mare în mijlocul papirusului rezultat. Numerele se vor tipări în formatul:

P1 P2 ... PN, unde 1ŁPiŁN "i și PičPj "ičj

Exemplu

PAPIRUS.IN PAPIRUS.OUT

4 3 2 1 4

5 4 7 3 1 9

3 2 5 8

7 6 4 3 9 5 2 6

4 4 1 3 8

Interpretarea este: dacă lipim, în această ordine, papirusurile 3, 2, 1 și 4, obținem papirusul (6, 4, 3, 9, 5, 2, 6, 2, 5, 8, 4, 7, 3, 1, 9, 4, 1, 3, 8). Acesta conține în mijloc elementul 8, și nu putem să aranjăm altcumva papirusurile pentru a obține în mijloc un element mai mare.

Dacă există mai multe soluții, se va tipări una la alegere. Mult succes, prințese și cavaleri!

P059923: Un dreptunghi

Prof. Rodica Pintea, Liceul "Grigore Moisil", București și Iuliu Vasilescu, student, Universitatea Politehnică, București

Se consideră o tablă pe care sunt desenate MŽN (1ŁN, MŁ20000) pătrate. Pe această tablă este plasat, la coordonate necunoscute un dreptunghi de dimensiuni, de asemenea necunoscute. Pentru aflarea poziției și a dimensiunilor dreptunghiului Alinuța aruncă bile de la marginile tablei în lungul liniilor sau coloanelor. Dacă bila izbește dreptunghiul, se întoarce, în caz contrar trece mai departe. Alinuța ne comunică rezultatele aruncărilor, falsificând unele dintre ele. Să se determine poziția și dimensiunile dreptunghiului astfel încât numărul de rezultate falsificate să fie minim. Dacă există mai multe soluții posibile, determinați-o pe cea pentru care aria dreptunghiului este maximă.

Observații:

- bila se poate arunca de mai multe ori pe aceeași linie sau coloană (eventual unele rezultate fiind falsificate);

- dimensiunile dreptunghiului pot fi și 0 (dreptunghiul poate fi un segment sau un punct). Un segment oprește doar bilele care vin perpendicular pe el, iar un punct nu oprește bile.

Date de intrare

Formatul fișierului de intrare DREPT.IN:

- pe prima linie sunt scrise două numere naturale M și N, reprezentând numărul de linii, respectiv numărul de coloane ale tablei;

- pe cea de a doua linie este scris un număr natural Q, (1ŁQ Ł20000) reprezentând numărul de aruncări pe linii;

- pe următoarele Q linii sunt perechi de numere naturale:

L1 R1

L2 R2

...

Lq Rq

unde linia Li Ri are semnificația: aruncarea pe linia Li are rezultatul Ri (valoarea 0 semnifică faptul că bila a trecut, valoarea 1 semnifică faptul că bila s-a întors).

Pe următoarea linie avem un număr natural P, reprezentând numărul de aruncări pe coloane (1ŁPŁ20000).

Pe următoarele P linii sunt perechi de numere naturale:

C1 S1

C2 R2

...

Cp Sp

unde linia Ci Si are semnificația: aruncarea pe coloana Ci are rezultatul Si (valoarea 0 semnifică faptul că bila a trecut, valoarea 1 semnifică faptul că bila s-a întors).

Date de ieșire

Fișierul de ieșire DREPT.OUT va conține patru numere naturale: L C H W, unde L, C reprezintă linia și coloana colțului stânga jos al dreptunghiului determinat (pătratul 1, 1 este colțul stânga jos al tablei) iar H, W reprezintă înălțimea și lățimea dreptunghiului.

Exemplu:

DREPT.IN DREPT.OUT

4 5 2 1 1 4

3

4 0

1 0

5 0

Figura de mai jos corespunde exemplului:

P059924: Submulțimi

Prof. Ovidiu Domșa, Colegiul "Horea, Cloșca și Crișan", Alba Iulia

Se dă o mulțime cu m elemente numere naturale strict pozitive, a căror sumă este mai mică decât 400000.

Să se determine două submulțimi disjuncte ale mulțimii date având proprietatea că suma elementelor unei mulțimi este egală cu suma elementelor celei de a doua.

Date de intrare

Datele de intrare se citesc din fișierul de tip text SUB.IN. Fișierul are următoarea structură:

Pe prima linie este scris numărul întreg m (3ŁmŁ30), reprezentând numărul elementelor mulțimii.

Pe următoarea linie sunt scrise elementele mulțimii, m numere naturale pozitive diferite, separate printr-un spațiu.

Date de ieșire

Rezultatele se vor scrie în fișierul SUB.OUT.

- pe prima linie se va afla numărul elementelor unei submulțimi;

- pe a doua linie se vor scrie elementele primei submulțimi separate printr-un spațiu;

- pe a treia linie se scrie numărul elementelor celei de a doua submulțimi;

- pe a patra linie vor fi scrise elementele celei de a doua submulțimi separate printr-un spațiu.

Dacă nu există soluție fișierul va conține pe prima linie caracterele NU.

Exemplu

SUB.IN

7

1 10 4 17 124354 25 124330

SUB.OUT

4

1 10 17 124330

2

4 124354

Premii

[cuprins]