Pat grade b-b1005 continue (3n+1) guess score (25) [map solve]

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>
#include<map>
using namespace std;
// utilize map Automatic sorting and find() Characteristics , Completely eliminate elements and output from large to small  
//1、 use map Store positive integers to be verified （1<n<=100),map It can be sorted from large to small  
//2、 Traverse map Take out a number , Start validation , use iscal[] Whether the record has been verified .
//2.1、 It may be greater than 100, for example (99*3+1)/2 >100, At this time, it is impossible to map in 
//2.2、 utilize iscal[], If it has been verified, it is not necessary to eliminate it , Such as verification 3 when ,
//5、8、4、2、1 Again iscal[] The middle is true, There is no need to eliminate 
//2.3、 You can use map.find() and map.erase() To operate 
//3、 because map Sort from large to small , Output directly after traversal verification  

bool iscal[101];// Record whether it has been calculated 
//map Sort from large to small , Store the positive integer to be verified  
map<int, bool, greater<int>> table;
int main(){
	int k,n;
	cin >> k;
	for(int i = 0; i < k;++i){
		cin >> n;
		table[n] = true;// Put in map 
	}
	for(auto it = table.begin(); it != table.end(); ++it){
		int t = it->first;
		while(t /2 != 1){ 
			if(t & 1) t = (3 * t + 1)/2; // If it's an odd number  
			else t /=2;
			if(t > 100) continue; // Greater than 100 There is no need to eliminate and record  
			if(iscal[t]) break; //false when , Indicates that it has not been verified , You can find and eliminate  
			iscal[t] = true; 
			map<int,bool> :: iterator pt = table.find(t); // Find and cull  
			if(pt != table.end()) table.erase(pt);
		} 
	}
	auto it = table.begin();
	cout << it->first;// Output the first element , And there is at least one output  
	it++;
	while(it != table.end()){// Subsequent elements, if any , Then output the space first and then the element  
		cout << " " << it->first;
		it++;
	}
	return 0; 
}