Lista de probleme 9

Gimi a găsit un nou joc, faimos pentru dificultatea sa ridicată. Jocul este alcătuit din N camere, numerotate de la 1 la N. Fiecare cameră i conține un monstru a cărui putere este un număr natural P[i]. Gimi trece, în ordine, prin toate camerele. În fiecare cameră el poate alege să se lupte cu monstrul sau nu. Gimi se întreabă în câte moduri poate să aleagă 3 monștri cu care să se lupte. Două mulțimi de trei monștri se consideră diferite dacă există cel puțin un monstru în prima mulțime care nu aparține celei de-a doua mulțimi. Formal, se cere numărul de tripleți i < j < k pentru care P[i] < P[j] < P[k] și P[i] + P[j] + P[k] ≤ S.

Se dă un șir A, ale cărui elemente sunt definite prin relația \( {A}_{i} = {i}^{k} \cdot {2}^{i} \) pentru orice 1 ≤ i, unde K este un număr natural dat. Elementele acestui șir se așează într-o matrice M, formată din L linii și C coloane. Ashima vă cere să răspundeți la Q cerințe de forma: \(l_1\ l_2\ c_1\ c_2\) : care este suma elementelor \(M_{i,j}\) din matricea M astfel încât \(l_1 \leq i\leq l_2\) și \( c_1 \leq j \leq c_2\)?

Se dă un tablou bidimensional cu N linii și N coloane. Există Q poziții distincte, etichetate cu numere naturale distincte de la 1 la Q, unde în tablou există valoarea 1, la toate celelalte poziții din tablou există valoarea 0. Pentru o poziție oarecare, dintre cele Q date, numim “forța” acelei poziții numărul subtablourilor din tabloul dat care conțin doar o singură valoare 1, cea aflată la acea poziție, restul elementelor din subtablouri fiind egale cu 0. Pentru un șir format din P etichete distincte, dintre cele corespunzătoare celor Q poziții date, se cere să se calculeze suma “forțelor” acestora.

Marele dramaturg BONIFACCI a uimit lumea teatrului cu noua sa capodoperă, Dada?!. Pentru că teatrul modern este un pic minimalist, piesa are un singur actor. Pentru că teatrul modern este un pic absurd, Actul 1 constă doar din replica A, iar Actul 2 constă doar din replica D. La repetiție, actorul și-a propus să recite, cu intonație, L replici alăturate din actul al N-lea, începând cu replica numărul P, până la replica cu numărul P+L-1. Determinați secvența de caractere rostite de actor la repetiție.

Se consideră un număr natural nenul N. Să se determine toate pătratele perfecte distincte care se obțin prin permutarea cifrelor numărului N.

Kida vă oferă două numere N și M. Ea vă mai oferă și un șir, A, de N numere naturale cuprinse între 0 și M inclusiv. Șirul A conține două tipuri de valori: valori cuprinse între 1 și M, care nu pot fi schimbate, respectiv valori de 0, care pot fi înlocuite cu orice număr cuprins între 1 și M. Pentru un șir V, cu valori între 1 și M, vom nota cu count(V) numărul de perechi (V[i], V[j]) de pe pozițiile i și j astfel încât i < j și cmmdc(V[i], V[j]) = 1. Se cere suma count(V) pentru toate șirurile distincte V care se pot obține din șirul A, înlocuind toate valorile de 0 cu numere cuprinse între 1 și M. Deoarece acest număr poate să fie foarte mare, se cere restul împărțirii sale la 1.000.000.009.

Cunoscând numărul de zile în care se desfășoară activitatea, producția zilnică inițială, respectiv lista cu cele N comenzi, să se rezolve următoarele cerințe:

• dacă T = 1, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul ultimei zile (a N-a zi).
• dacă T = 2, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul celei de-a i-a zi, pentru fiecare i de la 1 la N.

Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice N x N cu N impar. Fiecare poziție din matrice este o cameră și în fiecare cameră se află câte o alună. Camerele sunt numerotate cu numărul de linie și numărul de coloană. Cunoscând N, să se răspundă la Q întrebări de forma: “Ce traseu a notat Chip pe poziția P?”

Pentru fiecare dintre cele Q excursii, se cere să se determine costul total minim, exprimat în dolari, care va fi plătit pentru ca cei doi tineri să se poată întâlni într-unul dintre cele N sate, eventual după modificarea a 0 sau mai multe indicatoare din satele vizitate.