Cerința

Să se determine numărul de șiruri de lungime 2 * n care conțin paranteze închise corect.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran restul împărțirii numărului de șiruri de lungime 2 * n, care sunt parantezate corect, la 666013.

Restricții și precizări

1 ≤ n ≤ 1000

Exemplu

Intrare

Ieșire

Explicație

((())), ()(()), ()()(), (())(), (()()).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema NumarParanteze:

#include <iostream>

#define MAX_N 1000
#define MOD 666013

int C[MAX_N + 1];

int catalan(int n) {
  if (C[n]) {
    return C[n];
  }
  int q = 0;
  long long tmp;
  for (int i = 0; i < n; i++) {
    tmp = q + 1LL * catalan(i) * catalan(n - i - 1);
    q = tmp % MOD;
  }
  C[n] = q;
  return q;
}

int main(void) {
  int n;

  std::cin >> n;
  C[0] = 1;
  std::cout << catalan(n) << '\n';
  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1257 NumarParanteze

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1257 NumarParanteze de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1257 NumarParanteze