Lista de probleme 720

Filtrare

#3971 sss

Vi se dau două numere naturale n, m și două șiruri de numere naturale A și B. Șirul A are n elemente, fiecare din intervalul [1, m], în timp ce șirul B are m elemente, fiecare din intervalul [1, n]. Scrieți un program care determină un subșir nevid al lui A și un subșir nevid al lui B care au aceeași sumă a elementelor.

Scrie un program care pentru un număr natural nenul n, găsește numărul de secvențe de numere naturale nenule a1, a2, a3,..., an, astfel încât a1 * a2 * a3 *...* an = a1 + a2 + a3 +...+ an și a1 ≥ a2 ≥ a3 ≥...≥ an.

Turneul Internațional Shumen 2021

#3969 pretty

Azi este ziua secvenței! Profesoara de mate a scris câteva secvențe pe tablă, fiecare având N numere distincte cuprinse între 1 și N, și le-a spus studenților că aceste secvențe au o proprietate specială. După o analiză atentă, Deni, una din studente, a ghicit corect proprietatea. Toate secvențele de pe tablă au cel puțin o pereche de numere adiacente de forma (x, x+1). Deni a fost așa de fericită încât a denumit acest tip de secvențe drăguțe. Scrieți programul care pentru un N dat trebuie să-i spună lui Deni care este numărul de secvențe drăguțe. Acest număr poate fi foarte mare, așa că trebuie calculat modulo M.

#3963 maxq

Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector V cu N numere întregi (numerotate de la 0 la N - 1) şi poate efectua următoarele operaţii:

  • schimbarea elementului de pe poziţia p cu un alt număr întreg;
  • aflarea subsecvenţei de sumă maximă din V inclusă între indicii a şi b;

Studii recente arată că într-adevăr există viață inteligentă pe Marte. Problema de acum este că omenirea se află în război cu Marțienii și cea mai bună strategie pentru noi este să atacăm primii. Pe Marte se află un sistem de cale ferată complex alcătuit din N orașe conectate de M căi ferate bidirecționale.

Omenirea a apelat la cel mai mare bombardier posibil, domnul RANDy, ca să distrugă căile ferate. Pentru că este un maniac, el mai are doar o bombă disponibilă, deci va putea ținti doar o cale ferată. RANDy va ținti doar căile ferate strategice. O cale ferată este strategică dacă și numai dacă există o pereche de orașe (x, y) astfel încât să putem ajunge de la x la y și după bombardarea acesteia, să nu mai poți ajunge de la x la y.

Marțienii încep să se prindă de planul nostru, așa că încep să construiască Q noi căi ferate. După fiecare cale ferată nou adăugată, RANDy vrea să știe câte căi ferate strategice există. El este în dubii, și vă cere ajutorul.

Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] < b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un șir s de caractere vom nota cu m(s) subșirul maxim lexicografic al lui s, și cu v(s) = |m(s)| lungimea acestui subșir. Felicia vă dă un șir s format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue s' ale lui s. Felicia vrea să calculați suma valorilor v(s') pentru toate subsecvențele posibile s' amintite anterior

Concursul Național Info Pro, Etapa II

Să se determine toate partițiile disjuncte ale mulțimii A={1,2,3,...,n}, formate din submulțimi cu exact m elemente.

Fie n un număr natural nenul și mulțimea A={1,2,3,...,n}.

Să se afişeze toate partițiile disjuncte ale mulțimii A într-un timp eficient folosind memoria eficient.

Problemă luată de la Carmen Minca, modificată puțin

Fie n un număr natural nenul, mulțimea A={1,2,3,...,n} și un număr m, 1 ≤ m ≤ n. Să se determine toate partițiile disjuncte ale mulțimii A, formate din submulțimi cu exact m elemente.

Avem la dispoziție oricâți căței și oricâte pisici, câte așezări ale acestora în linie dreaptă de lungime n există astfel incât să nu avem o pisică între 2 căței și configurația să înceapă cu un câine și să se termine cu o pisică? Răspunsul se afișează modulo \(10^9+7\).