HDU - 5166 - Missing number && 5167 - Fibonacci

Missing number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 430    Accepted Submission(s): 233

Problem Description There is a permutation without two numbers in it, and now you know what numbers the permutation has. Please find the two numbers it lose.  

Input There is a number  T  shows there are  T  test cases below. ( T≤10 )

For each test case , the first line contains a integers  n  , which means the number of numbers the permutation has. In following a line , there are  n  distinct postive integers.( 1≤n≤1,000 )  

Output For each case output two numbers , small number first.  

Sample Input

2
3
3 4 5
1
1
        

Sample Output

1 2
2 3
        

Source BestCoder Round #28  

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int vis[1005];

int main() {
	int T, n;
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		memset(vis, 0, sizeof(vis));
		int m = n + 2, a, b, flag = 1;
		while(n--) {
			scanf("%d", &a);
			vis[a] = 1;
		}
		for(int i=1; i<=m; i++) {
			if(!vis[i] && flag == 1) {
				a = i; flag = 2;
			}
			else if(!vis[i] && flag == 2) {
				b = i; break;
			}   
		}
		printf("%d %d\n", a, b);
	}
	return 0;
} 
           

Fibonacci

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1312    Accepted Submission(s): 328

Problem Description Following is the recursive definition of Fibonacci sequence:

Fi=⎧⎩⎨01Fi−1+Fi−2i = 0i = 1i > 1

Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.  

Input There is a number  T  shows there are  T  test cases below. ( T≤100,000 )

For each test case , the first line contains a integers n , which means the number need to be checked. 

0≤n≤1,000,000,000  

Output For each case output "Yes" or "No".  

Sample Input

3
4
17
233
        

Sample Output

Yes
No
Yes
        

Source BestCoder Round #28

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#define LL long long
using namespace std;

const int MAX = 1000000010L;
LL fibo[50] = {0, 1};
map<LL, bool> ma;

void init() {
	queue<LL> q;
	int flag;
	for(int i=2; i<50; i++) {
		fibo[i] = fibo[i-1] + fibo[i-2];
		if(fibo[i] > MAX) {
			flag = i; break;
		}
	}
	
	for(int i = 0; i < flag; i++) {
		q.push(fibo[i]); ma[fibo[i]] = true;
	}
	
	while(!q.empty()) {
		LL tmp = q.front();
		q.pop();
		for(int i = 2; i <= flag; i++) {
			LL t = tmp*fibo[i];
			if(t > MAX) break;
			if(ma[t]) continue;
			else {
				ma[t] = true;
				q.push(t);
			}
		}
	}
}

int main() {
	init();
	LL T, n;
	cin >> T;
	while(T--) {
		cin >> n;
		if(ma[n]) printf("Yes\n");
		else printf("No\n");
	} 
	return 0;
}