Lista de probleme 7

Avem o jucărie formată din NxN pătrate de latură 1 dispuse ca într-o matrice cu N linii și N coloane. Liniile și coloanele matricei sunt numerotate de la 1 la N, iar N este mereu impar. Pătrățelele pot fi albe și le vom codifica 0, sau negre și le codificăm 1. Împărțim matricea în zone concentrice astfel: zona 1 este formată din linia 1, coloana N, linia N și coloana 1; zona 2 este formată din linia a doua, coloana N-1, linia N-1, coloana 2 etc. Sunt [N/2] astfel de zone. În mijlocul matricei este, evident, un singur element, N fiind impar. Asupra oricărei zone putem aplica o operație de rotire, doar spre stânga.

Dată fiind codificarea jucăriei, precum și “lungimea” maximă permisă pentru o rotire în oricare zonă, să se determine numărul de posibilități de a aplica rotiri asupra zonelor așa încât să rezolvăm jucăria. Evident, unei zone i se poate aplica o singură rotire, de lungime cuprinsă între 0 și valoarea maximă permisă.

Se consideră două șiruri de numere naturale, ambele de lungime n, a=(a[1],a[2],...,a[n]) și b=(b[1],b[2],...,b[n]). Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea {1,2,…,n}. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici i și j, cu 1≤i≤j≤n, apoi prin interschimbarea secvențelor a[i],a[i+1],...,a[j] cu b[i],b[i+1],...,b[j] se obțin șirurile:

• a[1], a[2], ...,a[i-1], b[i],b[i+1],…, b[j], a[j+1],a[j+2], …, a[n] și
• b[1], b[2], ...,b[i-1], a[i], a[i+1],…, a[j], b[j+1],b[j+2], …, b[n].

Dacă măcar unul din șirurile obținute este permutare a mulțimii {1,2,…,n}, atunci spunem că s-a obținut un mixperm.

Să se determine în câte moduri se poate obține un mixperm.

Se consideră un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤…≤a[N]. În legătură cu acest șir de numere ne interesează perechile de poziții (i,j) cu 1≤i<j≤N și a[i]≠a[j] sau ne interesează suma elementelor anumitor secvențe.

Se cere să se scrie un program care să citească un număr C reprezentând tipul cerinței, un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N] și T perechi de numere naturale (p[k],q[k]) cu 1≤p[k]<q[k]≤N și 1≤k≤T și apoi:

(1) Dacă C=1, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) suma a[p]+a[p+1]+...+a[q].
(2) Dacă C=2, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) numărul de perechi (i,j) care respectă simultan condițiile p≤i<j≤q și a[i]≠a[j].

Cu toții știm că popcornul este o adevărată delicatesă culinară. În pregătirile tale pentru lotul de anul acesta (și pentru petrecerile de după), ai făcut comandă de N tipuri de floricele de porumb pentru microunde. Fiecare tip are asociate 3 valori:

• A[i] = Timpul (în secunde) la care orice floricică de acel tip “pocnește”;
• B[i] = Timpul (în secunde) la care orice floricică de acel tip “se arde”;
• C[i] = Cantitatea (în floricele) a respectivului tip.

Mai ai la dispoziție M pungi pentru floricele de unică folosință de capacitate foarte mare (practic, infinită) și un cuptor cu microunde. Cum, bineînțeles, nimănui nu îi plac floricelele nefăcute sau cele arse, îți dorești să le partiționezi convenabil în cele M pungi și apoi să le introduci pe rând în cuptorul cu microunde, setându-i un timp de preparare prep[i] corespunzător, astfel încât după cele M tranșe să obții cât mai multe floricele comestibile.

Formal, o floricică de tipul i introdusă în punga j , setată la timpul (în secunde) de preparare prep[j] este comestibilă dacă și numai dacă A[i] ≤ prep[j] < B[i].

Fiind date cele N tipuri de floricele și numărul de pungi disponibile, trebuie să găsești o partiție convenabilă și timpii optimi de preparare pentru fiecare pungă, astfel încât la final să obții numărul maxim de floricele comestibile, pe care să îl afișezi în fișierul de ieșire. Prea ușor!

Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].

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.

Ion şi Ana se amuză construind cuvinte formate din litere mari ale alfabetului englez: A,B,...,Z. Aceștia îşi imaginează o nouă limbă care admite cuvinte conţinând subsecvenţe formate din aceeaşi literă. Ei au impus totuși o restricţie: niciun cuvânt nu trebuie să înceapă cu litera Z. De exemplu, fie cuvântul: AAZCCCCADDDBBBBEEC. Cuvântul nu începe cu Z. El poate fi descompus în subsecvenţe formate din litere identice: AA Z CCCC A DDD BBBB EE şi C. Dintre acestea, CCCC şi BBBB au lungimea 4. Numim subsecvenţe repetabile maximale cele mai lungi subsecvenţe formate din litere identice. Deci, în exemplul de mai sus, CCCC şi BBBB sunt subsecvenţe repetabile maximale.

Întrebarea pe care şi-o pun acum Ion şi Ana este următoarea: care este numărul (modulo 30011) de cuvinte formate din cel mult n litere mari ale alfabetului englez, care conţin cel puţin o secvenţă repetabilă maximală de lungime k. Atenție, cuvintele nu vor putea conține secvențe repetabile de lungime strict mai mare decât k.

Cunoscând n și k, lungimea maximă a unui cuvânt și respectiv lungimea unei secvenţe repetabilă maximală, să se determine numărul de cuvinte care se pot forma, modulo 30011.