Muszę się poprawić, poprzedni algorytm zwracał błędne wyniki dla ok 1‰ przypadków (ok 0.8 na tysiąc), tutaj wersja poprawiona
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iterator>
#include <vector>
int primes[] = {
6337,9067,6551,6323,8609,9677,7907,9343,9803,7561,11411,10657,6607,9689,10457,
9277,11369,9907,7297,8681,10477,8443,9973,10589,10957,7039,7307,9749,9349,6907,
10427,10709,11471,11087,8263,6151,6581,8009,10613,7589,9173,8647,8117,10781,
8093,7487,9227,11299,7901,9049,7393,6397,9421,7963,8171,6793,8929,9871,8011,
10091,8893,11159,8237,6857,10177,11399,8887,6599,8039,9319,8863,8963,10847,
6737,8123,9439,11383,11171,7759,9601,10753,9791,9661,10253,11503,10883,6997,
6521,8731,8761,9833,6977,8377,10247,6971,8527,7789,9161,10529,11621,8017,7127,
8719,10259,7549,8821,8699,11149,8167,8707,10141,11083,7187,9187,10729,7867,6317,
6679,6961,6991,9091,11527,9629,7207,9739,9157,7793,10007,9311,10711,8147,8161,
8623,8629,8369,7643,6871,7459,10267,6761,9433,10597,7829,7541,10459,7457,7699,
11467,7517,11329,6359,10631,8287,10301,7877,10099,6361,8521,7937,8663,9901,9109,
9403,8291,10343,8363,10453,6863,8353,7499,6733,7559,6389,6911,8389,6689,10303,
10739,10837,6967,8233,8111,9059,8599,10771,11497,8971,6829,9613,6673,7109,8447,
9203,10333,6473,6311,8501,6299,7069,8311,7639,7213,6959,8779,6637,8089,9199,
11273,9257,10111,7333,10987,6427,11251,7727,6709,7951,9631,10889,10313,6659,
10601,6247,8467,7417,11047,8677,11239,7321,9769,10973,11587,6691,6269,9413,
11003,7369,10501,6197,7577,9859,7433,8689,9397,11597,9001,10867,8839,11161,
10321,7591,8693,11549,10331,10133,7253,8293,11113,10103,11593,7219,7919,8209,
};
static_assert(std::size(primes) > 256);
template<typename T>
class simple_2d_matrix_view
{
T* data_;
size_t width_;
size_t height_;
public:
simple_2d_matrix_view(T* ptr, size_t h, size_t w):
data_{ptr},
width_{w},
height_{h}
{}
size_t width() const { return width_; }
size_t height() const { return height_; }
T& operator()(size_t h, size_t w) {
assert(w < width_);
assert(h < height_);
return data_[width_ * h + w];
}
T const& operator()(size_t h, size_t w) const {
return const_cast<simple_2d_matrix_view&>(*this)(h, w);
}
};
int sign(std::vector<int> const& vec)
{
int cnt = 0;
for(int i = 0; i < vec.size(); i++)
for(int j = i + 1; j < vec.size(); j++)
if (vec[i] > vec[j]) cnt++;
return cnt % 2 == 0 ? 1 : -1;
}
long long matrix_det(simple_2d_matrix_view<int> v)
{
assert(v.height() == v.width());
long long det = 0;
std::vector<int> indices(v.width());
std::iota(indices.begin(), indices.end(), 0);
do {
long long val = 1;
for(int x = 0; x < v.height(); x++) {
int y = indices[x];
val *= v(x, y);
}
det += val * sign(indices);
} while(std::next_permutation(indices.begin(), indices.end()));
return det;
}
bool is_palindromic(int val)
{
std::stringstream conv;
conv << val;
std::string tested = conv.str();
if (tested.size() == 1)
return true;
if (tested.size() == 2)
return tested.front() == tested.back();
std::vector<int> matrix(std::begin(primes), std::end(primes));
matrix.resize(tested.size() * tested.size());
simple_2d_matrix_view<int> v(matrix.data(), tested.size(), tested.size());
for (int i = 0; i < tested.size(); i++)
v(0, i) = tested[i] - '0';
for (int i = 0; i < tested.size(); i++)
v(tested.size() - 1, tested.size() - 1 - i) = tested[i] - '0';
return matrix_det(v) == 0;
}
int main()
{
int val;
if (!(std::cin >> val))
return 1;
if (is_palindromic(val) == 0)
std::cout << "TAK\n";
else
std::cout << "NIE\n";
}