Lista de probleme 217

Fie N și K două numere naturale. Toate punctele din plan de coordonate întregi (x,y) cu proprietatea 0 ≤ x ≤ N, 0 ≤ y ≤ N se unesc prin linii orizontale și verticale de lungime 1. Apoi K linii de lungime 1 dintre cele de mai sus se șterg. Definim o cale ca fiind o succesiune continuă de linii orizontale sau verticale de lungime 1, între originea sistemului de axe și punctul de coordonate (N, N), cu lungimea totală 2∙N. Să se determine numărul total de căi distincte.

În Hogwarts există o tablă de șah cu N linii și M coloane. Harry Potter a găsit plasate, de către Hagrid, T ture care apără fiecare linia și coloana pe care este așezată. El trebuie să plaseze în siguranță K pioni pe tablă, adică fără ca vreunul dintre ei să fie atacat de vreo tură. Tabla de șah din Hogwarts este specială deoarece în cadrul unei celule pot fi plasați chiar și mai mulți pioni simultan! Cunoscând toate aceste reguli, ajutați-l pe Harry Potter să determine în câte modalități poate plasa în siguranță toți cei K pioni pe tabla de șah.

Definim o expresie ca fiind un șir de caractere e care respectă una dintre următoarele:

• e = "x";
• e reprezintă un număr natural (constantă); (ex. e ∊ {"1", "2"; "200"; ...})
• e = "[e1,e2]" sau e = "(e1,e2)", unde e1, e2 sunt (sub-)expresii. Aici, (•, •) semnifică cel mai mare
  divizor comun a două numere, iar [•,•] semnifică cel mai mic multiplu comun a două numere. De exemplu, avem că (6, 8) = 2, [6, 8] = 24.

Dându-se o expresie e și două numere naturale a, b, să se calculeze eval(e, a) + eval(e, a+1) + ... + eval(e, b). Rezultatul se va afișa modulo 1.000.000.007.

Primarul orașului tocmai a aprobat un proiect pentru construirea unui ștrand la periferia localității. Zona pe care se dorește a fi amplasat ștrandul se poate identifica cu planul 2D (infinit). Aceasta conține N arbori, aflați la coordonate întregi, cu lățimea de 1 metru. Nu există doi arbori la aceeași coordonată x sau y. Mai exact, xi ≠ xj și yi ≠ yj, pentru orice i ≠ j. Care este suma ariilor tuturor regiunilor valide posibile? Rezultatul se va afișa modulo 1.000.000.007.

In plină perioadă de pandemie, cercetătorii unui institut vor să facă o serie de experimente pe culturi de celule. S-a observat deja că celula cercetată are o creștere liniară dependentă de cele trei zile imediat anterioare: dacă acum două zile aveam x celule, ieri aveam y iar astăzi avem z celule, atunci mâine vom avea x+ay+bz celule. Dacă într-o zi, numărul de celule depășește o valoare k, cercetătorii reduc cultura la valoarea modulo K.

Dacă, pentru un n dat, se cunoaște numărul de celule din zilele n, n-1, n-2 și se cunosc factorii de multiplicare a și b, care este numărul de celule care trebuie cultivate în primele 3 zile ale experimentului?

Un număr este special dacă are o cifră cu frecvența strict mai mare decât partea întreagă a jumătății lungimii numărului și nu conține cifra 0. Câte numere speciale există respectiv care este suma tuturor numerelor speciale de lungime N.

După ce Le. Quack a avut mare succes cu noul lui joc de cărți a decis să se apuce de scamatorii, pentru ca este pasionat de cărți îi cere patronului N cărți. Acesta așează toate cărțile pe față și se pregătește să facă o scamatorie. Acesta vrea să întoarcă toate cărțile pe spate, o operație constă în alegerea a mai multor cărți pe față adiacente și întoarcerea lor. Ca să facă totul mai interesant el alege Q persoane din public si acestea îi spun două numere, X Y, cu semnficația ca Le. Quack să facă toate trucurile posibile cu X cărți inițial pe față toate și exact Y operații de întoarcere astfel încât să ajungă cu toate cele X cărți alese pe spate. După fiecare dintre cele Q persoane el repune toate cărțile pe față. Le. Quack trebuie să numere toate posibilitățile de a face fiecare truc de magie doar că nu este bun la informatică așa că vă cere ajutorul!

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 la dispoziție toate numerele naturale de la 1...M pentru a forma vectori de lungime N. De exemplu , Pentru N = 3 și M = 200 , un posibil vector este [199 , 41 , 41]. Pentru fiecare vector distinct care poate fi creat ( doi vectori A și B sunt distincți dacă există cel puțin un i astfel încât A[i] != B[i]) , se cere să determinați cel mai mare divizor comun al elementelor sale. Care este suma valorilor determinate ?

Anual, Imperiul Interstelar organizează o întâlnire administrativă în capitală. La întâlnire sunt invitați toți guvernatorii planetelor din imperiu. Planetele imperiului pot fi numerotate cu valori de la 0 la MOD-1(inclusiv) unde planeta 0 este chiar capitala. Distanțele mari dintre planete fac transportul obișnuit între planete aproape imposibil. Din fericire, găuri de vierme conectează tot imperiul. Vom nota planeta către care duce o gaură de vierme cu f(x) = (x * a + b) % MOD. Astfel, de la planeta x există un drum către planeta f(x) și un drum de la planeta f(x) la planeta x. Fiecare guvernator începe de pe o planetă cunoscută și trebuie să ajungă în capitală. Atenție, pozițiile inițiale nu trebuie să fie distincte! Fiecare salt printr-o gaură de vierme consumă o unitate de energie din rețeaua centrală. Se presupune că fiecare guvernator ia ruta cea mai scurtă către capitală. Din motive birocratice, sunteți rugați să calculați cantitatea de energie consumată de transportul guvernatorilor către captială.