Lista de probleme 878

Filtrare

#4557 Lee3

Se dă o matrice binara cu N linii și M coloane. Celulele cu numarul 0 sunt libere si se pot traversa. Celulele cu numarul 1 sunt ocupate si nu se pot traversa. Pentru K poziții date, se cere să se determine drumul de lungime minimă care pleacă de la poziția (i1, j1) și trece prin toate cele K poziții intermediare (nu contează în ce ordine), ajungând în final în poziția (i2, j2).

Se dă un vector de N numere naturale. Se dau deasemenea Q query-uri de forma l r, unde se cere suma tuturor subsecvențelor de elemente consecutive. Mai formal, pentru fiecare query [l, r], se cere rezultatul funcției F(l, r) = \( \sum_{i=l}^{r} \sum_{j=i}^{r} \) S(i, j), unde S(l, r) este suma tuturor elementelor din secvența [l, r].

Vrei să-ți aranjezi vitrina florăriei în cel mai minunat mod cu putință. Ai F buchete de flori de diferite soiuri și cel puțin la fel de multe vaze aliniate pe un rând. Vazele sunt lipite de raft și sunt numerotate de la stânga la dreapta cu numere de la 1 la V, unde V este numărul de vaze. Pentru a obține cel mai plăcut efect trebuie să maximizezi suma valorilor estetice pentru aranjament, păstrând în același timp ordinea necesară a florilor. Dacă există mai multe aranjamente de valoare maximă totală, oricare dintre ele va fi acceptată. Trebuie să afișați exact un aranjament.

#4528 batch

Se dă o secvență de N procese, numerotate de la 1 la N, care urmează să fie pe rând executate de o mașină. Șirul de procese trebuie împărțit în unul sau mai multe grupe, fiecare grupă conținând o secvență de procese consecutive. Procesarea începe la momentul 0. Dat timpul S și un șir de procese împreună cu timpii de executare și factorii de cost, calculați costul total minim.

#4524 Acces3

Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.
p. Accesul în clădire se realizează prin una dintre camerele de pe linia 1 și coloana 1 sau linia 1 și coloana m.

În una dintre camere se află proprietarul clădirii, care dorește să afle,care este numărul de variante în care poate să părăsească clădire și care este durata maximă exprimată în minute a unui traseu se ieșire fără ca să treacă de două ori prin aceeași cameră.

Chimmy are un șir de N numere întregi și Q întrebări de forma a b, unde pentru fiecare întrebare Chimmy dorește să afle, pe parcurgerea șirului de la poziția a la poziția b, de câte ori se schimbă maximul. Chimmy, neștiind să programeze, vă cere să îl ajutați pentru 100 de puncte!

#4511 divnoua

Se citesc numerele naturale n şi k şi cifrele nenule distincte c[1], c[2], …, c[n].

Să se determine câte numere de k cifre formate doar cu cifrele c[1], c[2], …, c[n] sunt divizibile cu 9. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 666013.

Se dă un număr natural nenul n. Se construiește mulțimea numerelor formate din n cifre care au proprietatea că nu au două cifre alăturate care să fie prime. De exemplu 1476 este un număr corect format, dar 1537 nu este pentru că are cifrele alăturate 5 și 3 sau 3 și 7 cu proprietatea că sunt prime.
Să se determine câte numere formate din n cifre au proprietatea că nu au două cifre alăturate care să fie prime. Pentru că acest număr poate fi foarte mare, se va determina modulo 666013.

Se dă un string S format doar din litere mici ale alfabetului englez și Q operații de forma:

  • 1 a b len – se va afișa 1 dacă secvențele S[a, a+len-1] și S[b, b+len-1] sunt egale. În caz contrar, se va afișa 0.
  • 2 l r ch – toate caracterele între pozițiile l și r devin ch.

Să se scrie un program care poate efectua aceste operații.

Se consideră un șir format din primele N numere naturale nenule. Să se afle numărul de partiții în 2 submulțimi disjuncte cu suma egală care există pentru acest șir.