Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Lista de probleme 13

Filtrare

Mai multe opțiuni

maxime

#3692

Se dă un șir V cu N valori naturale nenule, memorate pe poziții consecutive începând cu poziția 1. Notăm cu S următoarea secvență de cod aplicată asupra sa:

(C/C++)
maxim = 0;
rep = 0;
for(i = 1; i <= N; i++)
	if(V[i] > maxim)
		maxim = V[i];
	else
		if(V[i] == maxim)
			rep++;

Considerăm operația de eliminare din V a elementului de pe o anumită poziție dată P. În urma operației de eliminare elementele de pe pozițiile P + 1, P + 2, ..., N ajung pe o poziție cu 1 mai mică iar N scade cu 1.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei rep dacă am aplica secvența S asupra șirului obținut după fiecare operație de eliminare.

Concursul Național Info Pro, Etapa II

Fișiere Lorintz Alexandru (Alex_tz307) Marius Nicoli concurs Clasa 10 Structuri de date liniare Stiva Stiva Programare dinamică Range Minimum Query Cautare binara
Rezolvă

crescator2

#3691

Fie un șir a de N numere întregi. Trebuie construit un nou șir b (tot cu N elemente) astfel:

  • dacă \( {a}_{i}>0 \), atunci \( {b}_{i}={a}_{i} \)
  • dacă \( {a}_{i}=0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă
  • dacă \( {a}_{i}<0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă cu excepția lui \( -{a}_{i} \)

Se garantează că \( {a}_{1} \) și \( {a}_{N} \)au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

Știindu-se șirul a, să se calculeze numărul de moduri de a forma șirul b astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la 1.000.000 007.

Concursul Național Info Pro, Etapa II

Fișiere Lorintz Alexandru (Alex_tz307) Alexandra Udriștoiu concurs Clasa 10 Probleme diverse Combinatorică Combinari Invers modular Programare dinamică Stars and Bars
Rezolvă

D-BitwiseParadise

#3838

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.

infoleague.net runda antrenament 2, problema D.

Fișiere Iacob Tudor (IacobTudor) Tudor Iacob concurs Clasa 10 Probleme diverse Combinatorică Programare dinamică Combinari Exponentiere rapida Invers modular Precalculare number theory Formula Operații pe biți
Rezolvă

Feast

#4687

Se dă un șir de \(N\) numere întregi. Să se aleagă maxim \(K\) secvențe disjuncte astfel încât suma elementelor incluse în secvențe să fie maximă.

NOISG 2019, problema 3

Consola Moldovan Robert (use KN) (moldovan_robert_lol) Zhang Guangxuan concurs Clasa 11 Probleme diverse Probleme diverse Relaxare lagrangiană Programare dinamică Greedy
Rezolvă

Cladire6

#4823

Se consideră un număr natural nenul N și o matrice cu N linii și coloane, numerotate de la 1 la N. Determinați numărul de modalități în care se poate ajunge de la elementul de coordonate (1,1) la cel de coordonate (N,N), cu condiția că, din elementul (i,j) se poate trece în ordice element (iv, jv), pentru care iv ≥ i, jv ≥ j.

Consola Moldovan Robert (use KN) (moldovan_robert_lol) medie Clasa 11 Programare dinamică Probleme de numărare Programare dinamică Sume parțiale
Rezolvă

best_sum2

#3881

Se dă un șir de N numere întregi indexat de la 1. Să se afle suma maximă a unui subșir format din T elemente astfel încât oricare 2 elemente consecutive ale acestuia să se afle la distanță cel mult K în șirul dat (distanța dintre elementele de pe pozițiile i și j, i < j, este j - i).

Consola Lorintz Alexandru (Alex_tz307) Alexandru Lorintz dificilă Clasa 11 Programare dinamică Probleme diverse de programare dinamică Programare dinamică Deque
Rezolvă

Sandale

#4568

Între timp, într-un univers paralel…

Ștefan Ghe este creatorul site-ului renumit de probleme de algoritmică InfoZona. Din păcate, verișorul său diabolic, Feștan Ț, punându-și în practică skill-urile de hacker nebunatic, a spart site-ul InfoZona și îl va da înapoi domnului Ștefan doar dacă reușeste să rezolve următoarea problemă:

Se dă un șir A, indexat de la 1, de N numere naturale nenule, reprezentând un raft de sandale. Vom defini funcția \( F(l,r) = ( \sum_{i=l}^{r} A[i] )^3 \) ca fiind costul pentru a cumpara sandalele din secvența [l, r] laolaltă, toate în același coș de cumpărături. Feștan Ț are K coșuri de cumpărături la dispoziție și dorește să afle care este prețul minim pe care poate cumpăra toate cele N sandale, folosind coșurile de cumpărături de care dispune.

Ajutați-l pe domnul Ștefan Ghe să-și recupereze site-ul rezolvând această problemă și vă va face cinste cu o bere și cinci cămile!

Consola Moldovan Robert (use KN) (moldovan_robert_lol) Robert Moldovan dificilă Clasa 11 Programare dinamică Probleme diverse de programare dinamică Programare dinamică divide et impera
Rezolvă

best_sum1

#3879

Se dă un șir de N numere întregi indexat de la 1. Să se afle subșirul de sumă maximă format din T elemente astfel încât oricare 2 elemente consecutive ale acestuia să se afle la distanță cel puțin K în șirul dat(distanța dintre elementele de pe pozițiile i și j, i < j, este j - i).

Consola Lorintz Alexandru (Alex_tz307) Alexandru Lorintz medie Clasa 11 Programare dinamică Probleme diverse de programare dinamică Programare dinamică Deque
Rezolvă

palixor

#3478

Se dă un şir format din n numere naturale nenule. Aflaţi câte subşiruri ale şirului dat au proprietatea că, folosind toate cifrele numerelor din subşir, cu ajutorul acestora se poate forma un palindrom.

Fișiere Bunget Mihai (mihaibun) Mihai Bunget dificilă Clasa 11 Programare dinamică Probleme diverse de programare dinamică Programare dinamică Metoda Gauss
Rezolvă

Magic Digits

#3821

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

infoleague.net etapa 1, problema 3.

Consola Iacob Tudor (IacobTudor) Cozma Tiberiu Ștefan concurs Clasa 11 Programare dinamică Probleme de numărare Combinatorica Programare dinamică ad-hoc
Rezolvă
Du-te sus!