PROBLEME propuse pentru rezolvare

P039801: În fabrica de mobilă

Într-o fabrică se confecţionează din plăci dreptunghiulare, piese de mobilier, de asemenea dreptunghiulare, de diferite dimensiuni.

Maşina care decupează aceste piese impune următoarele restricţii:

- o tăietură realizată într-o placă trebuie să o separe pe aceasta în două plăci (trebuie să treacă dintr-o parte în alta, drept, fără a roti cuţitul);

- prin tăiere se pierde din placă o bucată de dimensiune D.

Despre fiecare piesă solicitată se ştie dacă se pot roti (sau nu) cu 90° în scopul confecţionării din placa existentă. Rotirea necesită repoziţionări ale cuţitului maşinii.

Să se determine modalitatea de dispunere a pieselor solicitate pe plăcile existente, astfel încât materialul pierdut cât şi numărul de repoziţionări ale cuţitului să fie minime.

Date de intrare:

Pe prima linie a fişierului de intrare PLACI.IN sunt date dimensiunile plăcilor existente (lăţime şi lungime, numere naturale <=1 şi <=1000), numărul lor fiind infinit şi toate plăcile fiind de aceeaşi dimensiune.

Pe linia a doua este scrisă valoarea lui D (număr natural, 1<=D<=5).

Pe următoarele linii sunt scrise date referitoare la tipurile de piese solicitate, despărţite printr-un spaţiu:

nr latime lungime caracter

unde:

- nr este un număr natural care reprezintă numărul de piese solicitate de acelaşi tip (1<=nr<=200);

- latime şi lungime precizează dimensiunile piesei solicitate (numere naturale, 1<=latime,lungime<=1000);

- caracter este fie 'r' fie 'n'; prin ele se precizează dacă o piesă poate fi (sau nu) rotită cu 90° la aranjarea pe placă.

Date de ieşire:

Rezultatele se vor scrie în fişierul de ieşire PLACI.OUT astfel:

pierdere // reprezintă suprafaţa totală a materialului pierdut din plăcile folosite (total D şi material din care nu se poate confecţiona nici o piesă solicitată);

nr_rotiri // numărul de repoziţionări ale cuţitului;

placa x // cuvântul 'placa', un spaţiu, apoi x = numărul de ordine al plăcii;

piesa st sus caracter // unde piesa este numărul de ordine al piesei, st şi sus sunt coordonatele poziţiei piesei pe placă (originea =0,0 se consideră a fi în colţul din stânga sus al plăcii);

// caracter este 'r' sau 'n' în funcţie de posibilităţile de rotire.

P039802: Cămile

O caravană cu n (n<=30) cămile înaintează în deşert în şir indian. După prima zi de mers apare un conflict între fiecare cămilă şi cea din faţa sa (între a doua şi prima, între a treia şi a doua etc).

Conducătorul caravanei va trebui ca a doua zi, datorită conflictelor, să schimbe ordinea cămilelor în caravană. Să se găsească numărul de posibilităţi pe care le are conducătorul caravanei.

Date de intrare:

Din fişierul CAMILE.IN se va citi numărul natural n al cămilelor.

Date de ieşire:

Rezultatul se va scrie în fişierul CAMILE.OUT.

Exemplu:

CAMILE.IN CAMILE.OUT

3 3

P039803: HDTV (High Definition TeleVision)

La televiziunea HDTV se utilizează mai multe modalităţi de comprimare a imaginilor în scopul eliminării informaţiilor redundante, astfel reducând cantitatea de informaţii care urmează să fie transmisă. Să se simuleze decomprimarea în scopul reconstruirii imaginilor de televiziune. Pentru simplificare, imaginile sunt reprezentate prin tablouri dreptunghiulare de pixeli având originea (0,0) în colţul din stânga jos. Fiecare pixel poate avea ca valoare una din cele 26 de litere ale alfabetului englez de la 'A' la 'Z'.

Date de intrare:

Sistemul de comenzi preia o literă mică urmată de lista parametrilor care reprezintă comanda. Anumiţi parametri definesc blocuri dreptunghiulare din imagine. În listele de comenzi de mai jos, blocul (x,y,w,h) reprezintă un bloc dreptunghiular având colţul din stânga jos în punctul de coordonate (x,y) şi colţul din dreapta sus în punctul de coordonate (x+w-1,y+h-1). Aceste comenzi şi parametrii lor sunt:

i x y

Efect:

Se iniţializează o imagine nouă având lăţimea de x pixeli şi înălţimea de y pixeli. Imaginea conţine cel mult 10000 pixeli care sunt iniţializaţi cu litera 'A'. Ultima comandă în fişierul de intrare este o comandă similară care indică o imagine având dimensiunea 0.

f x y w h c

Efect:

Se umple blocul (x,y,w,h) cu caracterul c, unde c este o majusculă.

c x y w h a b

Efect:

Se copiază un bloc (x,y,w,h) în blocul (a,b,w,h). Aceste blocuri se pot suprapune.

r x y w h data

Efect:

Se citesc valorile elementelor cu care se va încărca blocul (x,y,w,h) din lista de date data. Blocul este umplut linie după linie începând cu pixelul (x,y). Datele sunt w´h majuscule.

d x y w h data

Efect:

Se decomprimă datele dintr-un bloc (x,y,w,h) în mod similar comenzii r. Datele sunt memorate într-un format codificat, alcătuit din perechi de număr-literă, unde număr precizează numărul de apariţii al literei literă.

Exemplu:

3A1B10C corespunde şirului decomprimat AAABCCCCCCCCCC.

Observaţii:

- Comenzile şi parametrii lor pot conţine spaţii şi tabulatoare şi pot fi continuate pe mai multe linii.

- Un număr nu va fi rupt în cifre niciodată.

- Parametrii sunt numere pozitive şi sunt de aşa natură încât orice bloc specificat se află în interiorul imaginii.

- În cazul comenzilor r şi d, conţinutul parametrului data respectă dimensiunile blocului.

Din fişierul de intrare TV.IN se va citi o listă de comenzi.

Date de ieşire:

De fiecare dată când se întâlneşte o comandă i, unitatea de control va calcula un număr de verificare pentru imaginea existentă, apoi se va iniţializa o imagine nouă. Numărul de verificare este suma modulo 256 a codurilor ASCII ale caracterelor corespunzătoare pixelilor din imagine, luate linie după linie în forma:

nr_de_verificare = 127

cu un singur spaţiu în faţa şi după semnul '='.

Nici un număr de verificare nu se va calcula şi scrie pentru prima comandă i, deoarece nu există nici o imagine în acest moment.

Următoarele diagrame prezintă forma imaginilor corespunzătoare conţinutului fişierelor TV.IN şi TV.OUT.

AAAAUGHAAA LOVE

BBBBLEAAAA LONE

BBBBLLLAAA LATE

AA AAAABLLAAA HATE

Exemplu:

TV.IN

i2 1i 10 4f 0 1 6 2 Bd4 0 3

4 1B6L1E1A

1U1G1H i 4 5 r 0 4 4 1 L OVE c 0 4 4

1 0 3 f 2 3 1 1 N

c 0 3 4 1 0 2 f 1 2 1 1 A c 0 2 4

1 0 1 r 2 1 1 1 T

c 0 1 4 1 0 0 f 0 0 1 1 Hi 0 0

TV.OUT

nr_de_verificare = 130

nr_de_verificare = 152

nr_de_verificare = 204

P039804: Inteligenţă artificială simbolică

Trebuie să scrii un program simplu de inteligenţă artificială simbolică. Acestuia i se vor furniza anumite informaţii şi i se vor pune întrebări. Programul de inteligenţă artificială trebuie să răspundă la întrebări. Din fericire aceste informaţii şi întrebări se referă numai la anumiţi indivizi care sunt grupaţi (pentru grupare se folosesc substantive colective) care efectuează acţiuni (pentru gruparea acţiunilor se folosesc verbe).

Gramatica folosită este foarte simplă: se folosesc două tipuri de propoziţii şi un singur tip de întrebare. Toate substantivele la plural sunt marcate printr-un caracter 's'.

Date de intrare:

Fiecare şir din datele de intrare conţine fie o singură propoziţie, fie un spaţiu. Sfârşitul fişierului este marcat de o linie a cărui conţinut este caracterul '#'. Fiecare propoziţie are una din următoarele forme:

- 'as v bs.', unde a şi b sunt substantive şi v este un verb. Aceasta înseamnă că tot ce este de tip a realizează acţiunea v asupra a tot ce este de tip b.

- 'a is a b.', unde a şi b sunt substantive. Aceasta înseamnă că individul a este de tip b.

- întrebarea are forma: 'does a v b?', unde a şi b sunt substantive, iar v este verb. Se pune întrebarea: individul a face acţiunea v asupra individului b?

Lungimea maximă a şirurilor este de 80 litere. Cuvintele conţin cel mult 40 de litere şi pot fi formate din majuscule şi litere mici, deşi în timpul căutării litera mică nu se deosebeşte de majusculă. Pot exista mai multe spaţii între cuvinte, dar niciodată între cuvinte şi semnele de punctuaţie de la sfârşitul propoziţiilor. Numărul maxim de informaţii dintr-un fişier de intrare este 100.

Date de ieşire:

Pentru fiecare întrebare din fişierul de intrare se va afişa o singură linie, având conţinutul: 'YES.' în cazul în care din informaţiile anterioare se poate decide că răspunsul la întrebare este adevărat şi 'NO.' în caz contrar.

Exemplu:

AI.IN AI.OUT

Dogs chase cats. YES.

Sheeps ignore glasss. NO.

Fido is a dog.

Fluffles is a cat.

Does Fido chase Fluffles?

Does Fluffles chase Fido?

P039805: Potrivire de cuvinte

Ca agent al serviciilor secrete, ai sub supraveghere traficul corespondenţei pe poşta electronică, căutând coduri care ar putea să indice acţiuni subversive. Totuşi, anumite elemente subversive ale societăţii au început să amestece literele din unele cuvinte din mesajele lor cu scopul de a le face de neînţeles. Tu, familiarizat cu asemenea trucuri, te decizi să scrii un program care să caute propoziţii având cuvinte ale căror litere au fost amestecate.

Date de intrare:

Datele de intrare din fişierul AI.IN conţin perechi formate din liste de cuvinte şi propoziţii. Lista de cuvinte conţine cuvintele care trebuie căutate în propoziţia următoare. Toate literele din datele de intrare sunt litere mici. Cuvintele pot fi formate din cel mult 20 de litere şi sunt separate printr-un spaţiu. Lungimea maximă a fiecărei linii este de 80 de caractere. Fiecare listă este scrisă pe o singură linie şi conţine cel mult 20 de cuvinte. Propoziţiile se pot continua pe mai multe linii şi se termină cu caracterul '.'.

Fişierul se termină cu o listă care conţine caracterul '#'.

Date de ieşire:

Pentru fiecare pereche de listă de cuvinte şi propoziţie, să se găsească cuvintele din listă care apar în propoziţii (având caracterele amestecate sau nu). În fişiereul AI.OUT se vor afişa aceste cuvinte în ordinea în care apar în listă, separate printr-un spaţiu. Dacă nici un cuvânt din listă nu se potriveşte cu vreun cuvânt din propoziţie, se va afişa o linie vidă.

Exemplu:

CUVINTE.IN

bomb

we twan ot ombb mericaa.

guns mines missiles

aameric ssell snug

dan iimsssle ot sit neeemis.

cat sat mat

cat sat tam mat.

#

CUVINTE.OUT

bomb

guns missiles

cat sat mat

P039806: Sfârşitul lumii

Unui profet i s-a spus că sfârşitul lumii poate fi cândva între 01994 şi 99999 inclusiv. I s-au dat diferite indicaţii privind data posibilă, prezentate sub forma:

"Cifra zecilor este de trei ori mai mare decât cifra sutelor, plus şase".

Profetul a interpretat această indicaţie sub forma: 'd=3c+6;'

(e este cifra zecilor de mii, d este cifra miilor, c este cifra sutelor, b este cifra zecilor, a este cifra unităţilor numărului care reprezintă un an).

Să se scrie un program care citeşte un set de indicaţii care pot avea una din formele:

<v> = propoziţie +/- propoziţie, sau

unde:

propoziţie poate fi:

k<v> sau

<v> sau

k

unde:

<v> este o variabilă (a, b, c, d, sau e);

k este o constantă având valoarea între 0 şi 9.

Date de intrare:

Fiecare linie din fişierul de intrare LUMEA.IN conţine un set de indicaţii diferite. Sunt cel mult 5 indicaţii în fiecare set. Să se afîşeze, pentru fiecare set, prima dată după 1993 care poate fi un an care să reprezinte sfârşitul lumii (nu contrazice nici una din indicaţii), sau mesajul 'Suntem salvati!', dacă rezultă că nici o dată până la 100000 nu ar fi data probabilă a sfârşitului lumii (de asemenea, această concluzie nu contrazice nici una din indicaţiile setului).

Toate calculele sunt realizate modulo 10. Fişierul de intrare se termină printr-o linie care conţine caracterul '#'.

Exemplu:

LUMEA.IN

a=2;b=4;e=9+a;

d=3;

c=e+e;d=4;c=d+e;

e=e+1;

c=2d+4;e=4-2c;a=4d+5;d=3;b=a-e;

#

LUMEA.OUT

10042

03000

44800

Suntem salvati!

43037

P039807: Prelucrare de texte

Să se scrie un procesor de texte care va prelucra şiruri de caractere (string-uri). Va citi o singură linie a textului, urmată de o linie de comenzi care va modifica şirul. Programul trebuie să producă la ieşire o linie a textului prelucrat.

Comenzile sunt următoarele:

0 - mută cursorul la începutul liniei;

$ - mută cursorul în poziţia următoare ultimului caracter (în dreptul caracterului de sfârşit de linie);

x - şterge caracterul din dreptul cursorului dacă nu este la sfârşitul liniei;

s - înlocuieşte caracterul din dreptul cursorului cu caracterul din dreapta acestuia, cât timp cursorul nu este în faţa caracterului sfârşit de linie sau în dreptul acestuia;

i x - inserează caracterul x pe poziţia cursorului, şi mută cursorul cu un caracter;

u - schimbă litera mică în majusculă şi mută cursorul cu un caracter;

+ - mută cursorul cu un caracter la dreapta;

- - mută cursorul cu un caracter la stânga.

Cursorul poate fi poziţionat în dreptul primului caracter, sau în dreptul oricăruia din faţa caracterului de sfârşit de linie.

Comenzile din fişierul de intrare TEXTE.IN sunt scrise pe o linie, după care, pe o linie nouă urmează textul care nu conţine spaţii. Linia în care s-a scris textul nu conţine (în interiorul textului) caracterul de sfârşit de linie. Cursorul porneşte de la primul caracter al fiecărui text. Fişierul se termină cu o linie text care conţine un singur caracter: '#'.

Exemplu:

TEXTE.IN

Hello, I am a frog.

$-----xxxxipieirisioin

Needle nardle noo.

+++xizuu+++xxips

#

TEXTE.OUT

Hello, I am a person.

NeezLE napel noo.

P039808: Trupa de comando

Se consideră o hartă pe care sunt desenate n ţări. Suprafaţa fiecărei ţări este colorată într-o singură culoare.

O trupă de comando porneşte dintr-o ţară dată x şi trebuie să ajungă într-o altă ţară dată y. Pe parcursul traversării oricărei ţări, membrii trupei trebuie să se îmbrace în echipament de camuflaj având culoarea de pe hartă a ţării traversate. Determinaţi drumul trupei de comando astfel încât ei să aibe nevoie de un număr minim de echipamente.

Date de intrare:

Fişierul de intrare INPUT.TXT are următoarea structură:

- pe prima linie se află un număr întreg n (2<=n<=100), reprezentând numărul de ţări de pe hartă;

- fiecare dintre următoarele n linii conţine un string care are structura:

nume_i culoare_i vecin₁ vecin₂ ... vecink

unde:

- nume_i reprezintă numele unei ţări (string);

- culoare_i reprezintă culoarea (string) ataşată ţării având numele nume_i;

- vecin₁ vecin₂ ... vecin_k (0<=k<=n) reprezintă numele ţărilor vecine cu ţara nume_i;

- şirurile de caractere corespunzătoare numelor, respectiv culorii sunt separate prin câte un spaţiu;

- pe următoarea linie sunt date două nume (stringuri): ţara din care porneşte expediţia şi ţara în care trebuie să ajungă.

Se presupune că datele sunt corecte.

Date de ieşire:

Fişierul de ieşire OUTPUT.TXT are următoarea structură:

- pe prima linie se va scrie un număr întreg m (1<=m<=n) reprezentând numărul de echipamente necesare trupei pentru a realiza expediţia respectând cerinţele problemei;

- pe următoarele m linii se va descrie drumul trupei, specificând pe fiecare linie numele unei ţări prin care va trece trupa.

În cazul în care există mai multe soluţii, se va specifica cea care trece printr-un număr minim de ţări.

Exemplu:

INPUT.TXT:

6

Romania rosu Bulgaria Ungaria Yugoslavia

Bulgaria verde Romania Yugoslavia

Ungaria galben Romania Yugoslavia Croatia

Yugoslavia alb Romania Ungaria Croatia

Croatia rosu Ungaria Yugoslavia Italia

Italia galben Croatia

Romania Italia

OUPUT.TXT:

2

Romania

Ungaria

Croatia

Italia