pb #2904 de pe pbinfo
Cerința
Se dă un număr natural n. Să se determine dacă numărul se poate scrie ca sumă de două numere triunghiulare.
Dacă este posibil se vor afișa două numere triunghiulare a căror sumă este egală cu n, în orice ordine, respectiv mesajul NU în caz contrar.
Un număr triunghiular este numărul de puncte dintr-un triunghi echilateral umplut uniform cu puncte. De exemplu, 1, 3, 6, 10, 15 sunt numere triunghiulare.
Date de intrare
Programul citește de la tastatură numărul n.
Date de ieșire
Programul va afișa pe ecran, în orice ordine, două numere triunghiulare care însumate dau numărul n, separate printr-un spațiu, sau mesajul NU dacă numărul nu poate fi scris ca suma de două numere triunghiulare.
Restricții și precizări
n ≤ 10^12;
numerele triunghiulare determinate pot fi identice.
Exemplul 1:
Intrare
24
Ieșire
3 21
Exemplul 2:
Intrare
15
Ieșire
NU
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
long long n, aux;
int main()
{
cin >> n;
long long left = 1, right = n;
for(int i = 1; i <= right; i++) {
if(1LL * i * (i + 1) / 2 > n) { // am folosit 1LL deoarece i * (i + 1) / 2 poate sa fie long long, si long long nu poate fi stocat de acel if daca noi nu ii zicem dinainte ca este long long, si de accea 1LL atentioneaza if-ul ca avem un rezultat long long
right = i;
break;
}
}
while(left <= right) {
aux = left * (left + 1) / 2 + right * (right + 1) / 2;
if(aux == n) {
cout << left * (left + 1) / 2 << " " <<right * (right + 1) /2;
return 0;
}
if(aux > n) {
right--;
} else if(aux < n) {
left++;
}
}
cout <<"NU";
return 0;
}
Explicație:
Formula unui numar triangular este n * (n + 1) / 2, n fiind sursa de unde provine numarul triangular, de exemplu sursa lui 15 este 5
Generam primele n numere triunghiulara pana la n, pentru a stii la ce indice ne oprim, apoi folosim un fel.. de cautare binara
In aceasta "cautare binara" folosim urmatoarea idee
Stanga va fi egal cu 1, ca e inceputul, iar Dreapta va fi egala cu indicele calculat de noi mai sus
Cat timp Stanga <= Dreapta incepem cautarea, daca sursele noastre(stanga + dreapta) au alcatuit numarul nostru triangular , ne oprim si AFISAM NUMERELE TRIANGULARE, atentie, nu sursele! adica st * (st + 1) / 2 si dr * (dr + 1) / 2. Daca nu verificam, numarul format este mai mare ca n? daca e mai mare inseamna ca sursa dreapta e mult prea mare si o micsoram cu 1, daca numarul format e mai mic, inseeamna ca sursa dreapta e deja la maximul ei, si noi tot ce putem face e sa incrementam sursa stanga pentru a incerca sa obtinem rezultatul dorit.
Intr-un final, daca nimic nu s-a intamplat, si programul inca functioneaza inseamna ca numarul nu e triangular si afisam NU