Clasa a XI-a/Programare dinamică/Probleme diverse folosind programare dinamică (pagina 2)
Probleme diverse folosind programare dinamică · Probleme de informatică
Știai că! Pe InfoAs, problemele sunt atent selectate și verificate pentru a asigura o experiență de învățare optimă.
Subsir zig zag
Problemă medie din Colecția InfoAs
Dându-se un șir de numere naturale, să se găsească cel mai lung subșir de numere zig-zag din șir.
Rucsac 3
Problemă dificilă din Colecția InfoAs
Dându-se n obiecte, pentru fiecare cunoscându-se greutatea și valoarea, împreună cu o greutate gmax, să se determine valoarea maximă care se poate obține știind că se pot lua obiecte ale căror greutate adunată să nu depășească gmax.
Transformare palindrom
Problemă dificilă din Colecția InfoAs
Dându-se un șir de caractere, să se determine numărul minim de caractere ce trebuie inserate pentru a transforma șirul într-unul palindrom.
RecycleBin
Problemă dificilă din Olimpiada Județeană de Informatică 2020, clasele XI-XII
Se dă un șir de N numere întregi notat cu A. O operație constă în alegerea unei subsecvențe din șir și ștergerea acesteia. Pentru fiecare subsecvență din șir considerăm suma elementelor ei. Definim costul unui șir ca fiind maximul acestor sume, în cazul în care șirul conține cel puțin un număr pozitiv, altfel costul șirului este egal cu 0. Să se determine costul maxim posibil ce se poate obține dintr-un șir al mulțimii M.
Catalin si greselile
Problemă dificilă din Moisil++ 2016, clasele XI-XII
Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j cu o anumită proprietate. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară. Îl puteți ajuta pe Cătălin la întrebările lui?
Alee
Problemă dificilă din Olimpiada Locală de Informatică 2024, Brașov, clasa a XI-a
Constructorul Mihai are sarcină de la șeful său să construiască o alee de lungime N metri și lățime 4 metri, având la dispoziție plăci dreptunghiulare de dimensiune 1 x 2 metri. Curios din fire, acesta se întreabă în câte moduri diferite poate construi această alee.
Alee XII
Problemă dificilă din Olimpiada Locală de Informatică 2024, Brașov, clasa a XII-a
Constructorul Mihai are sarcină de la șeful său să construiască o alee de lungime N metri și lățime 4 metri, având la dispoziție plăci dreptunghiulare de dimensiune 1 x 2 metri. Curios din fire, acesta se întreabă în câte moduri diferite poate construi această alee.
Aiurea
Problemă dificilă din InfoAs PreOJI 2026, clasele XI-XII
Considerăm două șiruri s1 și s2, ambele de lungime n și formate doar din litere mici ale alfabetului englez. Ne propunem să vedem dacă printr-o serie de transformări, putem obține s2 din s1. Pentru a face acest lucru, putem aplica o operație de sortare(st, dr) de câte ori vrem, cu semnificația că valorile de pe pozițiile de la st la dr din șirul s1 se ordonează crescător lexicografic. Important este faptul că intervalele [st, dr] din cadrul operațiilor vor fi toate disjuncte două câte două. Operația de sortare(st, dr) are costul n - (dr - st + 1). Să se determine dacă se poate obține șirul s2 din s1 (posibil) folosind operațiile de sortare(st, dr), împreună cu cel mai mic cost posibil pentru a face acest lucru, în cazul în care se poate.
Descoji
Problemă dificilă din InfoAs PreOJI 2026, clasele XI-XII
Se dă un număr natural n. Câte șiruri binare (formate doar din 0 și 1) de lungime n există astfel încât să nu conțină trei cifre de 1 consecutive? Pentru că numărul poate să fie foarte mare, se cere răspunsul modulo 1.000.000.007.
Farfurii
Problemă dificilă din Cupa InfoAs, ediția 8
Ai devenit manager la un restaurant micuț din orașul tău. Ai așezat cele n mese în linie, iar la fiecare masă stă exact o persoană care mănâncă. Fiecare persoană are o farfurie. Când termină toți de mâncat, chemi chelnerii să colecteze farfuriile: aceștia încep de la masa numărul 1 și merg către ultima masă, n, colectând farfuriile cu o singură condiție: ultima farfurie pe care a colectat-o un chelner trebuie să fie cel puțin la fel de mare (în rază) ca și farfuria unui client pentru a o putea colecta; astfel, farfuriile mai mari stau deasupra celor mai mici în teancul pe care îl ține fiecare chelner și există siguranța de a nu scăpa vreuna. Să se determine numărul minim de chelneri necesari pentru a colecta toate farfuriile.
21 de probleme respectă filtrele.
Alege clasa Șterge