Lista de probleme 215

Se dă N și Q, apoi Q interogări de tipul K X pentru fiecare interogare să se afișeze separate prin spațiu ( ficare interogare pe un rând diferit ):

1. Câți vectori de exact N elemente din intervalul $[0,2^K)$ ( mai mari sau egale cu $0$ și strict mai mici ca $2^K$ ) există astfel încât valoarea $a_1$ & $a_2$ & ... & $a_N$ să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu & am notat operația pe biți AND.

2. Câți vectori de exact N elemente din intervalul $[0,2^K)$ ( mai mari sau egale cu $0$ și strict mai mici ca $2^K$ ) există astfel încât valoarea $a_1$ | $a_2$ | ... | $a_N$ să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu | am notat operația pe biți OR.

3.Câți vectori de exact N elemente din intervalul $[0,2^K)$ ( mai mari sau egale cu $0$ și strict mai mici ca $2^K$ ) există astfel încât valoarea $a_1$ ^ $a_2$ ^ ... ^ $a_N$ să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu ^ am notat operația pe biți XOR.

Aveți o foaie de hârtie dreptunghiulară cu dimensiunile N x M centimetri. Foaia este împărțită într-o rețea de pătrate de 1 x 1 centimetri fiecare. Puteți considera foaia ca un sistem de coordonate – colțul din stânga jos este originea (0,0) a sistemului de coordonate și fiecărui vârf al unui pătrat îi sunt atribuite coordonate întregi – între 0 și N pe axa x și între 0 și M pe axa y. Primiți o succesiune de cereri de tăiere a foii de hârtie (sau mai exact, a părții care a mai rămas din ea). Fiecare cerere este definită de o pereche de numere întregi nenegative (p, q), reprezentând un punct din rețea, care este situat în porțiunea netăiată a hârtiei. Scrieți un program care după fiecare cerere calculează aria figurii rămase.

Anul 1905. Un stat din America de Sud și-a propus investiții majore în infrastructura feroviară. Brazilianul Badinho este managerul unei companii de transport feroviar pe o magistrală importantă. De-a lungul magistralei se află N stații, numerotate de la 1 la N. Fiecărei stații îi corespunde un număr Xi care reprezintă numărul de kilometri de la începutul magistralei până la stația i (X1 = 0). Știind că Badinho trebuie să cheltuiască întreaga sumă pe care ar primi-o dintr-o subvenție, să se determine:
-Numărul de moduri de a deschide o rută de tip Regio, modulo 1.000.000.007
-Numărul de moduri de a deschide o rută de tip Expres, modulo 1.000.000.007

Se consideră două numere naturale K și N. Să se determine numărul T al tuplelor formate din K numere naturale (X1, X2, X3, …, XK) cu proprietățile:

• 1 ≤ X1 ≤ X2 ≤ X3 ≤ ... ≤ XK ≤ N
• cel mai mare divizor comun al numerelor X1, X2, …, XK este 1.

Robotul Vasile s-a angajat la fabrica decoraţiunilor de Crăciun unicat. El trebuie să monteze beculeţe colorate în brăduţi, astfel încât oricare doi brăduţi să fie diferiţi. Pe o bandă de asamblare robotul Vasile are la dispoziţie N beculeţe colorate b1, b2, …, bN, astfel încât oricare două beculeţe sunt colorate diferit. În vârful bradului va pune o steluţă, iar pentru montarea beculeţelor în brăduţ el construieşte lanţuri de becuri. Cunoscând numărul N de beculeţe aflate pe banda de asamblare, scrieţi un program care să rezolve următoarele două cerinţe:
1. determină înălţimea bradului (numărul de lanţuri ce pot fi construite cu cele N beculeţe);
2. determină numărul de brazi diferiţi ce pot fi construiţi cu cele N beculeţe.

Cei N copii de la școala generală vor să formeze o echipă de fotbal compusă din K elevi, dintre care cel puțin unul stângaci și cel puțin unul dreptaci. Pentru fiecare copil i (de la 0 la N-1) se cunoaște intervalul de timp în care acesta este disponibil pentru a face parte din echipă, sub forma unei perechi, [starti, endi], cât și dacă este stângaci sau dreptaci. K copii pot juca în aceeași echipa dacă intervalele de timp în care aceștia sunt disponibili se suprapun în cel puțin un punct (moment de timp). Se cere numărul de moduri în care se poate alcătui o echipă cu K dintre cei N elevi; deoarece acest număr poate să fie foarte mare, el se va afișa modulo 1.000.000.009.

Construcția unei noi clădiri a fost finalizată! Frank, celebrul arhitect a făcut o poză cu fațada. Nu este chiar mulțumit de poză deoarece a observat o înclinație a pozei relativ la orizontală. Asta se poate repara printr-o rotație, iar Frank se întreabă dacă procesul de îndreptare nu ar putea fi automatizat. Cu acest scop, imaginea este transformată într-o mulțime de segmente din plan, detectate automat cu algoritmi speciali, ca în imaginea din dreapta. Segmentele care se obțin sunt identificate prin cele două extremități, puncte având coordonate numere naturale, în sistemul xOy: (x1, y1), (x2, y2). Un segment este numit aliniat cu axele dacă este orizontal paralel cu axa Ox, deci y1 = y2) sau vertical (paralel cu axa Oy, deci x1 = x2). Prin rotația imaginii în ansamblu, o parte dintre segmente devin aliniate cu cele două axe. Scrieți un program care pentru o mulțime de segmente determină numărul maxim de segmente care se pot alinia prin rotirea cu un același unghi a tuturor segmentelor. Unghiul de rotație poate fi orice număr real.

Kida și El Bandito Inofensivo au N display-uri digitale care pot afișa litere mici din alfabetul englez. Fiecare dintre cele N display-uri are câte M celule. Pentru fiecare display i, cunoaștem literele care pot fi afișate în fiecare celulă j a sa. El Bandito Inofensivo consideră că un cuvânt de lungime M este comun dacă acesta se poate forma pe cel puțin K dintre cele N display-uri. Auzind asta, Kida vă roagă să o ajutați să calculeze numărul de cuvinte comune distincte. Ajutați-o pe Kida să calculeze numărul de cuvinte comune distincte. De vreme ce acest număr poate să fie foarte mare, se cere restul său la împărțirea prin 1.000.000.009.

După ce a scăpat de Spân și a devenit împărat, Harap-Alb a decis să își construiască un nou castel în împărăția sa ce poate fi reprezentată cu ajutorul sistemului de coordonate carteziene. El știe că Roș-Împărat a construit N+1 garduri dreptunghiulare, însă știe și că acesta este cam zgârcit și nu a folosit cele mai bune materiale. Harap-Alb a învățat din greșeli, iar acum încearcă să se ferească de pericole cât de mult poate. De aceea, el vrea să își amplaseze castelul într-un punct din sistemul cartezian care să se afle în interiorul a cel puțin N dintre cele N+1 garduri. Fiind date numărul natural nenul N și coordonatele celor N+1 garduri (perechi de colțuri stânga-sus și dreapta-jos), să se determine (în cazul în care există) punctul cel mai apropiat de originea sistemului de coordonate unde Harap-Alb își poate amplasa castelul astfel încât acesta să se afle în interiorul a cel puțin N garduri.

În teoria grafurilor, un graf planar este un graf care poate fi încorporat într-un plan, adică poate fi desenat în plan în așa fel încât muchiile sale să se intersecteze doar în noduri. Cu alte cuvinte, aceste poate fi desenat în așa fel încât oricare două muchii să nu se intersecteze. Florin urmează în perioada 2023-2029 studii în informatică.
Fiind date NR = 2 * N noduri fixe (asemănător cu ceasul clasic) în planul xOy și N muchii, Florin vrea să determine numărul grafurilor distincte planare în care fiecare nod va avea gradul 1. Scrieţi un program care să determine numărul de grafuri obținute de Florin.