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

Lista de probleme 8

Filtrare

Mai multe opțiuni

#1958 MPalind

TH este foarte pasionat de șiruri palindromuri. El are un șir de caractere ce conține litere ale alfabetului englezesc A, indexat de la 1 și își pune M întrebări de forma: “Pentru x și y, în câte moduri pot împărți șirul A[x...y] în secvențe palindrom? Acest număr poate fi foarte mare, așa că mă mulțumesc cu rezultatul modulo 666013”.

Rezolvă

#3784 SubsirPalindromMaximal

Fie un șir de n litere mici. Să se determine lungimea maximă a unui subșir care este palindrom.

Folclorul informatic

Rezolvă

#3888 PalSplit

Avem un vector de n elemente naturale nenule. O operație constă în alegerea unei subsecvențe (elemente adiacente) palindromice și eliminarea ei din vector, în urma eliminării elementele rămase se vor restrânge. Care este numărul minim de operații necesar pentru a elimina toate elementele?

codeforces, Div1. #336

Rezolvă

#2293 mxt

Se consideră un șir de numere naturale a[1], a[2], …, a[n]. Asupra șirului efectuăm n operații. O operație constă din eliminarea unuia din numerele de la capetele șirului. Deci la primul pas se elimină fie a[1], fie a[n]. Dacă la pasul i se elimină elementul a[k], atunci costul eliminării este i * a[k]. Să se determine costul maxim posibil total al celor n operații.

Folclorul informatic

Rezolvă

#2862 stiva2

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

ONI 2008 Baraj

Rezolvă

#2137 nunta1

În fața palatului Prințesei Mofturoase se află n pețitori așezați la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre prețioase pe care dorește să le ofere prințesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prințesa a decis să-i determine ca n-1 dintre ei să renunțe în chip pașnic, pețitorul rămas devenind alesul prințesei (indiferent de numărul de pietre prețioase deținute de acesta). Doi pețitori vecini la coadă se pot înțelege între ei astfel: cel care are mai puține pietre prețioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre față de câte avea. Dacă doi pețitori au același număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său. Un pețitor se poate înțelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui pețitor, toți cei din spatele lui avansează.

Fie P numărul de pietre prețioase pe care le are pețitorul care va deveni alesul prințesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

OJI 2002

Rezolvă

#2470 zuma

Se dă un șir de caractere de lungime N format din litere mari ale alfabetului englez și un număr întreg K. Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin K având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime 0) sau șirul nu mai conține subsecvențe de lungime cel puțin K cu toate elemente egale.
Cunoscând N, K și șirul de caractere, să se determine care este lungimea minimă la care poate fi redus șirul după aplicarea operațiilor într-un mod convenabil.

ONI 2018 clasele XI-XII

Rezolvă

#3221 mean

George este un mare iubitor al informaticii, dar este încă la început și de aceea are nevoie de ajutorul vostru. La ora de informatică profesoara scrie pe tablă N numere naturale, iar la fiecare pas George trebuie sa aleagă două numere de pe poziții consecutive și să le înlocuiască cu un singur număr egal cu partea întreagă a mediei lor aritmetice. George trebuie să facă aceste înlocuiri până când mai rămâne pe tablă doar un număr. Ajutați-l pe George sa afle care este cel mai mare număr care poate fi obținut la final.

info(1)cup 2019, Runda națională

Rezolvă