228
Cerința
Se citesc pe rând numere naturale nenule. Să se determine câte din numerele citite sunt termeni ai șirului lui Fibonacci.
Date de intrare
Fișierul de intrare cautafibo.in
conține numere naturale nenule, separate prin spații.
Date de ieșire
Fișierul de ieșire cautafibo.out
va conține o singură valoare, reprezentând numărul termenilor Fibonacci care se regăsesc în fișierul de intrare.
Restricții și precizări
- numerele din fișierul de intrare vor avea cel mult
10
cifre - fișierul de intrare va conține cel mult
100.000
de numere naturale nenule
Exemplu
cautafibo.in
5 10 89 1 7 9 8 1 6 55 19 13 55
cautafibo.out
8
Explicație
Numerele Fibonacci din fișierul de intrare sunt: 5 89 1 8 1 55 13 55
#include <bits/stdc++.h> using namespace std; ifstream cin("cautafibo.in"); ofstream cout("cautafibo.out"); unsigned long long a[55] , cnt; int n; void fib() { a[1] = 1 , a[2] = 1; for(n = 3 ; a[n - 1] <= 10000000001ll ; n++) a[n] = a[n - 1] + a[n - 2]; } int main() { fib(); long long x; while(cin >> x) { unsigned long long st = 0 , dr = n - 1 , poz = -1; while(st <= dr) { int m =(st + dr)/2; if(x <= a[m]) { poz = m; dr = m - 1; } else st = m + 1; } if(a[poz] == x) cnt++; } cout << cnt; }
Comentarii