[Mảng 1 Chiều Cơ Bản]. Bài 11. Liệt kê và đếm số Fibonacci

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Java 12.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
28Tech
Problem type
Allowed languages
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng số nguyên A[] gồm N phần tử, hãy liệt kê các số trong mảng là số Fibonacci.


Đầu vào

Dòng đầu tiên là số nguyên dương N

Dòng thứ 2 gồm N số nguyên viết cách nhau một vài khoảng trắng


Giới hạn

1<=N<=10^6

0<=A[i]<=10^18


Đầu ra

In ra các số là số Fibonacci trong dãy theo thứ tự xuất hiện. Nếu trong mảng không tồn tại số Fibonacci nào thì in ra "NONE".


Ví dụ :

Input 01
6
1597 25358 7318 5878 0 2634
Output 01
1597 0

Comments

Please read the guidelines before commenting.



  • 0
    GodNona  commented on Feb. 2, 2025, 6:33 a.m.

    mn giúp e với ạ. E bị wrong answer 5 test ạ

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    ll a[1000006]; set<ll> se;

    int main() { iosbase::syncwith_stdio(0); cin.tie(NULL);

    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    ll f1 = 0, f2 = 1;
    se.insert(f1);
    se.insert(f2);
    for(int i = 3; i <= 92; i++)
    {
        ll f3 = f1 + f2;
        se.insert(f3);
        f1 = f2;
        f2 = f3;
    }
    
    int check = 0;
    for(int i = 0; i < n; i++)
    {
        if(se.find(a[i]) != se.end())
        {    
            cout << a[i] << " ";
            check = 1;
        }
    }
    if(check == 0)
        cout << "NONE";
    
    
    return 0;
    

    }


  • -3
    VDev  commented on Jan. 18, 2025, 3:52 p.m. edited

    FULL AC

    #include <bits/stdc++.h>
    #include <iomanip>
    #include <cmath>
    #include <climits>
    #define ll long long
    using namespace std;
    ll a[10000011];
    ll cnt = 0;
    ll fi(ll n){
        ll f[100];
        f[0] = 0, f[1] = 1;
            for(ll i = 2; i <= 92; i++){
            f[i] = f[i - 1] + f[i - 2];
            }
            for(ll i = 0; i <= 92; i++){
            if(n == f[i]){
                return true;
            }
            }
            return false;
    }
    int main(){
        ll n;
        cin >> n;
        for(ll i = 0; i < n; i++){
            cin >> a[i];
        }
        for(ll i = 0; i < n; i++){
                if(fi(a[i])){
                    cout << a[i] << " ";
                }else cnt++;
        }
        if(cnt == n) cout << "NONE";
        return 0;
    }
    

  • 0
    khiem101701  commented on Dec. 3, 2024, 10:14 a.m.

    include <iostream>

    using namespace std; long long fibo[101];

    void fibonacci(long long f[]){ f[0] = 0; f[1] = 1; for (int i = 2;i < 101;i++){ f[i] = f[i-1]+f[i-2]; } } int main(){ fibonacci(fibo); int n; cin>>n; long long arr[n]; for (int i = 0; i< n;i++){ cin>>arr[i]; } bool flag = true; for (int i = 0;i < n;i++){ for(int j = 0;j < 101;j++){ if(arr[i] == fibo[j]){ cout<<arr[i]<<" "; flag = false; break; } } } if(flag) cout<<"NONE"; return 0; }


  • 0
    Dungx_2008  commented on Nov. 24, 2024, 10:07 a.m.

    include <bits/stdc++.h>

    define N 10000000

    define ll long long

    using namespace std; ll f[100],a[N],n; bool kt = true; set<ll> se; void fibo() { f[0] = 0; f[1] = 1; se.insert(0); se.insert(1); for(int i=2;i<=92;i++) { f[i] = f[i-1] + f[i-2]; se.insert(f[i]); } } int main() { fibo(); cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) { if(se.find(a[i]) != se.end()) { cout << a[i] << " "; kt = false; } } if(kt) cout << "NONE"; return 0; }


  • 0
    HungDSQ2  commented on Nov. 1, 2024, 9:35 a.m.

    có code k ae


  • -4
    thainguyen2802  commented on June 16, 2024, 10:44 a.m.

    Mình dùng mảng số fibo bị tle 2 test cuối, ai có cách khác tối ưu hơn không ạ?


    • 0
      kytoLam  commented on Oct. 26, 2024, 9:07 a.m.

      có thể dùng binary search để tìm nha bạn, mà linear cũng đâu TLE đâu ta


    • 1
      thaomy  commented on June 18, 2024, 2:30 p.m.

      mình thấy dùng được mà bạn

      include <stdio.h>

      long long Fi(long long n){ long long F[100]; F[0]=0, F[1]=1; for(int i=2; i<93; i++){ F[i]=F[i-1]+F[i-2]; } for(int i=0; i<93; i++){ if(n==F[i]) return 1; } return 0; } int main() { long long N; scanf("%lld", &N); long long A[N]; for(long long i=0; i<N; i++){ scanf("%lld", &A[i]); } long long res=0; for(long long i=0; i<N; i++){ if(Fi(A[i])==1) printf("%lld ", A[i]); else res++; } if(res==N) printf("NONE");

      }