1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <iostream>
#include <vector> // for Fibonacci numbers, random access is required
#include <set> // for multiplications of Fibonacci numbers

using namespace std;

// function to calculate Fibonacci numbers in given range
void calculateFibonacciNumbers(vector<unsigned int>& numbersOfFibonacci, unsigned int maxValue) {
	// set init values
	// F0 equals 1 to not repeating it in list
	unsigned int valueF0 = 1;
	unsigned int valueF1 = 1;
	// temporary value to hold F0 value in calculations
	unsigned int tmpF = 0;
	// insert first Fibonacci number
	//numbersOfFibonacci.push_back(0);
	// calculate Fibonacci number until it will be greater than max value
	while (valueF1 < maxValue) {
		numbersOfFibonacci.push_back(valueF1);
		tmpF = valueF0;
		valueF0 = valueF1;
		valueF1 += tmpF;
	}
}

// function to calculate multiplications of given Fibonacci numbers
void calculateMultiplicationsOfFibonacciNumbers(set<unsigned int>& multiplicationsOfFibonacciNumbers, vector<unsigned int>* numbersOfFibonacci) {
	// auxiliary iterators to limit range of Fibonacci numbers
	// for rows:
	vector<unsigned int>::iterator rowMinValue = numbersOfFibonacci->begin();
	vector<unsigned int>::iterator rowMaxValue = numbersOfFibonacci->end() - (unsigned int)(numbersOfFibonacci->size()/2);
	vector<unsigned int>::iterator rowIndex;
	// for columns:
	vector<unsigned int>::iterator colMinValue = numbersOfFibonacci->begin();
	vector<unsigned int>::iterator colMaxValue = numbersOfFibonacci->end();
	vector<unsigned int>::iterator colIndex;
	// calculate multiplications without duplications
	// and values greater than max value of input vector
	// input value 0 separately
	multiplicationsOfFibonacciNumbers.insert(0);
	for (rowIndex = rowMinValue; rowIndex != rowMaxValue; ++rowIndex) {
		// chech if all numbers will calculate
		if (colMinValue == colMaxValue) break;

		for (colIndex = colMinValue; colIndex != colMaxValue; ++colIndex) {
			multiplicationsOfFibonacciNumbers.insert( (*rowIndex) * (*colIndex) );
		}

		// change range of columns
		colMinValue++;
		colMaxValue--;
	}
}

int main(int argc, char* argv[]) {

	// get number of data
	unsigned int numberOfData = 0;
	cin >> numberOfData;

	// read all data
	// if input vector is greater than 1000 then
	// calculate all multiplications of Fibonacci numbers
	// in range 0 to 10^9 -> it is 946 combinations
	// otherwise during reading input vector search
	// for the greatest value and calculate multiplications
	// in range 0 to this value
	unsigned int* dataInVector = new unsigned int[numberOfData];
	unsigned int greatestValue = 0;
	if (numberOfData > 1000) {
		for (unsigned int i = 0; i < numberOfData; ++i) {
			cin >> dataInVector[i];
			if (dataInVector[i] > greatestValue) {
				greatestValue = dataInVector[i];
			}
		}
	} else {
		greatestValue = 1000000000; // 10^9
		for (unsigned int i = 0; i < numberOfData; ++i) {
			cin >> dataInVector[i];
		}
	}

	// variables for Fibonacci numbers and them multiplications
	vector<unsigned int> numbersOfFibonacci;
	set<unsigned int> multiplicationsOfFibonacciNumbers;

	// calculate those values
	calculateFibonacciNumbers(numbersOfFibonacci, greatestValue);
	calculateMultiplicationsOfFibonacciNumbers(multiplicationsOfFibonacciNumbers, &numbersOfFibonacci);

	// check if input values are Fibonacci numbers
	// and display proper information
	for (unsigned int i = 0; i < numberOfData; ++i) {
		if (multiplicationsOfFibonacciNumbers.find(dataInVector[i]) != multiplicationsOfFibonacciNumbers.end()) {
			cout << "TAK" << endl;
		} else {
			cout << "NIE" << endl;
		}
	}

	// clear used data
	delete dataInVector;

	return 0;
}