[Mảng 1 Chiều Cơ Bản]. Bài 11. Liệt kê và đếm số Fibonacci
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Java
12.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
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; }
có code k ae
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 ạ?
có thể dùng binary search để tìm nha bạn, mà linear cũng đâu TLE đâu ta
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");
}