Mate la alt nivel

Problema #3188 Mate (pbinfo)

Cerința

Iarina a auzit la ora de matematica de numere triangulare.

Un numar se numeste triangular daca se scrie ca suma primelor k numere naturale. Doamna profesoara le-a propus sa rezolve pentru acasa urmatoarea problema: Determinati toate numerele triangulare care sunt patrate perfecte.

Iarina va roaga sa o ajutati sa rezolve aceasta problema: Se da o valoare n sa se afiseze primele n numere naturale triangulare care sunt patrate perfecte.

Date de intrare

Fișierul de intrare mate.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire mate.out va conține numerele specificate in cerinta.

Restricții și precizări

• 1 ≤ n ≤ 10

Exemplu

mate.in 2

mate.out 1 36

Explicație

În fișierul de intrare sunt afisate 2 numere care sunt atat numere triangulare cat si patrate perfecte.

Ne folosim de faptul ca numerele triunghiulare care sunt si patrate perfecte se calculeaza dupa urmatoarea formula recurenta:

n[0]=0

n[1]=1

n[k] = 34 * n[k-1] – n[k-2]+2;

Rezolvare simpla folosind C++;

 

#include<fstream>

using namespace std;
ifstream cin("mate.in");
ofstream cout("mate.out");

long long ntpp(long long x) {
   if (x==0) return 0;
   if (x==1) return 1;
   return 34 * ntpp(x-1) - ntpp(x-2)+2;
}

int main()
{
   long long n; cin >> n;
   long long i=0, j=1;
   do{
      cout<<ntpp(j)<<" ";
      i++;j++;
   }while(i<n);
cin.close(); cout.close();
return 0;
}

Nimeni nu te poate opri sa te gandesti si la o alta solutie, tinand cont de faptul ca la precizarile speciale din textul problemei gasesti faptul ca n are un numar finit de valori.

#include <fstream>

using namespace std;
ifstream cin("mate.in");
ofstream cout("mate.out");

long long response[] = {1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056,1882672131025, 63955431761796, 2172602007770041};

int main()
{
   int n;cin>>n;
   for (int i=0; i<n; i++) {
      cout<<response[i]<<" ";
   }

cin.close(); cout.close();
return 0;
}