Lista de probleme 192

Filtrare

#2077 Poarta

Harta Galaxiei este reprezentată ca o matrice cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). Orice element al matricei reprezintă o zonă de formă pătrată cu latura de 1 an lumină (denumită quadrant) şi poate fi identificat prin coordonatele sale (numărul liniei şi respectiv numărul coloanei pe care află).

Nava Enterprise se află într-un quadrant de coordonate cunoscute şi trebuie să ajungă la destinaţie (un alt quadrant, diferit de cel de plecare, de coordonate de asemenea cunoscute).

Nava se poate deplasa de la un quadrant la unul dintre cei învecinaţi pe orizontală sau verticală într-o unitate de timp (mai exact, din zona de coordonate (L,C) nava se poate deplasa în una dintre zonele de coordonate (L-1,C), (L+1,C), (L,C-1), (L,C+1), fără a ieşi de pe hartă).

În plus, în unele zone (quadranţi) se găsesc porţi stelare. O poartă stelară permite deplasarea navei într-o unitate de timp în oricare altă zonă în care se găseşte o altă poartă stelară. Dacă în drumul său nava ajunge într-o zonă cu o poartă stelară, nava se poate deplasa într-o altă zonă cu poartă stelară sau poate să-şi continue drumul în una dintre zonele învecinate.

Determinați timpul minim în care nava poate ajunge din zona inițială în cea finală, precum și numărul de trasee de durată minimă.

#4020 text2

Dintr-o regretabilă eroare, redactorul Vasile a şters toate spaţiile din textul la care lucra. Textul este scris într-o limbă necunoscută, numai cu litere mici ale alfabetului englez. Vasile ştie că un cuvânt trebuie să conţină cel puţin o vocală şi că nu poate avea lungimea mai mare de 20 de litere. De asemenea, fiind un tip meticulos, el ştie că în text erau (înainte de ştergerea spaţiilor) exact N cuvinte. Vasile trebuie să restaureze textul, inserând spaţii între cuvinte. Cum există numeroase modalităţi de restaurare a textului, Vasile a hotărât să aleagă varianta în care literele sunt distribuite în cuvinte într-un mod cât mai armonios. Pentru a măsura armonia, Vasile a calculat suma pătratelor lungimilor cuvintelor. Textul este cu atât mai armonios, cu cât suma obţinută este mai mică. Dat fiind textul fără spaţii, să se determine câte posibilităţi de restaurare există (în total, indiferent de armonia lor), precum şi cea mai armonioasă modalitate de restaurare.

#3572 rafturi

Într-o bibliotecă se află C dulapuri identice aşezate unul lângă altul pe peretele unei încăperi, dulapurile fiind numerotate de la stânga spre dreapta cu numerele naturale de la 1 la C. Fiecare dulap conţine 1000 de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la 1 la 1000 de jos în sus.

Fiecare dulap este prevăzut cu o scară cu care se poate ajunge la orice raft. Dacă bibliotecara urcă scara unui anumit dulap D până la un anumit nivel k, ea va putea aduna orice carte de pe rafturile 1 până la k inclusiv, din dulapul D şi din dulapurile învecinate (dulapul D-1 şi dulapul D+1).

Cunoscând dulapurile şi rafturile de unde trebuie luate cărţi, bibliotecara doreşte să adune toate cărţile cerute, dar suma înălţimilor până la care trebuie să urce să fie minimă.

Miruna a găsit pe fundul mării o matrice cu n linii şi m coloane având elementele numere naturale. Din motive necunoscute, Mirunel, prietenul misterios al Mirunei, vrea să afle care este latura celei mai mari submatrice pătratice care conţine maxim k numere distincte. Submatricea cu colţul stânga-sus (xs, ys) şi colţul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] şi indicele coloanei în intervalul [ys, yd]. Scrieţi un program care să determine latura maximă a unei submatrice care respectă condiţiile lui Mirunel.

Se dă o matrice cu M linii şi N coloane în care toate elementele sunt numere naturale. Fie L latura maximă a unei submatrici simetrice din această matrice. Pentru fiecare dimensiune i între 1 și L să se determine câte submatrici simetrice şi cu latura i ale matricii date există.

Se organizează o petrecere la care participă N băieți (numerotați de la 1 la N) și N fete (numerotate de la 1 la N). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele și băieții formează o configurație de dans, adică N perechi, după una din următoarele reguli:
1. băiatul i dansează cu fata i;
2. băiatul i dansează cu fata j și atunci obligatoriu băiatul j dansează cu fata i.
De exemplu, pentru N = 7, două configurații de dans posibile sunt:
(1, 1) (2, 2) (3, 7)(4, 5) (5, 4) (6, 6) (7, 3)
(1, 1) (2, 2) (3, 3)(4, 5) (5, 4) (6, 6) (7, 7)
Prin perechea (i, j) s-a notat faptul că băiatul i dansează cu fata j. Două configurații sunt distincte dacă ele diferă prin cel puțin o pereche. Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.

#3563 spider

Omul păianjen (Spiderman) sare de pe o clădire pe alta, aflată în imediata vecinătate, în nord, est, sud sau vest. Clădirile din cartierul omului păianjen au o înălţime exprimată în numere naturale şi sunt aşezate pe m rânduri, câte n pe fiecare rând. Spiderman va alege să sară pe una dintre clădirile vecine, care are înălţimea mai mică sau egală, iar diferenţa de înălţime este minimă. Dacă există mai multe clădiri vecine de aceeaşi înălţime, omul păianjen aplică ordinea preferenţială nord, est, sud, vest, dar nu sare încă o dată pe o clădire pe care a mai sărit. Scopul omului păianjen este acela de a reuşi să facă un număr maxim de sărituri succesive.

Scrieţi un program care determină numărul maxim de sărituri succesive, pe care îl poate efectua, pornind de la oricare dintre clădiri, precum şi poziţiile clădirilor care formează drumul maxim.

#1120 xcmmdc

Se dă o matrice cu m linii şi n coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat k.

Pentru matricea dată şi numărul k dat să se răspundă la q întrebări de forma: “Câte submatrice pătratice de latură L cu cel mai mare divizor comun al elementelor egal cu k există în matricea dată?”

#1201 Text1

Un şir format din cifre trebuie să fie tastat în una sau mai multe sesiuni.

Există două tastaturi: tastatura A care conţine taste cu toate combinaţiile de exact două cifre: tasta 00, tasta 01, 02, …, 98, 99 și tastatura B care conţine taste cu toate combinaţiile de exact trei cifre: tasta 000, tasta 001, …, 998, 999. Cifrele se vor introduce în una sau mai multe sesiuni, pentru o sesiune putându-se folosi o singură tastatură. Datorită unei ordonanțe de urgență, dacă o combinație de taste a fost introdusă cu una din tastaturi în sesiunea curentă și, continuând sesiunea, această combinație poate fi introdusă din nou, este necesar să continuăm sesiunea cel puțin până când o vom introduce din nou. În cazul în care introducem până atunci și alte taste, trebuie să continuăm sesiunea până când vom introduce ultima apariție a lor.

Astfel, dacă şirul 255222255257 este început folosind tastatura A, se va scrie obligatoriu într‑o sesiune 25 52 22 25 52. Suntem obligați să tastăm până la ultima apariție a tastei 25 în sesiunea curentă, și când folosim tasta 52 suntem obligați să continuăm până la ultima apariție a acesteia. A se observa că cifrele de pe pozițiile subliniate sunt tot 2 și 5, însă nu formează o tastă care se poate apăsa în sesiunea curentă. Deoarece se dorește un număr cât mai mare de sesiuni, se va începe o nouă sesiune în care se va scrie doar 57.

Cunoscându-se numărul total de cifre și secvența de cifre ce formează şirul, să se determine o modalitate de a despărţi textul astfel încât el să poată fi scris într-un număr maxim de sesiuni.

Fie a și b două numere naturale nenule. Scrieți un program care determină numărul de numere naturale formate din exact a cifre care au fiecare produsul cifrelor egal cu b și afișează în fișierul de ieșire restul împărțirii valorii determinate la numărul 9973.