Lista de probleme 5

Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

În timpul acţiunii “Furtuna în deşert” din cauza unei furtuni de nisip, n soldaţi s-au rătăcit de plutoanele lor. După trecerea furtunii se pune problema regrupării acestora pe plutoane. Pentru aceasta se folosesc plăcuţele de identificare pe care soldaţii le poartă la gât. Pe aceste plăcuţe sunt scrise numere care pot identifica fiecare soldat şi plutonul din care acesta face parte. Astfel, soldaţii din acelaşi pluton au numărul de identificare format din aceleaşi cifre, dispuse în altă ordine şi numerele de identificare sunt unice. De exemplu, numerele de identificare 78003433, 83043073, 33347008 indică faptul ca cei trei soldaţi care le poartă fac parte din acelaşi pluton.

Fiind date cele n numere de pe plăcuţele de identificare, să se regrupeze cei n soldaţi pe plutoane, indicându-se numărul de plutoane găsite (un pluton refăcut trebuie să aibă minimum un soldat), numărul de soldaţi din cel mai numeros pluton, numărul de plutoane care au acest număr maxim de soldaţi precum şi componenţa unui astfel de pluton (cu număr maxim de soldaţi regrupaţi).

Fermierul Ion deţine un teren de formă pătrată, împărţit în NxN pătrate de latură unitate, pe care cultivă cartofi. Pentru recoltarea cartofilor fermierul foloseşte un robot special proiectat în acest scop. Robotul porneşte din pătratul din stânga sus, de coordonate (1,1) şi trebuie să ajungă în pătratul din dreapta jos, de coordonate (N, N). Traseul robotului este programat prin memorarea unor comenzi pe o cartelă magnetică. Fiecare comandă specifică direcţia de deplasare (sud sau est) şi numărul de pătrate pe care le parcurge în direcţia respectivă. Robotul strânge recolta doar din pătratele în care se opreşte între două comenzi.

Din păcate, cartela pe care se află programul s-a deteriorat şi unitatea de citire a robotului nu mai poate distinge direcţia de deplasare, ci numai numărul de paşi pe care trebuie să-i facă robotul la fiecare comandă. Fermierul Ion trebuie să introducă manual, pentru fiecare comandă, direcţia de deplasare.

Scrieţi un program care să determine cantitatea maximă de cartofi pe care o poate culege robotul, în ipoteza în care Ion specifică manual, pentru fiecare comandă, direcţia urmată de robot. Se va determina şi traseul pe care se obţine la recolta maximă.

Să considerăm ecuaţii de gradul I, de forma: expresie_1=expresie_2. Expresiile specificate sunt constituite dintr-o succesiune de operanzi, între care există semnul + sau semnul - (cu semnificaţia binecunoscută de adunare, respectiv scădere). Fiecare operand este fie un număr natural, fie un număr natural urmat de litera x (litera x reprezentând necunoscuta), fie doar litera x (ceea ce este echivalent cu 1x).

De exemplu: 2x-5+10x+4=20-x. Observaţi că în ecuaţiile noastre nu apar paranteze şi necunoscuta este întotdeauna desemnată de litera mică x.

Scrieţi un program care să rezolve ecuaţii de gradul I, în formatul specificat în enunţul problemei.

Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului. Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1, 2, …, N și două vârfuri ale sale notate X și Y (1 ≤ X, Y ≤ N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.