Pat b-b1005 continue (3n+1) guess (25) [array]

Karaz (Callatz) The conjecture is already in 1001 A description of . In this topic , It's a little more complicated .

When we test karaz's conjecture , To avoid double counting , You can record every number encountered in the recursion process . For example  n=3  When it comes to validation , We need to calculate 3、5、8、4、2、1, When we're dealing with  n=5、8、4、2 When it comes to validation , Karaz can directly guess whether it is true or not , It doesn't have to be repeated , Because of this 4 The number has been verified 3 When I met , We call 5、8、4、2 Be being 3“ Cover ” Number of numbers . We call a number in a sequence  n  by “ Key number ”, If  n  Cannot be covered by other numbers in the sequence .

A given set of numbers is now to be verified , We just need to verify a few of these key numbers , You don't have to double check the rest of the numbers . Your job is to find out these key numbers , And output them in descending order .

Input format ：

Each test input contains 1 Test cases , The first 1 The row gives a positive integer  K (<100), The first 2 Line is given  K  Positive integers that are not identical to each other  n (1<n≤100) Value , The numbers are separated by spaces .

Output format ：

The output of each test case takes up one line , Output key numbers in descending order . Digital inter use 1 Space between , But there is no space after the last number in the line .

sample input ：

6
3 5 6 7 8 11

sample output ：

7 6

#include<iostream>
using namespace std;
// Using arrays to solve , Verification and output require traversal checks 
//1、table[] Store the positive integer to be verified , And use idx Record the maximum positive integer ;
//2、  from idx~2 Traverse table[], And start verifying  
bool iscal[101], table[101];
int main(){
	int k,n, idx = -1; //idx Record the maximum positive integer  
	cin >> k;
	for(int i = 0; i < k; ++i){
		cin >> n;
		if(idx < n) idx = n;// Record the maximum positive integer  
		table[n] = true; //  Put in table[] 
	}
	for(int i = idx; i >1; --i)
		if(table[i]){ //true when , That is, in the table  
			int t = i;
			while(t != 1){// Start validation  
				if(t & 1) t = (t * 3 + 1)/2; // Odd number  
				else t /=2;
				if(t > 100) continue; // Greater than 100 No operation is necessary  
				if(iscal[t]) break; //  Verified , There is no need to operate and verify  
				table[t] = false; // Perform table output  
				iscal[t] = true;// The record has been verified  
			}
		}
	while(!table[idx] && idx > 1) idx--; // Find the largest positive integer again  
	cout << idx;// First bit output  
	for(int i = idx -1; i >1; --i) // First output spaces and then positive integers  
		if(table[i]) cout << " " << i;
	return 0;
}