Lista de probleme 77

Misiunea robotului Curiosity este de-a trimite imagini și informații către satelitul plasat pe orbita planetei Marte. Zona de explorare a robotului este de-a lungul unei axe de coordonate Ox. Robotul este înzestrat cu o baterie solară de capacitate energetică maximă C și consumă pentru fiecare unitate de drum parcurs o unitate de energie. Coordonata punctului de plecare al incursiunii robotului (raportată la origine x=0) este Xs, iar punctul unde este finalizat studiul are coordonata Xf.
Totodată, cercetătorii au stabilit N puncte ce fac posibilă încărcarea bateriilor robotului, numerotate de la 1 la N. În funcție de intensitatea luminii solare primite, reflectată în durata de încărcare a bateriei, punctele de încărcare sunt de trei tipuri: tipul 1–intensitate minimă/timp de încărcare mare, tipul 2–intensitate medie/timp de încărcare mediu, tipul 3–intensitate maximă/timp de încărcare scurt. Altfel, fiecare punct de încărcare i este descris prin perechea t[i] x[i], adică tipul de încărcare, respectiv poziția acestuia pe axă. În orice punct de încărcare robotul poate decide dacă încarcă sau nu bateria, cu unități de energie, nu mai mult decât capacitatea maximă. Robotul se poate deplasa dintr-un punct atât în stânga cât și în dreapta pe axă.
Pentru a scurta durata parcurgerii distanței către punctul final se dorește determinarea unei strategi optime a opririlor pentru încărcarea bateriilor, astfel încât cantitatea totală de energie încărcată în puncte de tipul 1 să fie minimă. În cazul în care sunt mai multe strategii de oprire pentru care cantitatea totală de energie încărcată în puncte de tipul 1 este minimă, atunci se va alege strategia pentru care cantitatea totală de energie încărcată în puncte de tipul 2 să fie minimă.

Dacă se cunosc Xs, Xf, C, precum și descrierea celor N puncte de încărcare să se determine o strategie de deplasare între coordonatele Xs și Xf, optimă din punct de vedere al timpului necesar încărcării bateriilor.

Sufle este un personaj cu urechi ascuțite, îndrăgostit de algoritmică. El are o antipatie profundă față de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap. Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:

Pentru oricare două numere naturale se definește următoarea operație:

• se consideră reprezentările în baza 2 pentru cele două numere;
• se alege o poziție în reprezentarea binară a primului număr;
• se schimbă cifra situată pe acea poziție în primul număr cu cifra aflată pe exact aceeași
  poziție în al doilea număr. (Observați cum Aisimok, obsedat de matematică, nu a folosit termenul bit, tocmai pentru a-l irita pe Sufle.)

Pentru un șir oarecare de numere naturale, se poate aplica de oricâte ori și asupra oricăror două numere operația descrisă mai sus. Scopul final este ca suma pătratelor numerelor din șir să ajungă la valoarea minim posibilă. Denumim costul șirului acestă valoare minimă.

Pentru a deveni și mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvențe ale unui șir dat. Costul unei subsecvențe este egal cu costul șirului definitit de subsecvența dată.

Cerința: Pentru un șir cunoscut și pentru mai multe subsecvențe date să se calculeze suma minimă a pătratelor numerelor din subsecvență după aplicare a operației descrise, de oricâte ori se consideră necesar și asupra oricăror numere din subsecvență.

Clasa din care faceţi parte merge în excursie! Principalul obiectiv este Lacul Roşu, o locaţie deosebit de frumoasă. Pentru a vă bucura cât mai mult de peisaj toţi elevii se vor plimba cu barca pe lac. Bărcile sunt de maxim două persoane şi au restricţiile următoare:

• greutatea totală suportată de o barcă este C;
• dacă în barcă se aşază două persoane, atunci diferența în modul dintre greutățile acestora trebuie să fie maxim B, în caz contrar barca nu este balansată și riscă să se răstoarne.

Dacă o singură persoană se aşază în barcă, nu se aplică restricția a doua. Care este numărul minim de bărci necesare pentru a putea plimba toţi elevii în condiţii de siguranţă?

Se dau două numere naturale nenule N și S. Determinați numerele distincte x1, x2, .., xN aparținând mulțimii {1, 2, ..., N} astfel încât
1 * x1 + 2 * x2 + .. + N * xN = S.

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort. Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

În școala unde învață, Andrei și Bogdan cunosc alți N elevi, etichetați cu numerele 1, 2, …, N. Dintre cei N elevi, o parte sunt prietenii lui Andrei. O parte dintre cei N elevi sunt dușmanii lui Bogdan. Se cunosc atât tichetele prietenilor lui Andrei, cât și etichetele dușmanilor lui Bogdan. Directorul școlii dorește să organizeze o excursie la care să participe Andrei, Bogdan și S dintre cunoscuții acestora, astfel încât din grupul celor S elevi să facă parte cel puțin K1 dintre prietenii lui Andrei și cel mult K2 dintre dușmanii lui Bogdan. Dorind să evite evenimente neplăcute, directorul va alege cei S elevi astfel încât numărul total al absențelor acumulate de aceștia, notat Sm, să fie minim.

Cunoscând valorile N, S, K1, K2, etichetele prietenilor lui Andrei, etichetele dușmanilor lui Bogdan, precum și numărul absențelor acumulate de fiecare dintre cei N elevi, determinați valoarea Sm obținută pentru un grup ce satisface condițiile de mai sus.

Ana şi Bogdan joacă un nou joc – JBB (Jocul „Borcane cu Bomboane”). Pe tabla de joc sunt plasate N borcane cu bomboane. Se ştie câte bomboane se află în fiecare borcan: în borcanul i sunt B i bomboane (1≤i≤N).

Ca de obicei, Ana începe jocul, iar apoi cei doi jucători mută alternativ. Fiind prima la mutare, Ana alege un borcan din care va lua toate bomboanele.

Pe tabla de joc sunt trasate săgeţi care unesc borcanele. Mai exact, de la fiecare borcan i pleacă o singură săgeată către un alt borcan j. Săgeţile indică modul în care jucătorii se deplasează pe tabla de joc. Dacă există săgeată de la borcanul i la borcanul j, iar un jucător a luat bomboanele din borcanul i, atunci adversarul său e obligat să se deplaseze la borcanul j. Dacă în borcanul j va găsi bomboane, este obligat să le ia pe toate. Dacă borcanul j este gol, atunci adversarul poate să aleagă un alt borcan care conţine bomboane şi continuă jocul.

Evident, scopul fiecărui jucător este să aibă, la finalul jocului (atunci când toate borcanele au fost golite) cât mai multe bomboane.

Determinaţi numărul maxim de bomboane pe care Ana le-ar putea obţine respectând regulile jocului. Bineînţeles, atât Ana, cât şi Bogdan joacă optim (adică la orice pas, fiecare jucător va face cea mai bună mutare pe care poate să o facă).

Se consideră N, un număr natural nenul. Dorim să-l scriem pe N ca sumă a două numere naturale nenule x și y, astfel încât suma cifrelor numerelor x și y să fie maximă. Scrieţi un program care să rezolve următoarele cerinţe:

1. să determine suma maximă a cifrelor a două numere x și y cu proprietatea că x+y=N;
2. să determine două numere naturale nenule xmax și ymax cu proprietatea că xmax≥ymax, xmax+ymax=N, suma cifrelor lor este maximă, iar diferența xmax-ymax este maximă;
3. să determine două numere naturale nenule xmin și ymin cu proprietatea că xmin≥ymin, xmin+ymin=N, suma cifrelor lor este maximă, iar diferența xmin-ymin este minimă.

Legendarul vrăjitor Merlin se distrează în laboratorul său. El are N poțiuni magice (etichetate cu 1, 2, …, N) aranjate pe o singură linie într-o ordine dată. El dorește să le aranjeze în ordine crescătoare. Se va muta o singură poțiune la un moment dat. Prima poțiune mutată va fi cea etichetată cu 1, apoi cea etichetată cu 2 și așa mai departe. Bineînțeles, pentru a rezolva problema, Merlin va apela la magie. Fiecare poțiune poate fi mutată folosind una sau mai multe vrăji, trecând prin una sau mai multe poziții intermediare. Mutând o poțiune de la poziția I în poziția J, vraja va consuma (I-J)2 unități de energie. De exemplu, dacă există șapte poțiuni aranjate astfel 1, 7, 3, 4, 5, 2, 6 și Merlin mută poțiunea (etichetată cu 2) de la cea de-a șasea poziție la a doua poziție atunci noua aranjare va fi 1, 2, 7, 3, 4, 5, 6 cu (6-2)2 unități de energie consumate. Înainte de a începe distracția, Merlin a stabilit două criterii:
1. El nu dorește să fie prea obosit la sfârșitul zilei, de aceea nu dorește să consume mai mult de E unități de energie.
2. De asemenea el se plictisește repede, de aceea el dorește să rezolve problema cu un număr minim de vrăji. Calculați numărul minim de vrăji pe care le poate folosi Merlin pentru a rezolva problema.

Cătălin lucrează la o firmă de transport de marfă. El se ocupă de planificarea traseelor pe care circulă camioanele. Există N trasee pe care pot merge camioanele, pe fiecare traseu poate circula cel mult un camion, iar acest camion nu poate depăși o limită de greutate ai. Firma deţine M camioane, fiecare camion poate circula pe maxim un traseu şi are o greutate bi. Ajutați-l pe Cătălin să planifice camioanele pe trasee în așa fel încât să poată circula cât mai multe camioane. Determinați numărul maxim de camioane care pot circula în același timp pe trasee și afișați o modalitate de a distribui camioanele pe trasee pentru a obține acest maxim.