Lista de probleme 809

Filtrare

#4284 kx_desc

Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x. Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.

Dându-se un graf neorientat cu n noduri și m muchii, să se determine numărul componentelor conexe.

Dându-se un graf neorientat cu n noduri și m muchii, să se determine numărul componentelor conexe.

Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i. Să se determine numărul perechilor de puncte simetrice.

Romeo şi Julieta sunt prinşi într-un labirint, dat sub forma unei matrice cu M linii şi N coloane, cu elemente 0 şi 1. Un element 1 reprezintă zid, iar 0 reprezintă spaţiu liber. Romeo şi Julieta se află iniţial în pătratelele (1,1) (Romeo) respectiv (M,N) (Julieta) ale matricei, care conţin 0, se pot deplasa numai pe pătratele care conţin 0 şi nu pot părăsi matricea. Scrieţi un program care va decide care dintre mutări vor fi efectuate de Romeo şi care de Julieta pentru a-i ajuta pe cei doi să ajungă la destinaţii.

#4244 urgenta

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.
Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de K grupuri.

Vrei să călătorești n kilometri din orașul A în orașul B cu o mașină care are un rezervor de combustibil care poate asigura un număr de m kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare :) )

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.

#4229 kdist

Bujorel s-a apucat de pomicultură şi a însămânţat un arbore (graf conex aciclic) cu N noduri, fiecare nod având o culoare dată dintr-un interval [1, K]. Acum, după ce arborele a crescut, el doreşte să ştie, pentru fiecare culoare, suma distanţelor dintre toate perechile de noduri ale arborelui ce au culoarea respectivă. Distanţa dintre două noduri se defineşte ca fiind numărul de muchii de pe drumul dintre cele două noduri. Deoarece Bujorel a folosit foarte mult îngrăşământ la plantarea arborelui, acesta a crescut foarte mult şi voi trebuie să scrieţi un program care calculează suma distanţelor dintre nodurile cu aceeaşi culoare.

Lot Resita 2012