Lista de probleme 11

Nivelul concursului: Online - open

https://infoleague.net/

Grupe

Juniori

Etichete

#3831 Medians

Se dă un vector cu n elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu k.

Se dau Q interogări de tipul : n , st , dr , r , k. Pentru fiecare din aceste interogări să se determine care este numărul maxim din șirul [n xor st , n xor (st+1) , n xor (st+2) , .... , n xor dr] care dă restul k prin împărțire la r , precum și numărul de numere din secvența care dau restul k prin împărțire la r.

Dându-se un vector cu elemente întregi, care este numărul minim de iterații ale unui algoritm dat astfel încât să sorteze vectorul descrescător?

După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își
creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi.

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 ?

infoleague.net runda de antrenament, problema B.

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

Să se calculeze câte numere de n cifre au gradul de frumusțe k.

#3827 C-Bombs

Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...n. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior.

După ce Julius Caesar l-a învins pe Pompey în bătălia de la Pharsalus , acesta decide să țină un festin în cinstea soldaților săi loilai . El are q scenarii posibile pt oaspeți definite printr o pereche (n,k) care înseamnă că fiecare dintre cei n invitați pot alege unul dintre cele k feluri de mâncare . Deoarece Julius Caesar a plătit cei mai buni bucătari pentru a prepara mancarea , el își dorește ca fiecare fel de mâncare să fi fost ales de minimum un invitat. O configurație este un șir de n numere a , al i-lea soldat a ales felul a(i) . Câte configurații distincte există care să îndeplinească cerințele marelui Julius Caesar ? Două șiruri sunt distincte dacă diferă prin cel puțin o poziție.

infoleague.net runda de antrenament, problema D.

#3822 GCD2

Se dă un vector A de N elemente. Trebuie să calculați suma celui mai mare divizor comun din toate secvențele vectorului . Mai formal , notând cu F(st , dr) = cmmdc(A[st] , A[st+1] ... A[dr]) 1 <= st <= dr <= N , trebuie să calculați suma tuturor F(st , dr) posibile.