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 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.

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.

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.

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.

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.