// определить максимальное количество полож (отриц) коэффициентов
// разобраться с int(coeff.size()



#include <string>
#include <cassert>
#include <iostream>
#include <fstream>
#include <list>
#define MAX_coeff 100  
#define MAX_polynom_size (2 * MAX_coeff + 1)

template <typename p_type> 
class polynom
{
public:
  p_type coefficients[MAX_polynom_size];  
  polynom() 
  {
    int i;
    for(i = 0; i < MAX_polynom_size; i++)
      coefficients[i] = p_type(0);
  }
// beg_num - это степень, с которой начинаем. Если beg_num = 0, то самый младший коэффициент будет при q^0
  polynom(list<p_type> coeff, int beg_num = -MAX_coeff)
  {
    int i;
    typename list<p_type>::iterator it;
    
    // Проверка, что начало интервала коэффициентов попадает в допустимый интервал 
    assert((-MAX_coeff <= beg_num) && (beg_num <= MAX_coeff));

    // Проверка, что конец интервала коэффициентов попадает в допустимый интервал (коэффициенты в том числе нулевые) 
    //  here was error
    //  cout << "bg=" << beg_num << " cs=" << coeff.size() << " " << beg_num + coeff.size() << " " << 
    //  beg_num + int(coeff.size()) << "\n";

    assert(beg_num + int(coeff.size()) <= MAX_polynom_size);
    
    for(i = 0; i < MAX_polynom_size; i++)
      coefficients[i] = p_type(0);
    
    for(i = MAX_coeff + beg_num, it = coeff.begin(); it != coeff.end(); it++, i++)
      coefficients[i] = *it;
  }
  int get_min_coefficient()
  {
    int i;
    for(i = 0; i < MAX_polynom_size; i++)
      if(coefficients[i] != 0)
        break;
    return i;
  }
  int get_max_coefficient()
  {
    int i;
    for(i = MAX_polynom_size - 1; i >= 0; i--)
      if(coefficients[i] != 0)
        break;
    return i;
  }
};

template <typename p_type> 
ostream& operator<<(ostream& o, polynom<p_type> p)
{
  int i;
  o << "[";
  for(i = 0; i < MAX_polynom_size; i++)
    if(p.coefficients[i] != 0)
    {  o << " + (" << p.coefficients[i] << ")*q^{";
       if((i - MAX_coeff) % 2 == 0)
         o << (i - MAX_coeff)/2 << "}";
       else
         o << (i - MAX_coeff) << "/2" << "}";
    }
  o << "]";
  return o; 
}

template <typename p_type> 
polynom<p_type> operator-(polynom<p_type> p)
{
  int i;
  polynom<p_type> res;
  for(i = 0; i < MAX_polynom_size; i++)
    res.coefficients[i] = -p.coefficients[i];
  return res;
}

template <typename p_type> 
polynom<p_type> operator+(polynom<p_type> p1, polynom<p_type> p2)
{
  int i;
  polynom<p_type> res;
  for(i = 0; i < MAX_polynom_size; i++)
    res.coefficients[i] = p1.coefficients[i] + p2.coefficients[i];
  return res;
}

template <typename p_type> 
polynom<p_type> operator-(polynom<p_type> p1, polynom<p_type> p2)
{
  return p1 + (-p2);
}

// Результат этой функции равен произведению многочлена p(q) на q^d 
template <typename p_type> 
polynom<p_type> multiply_q(polynom<p_type> p, p_type d)
{
  int i;
  polynom<p_type> res;

  int min_c = p.get_min_coefficient();
  int max_c = p.get_max_coefficient();
  // При умножении на q^d (d < 0) не выходим за нижнюю границу массива коэффициентов
  assert(min_c + d >= 0);
  // При умножении на q^d (d > 0) не выходим за верхнюю границу массива коэффициентов
  assert(max_c + d < MAX_polynom_size);


  // -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6
  //  0  0  0  5  0  1  1  2  3  0  0  0  0
  //  +2
  //  0  0  0  0  0  5  0  1  1  2  3  0  0
  //  -3
  //  5  0  1  1  2  3  0  0  0  0  0  0  0  
  // Из-за отсутствия второго условия была ошибка, пойманная unit-тестами 
  for(i = 0; (i + d < MAX_polynom_size) && (i < MAX_polynom_size); i++)
    if(i + d >= 0)
      res.coefficients[i + d] = p.coefficients[i];
  return res;
}

// Умножает многочлен на число 
template <typename p_type> 
polynom<p_type> operator*(p_type d, polynom<p_type> p)
{
  int i;
  polynom<p_type> res;
  for(i = 0; i < MAX_polynom_size; i++)
    res.coefficients[i] = d * p.coefficients[i]; 
  return res;  
}

// Перемножает два многочлена
template <typename p_type> 
polynom<p_type> operator*(polynom<p_type> p1, polynom<p_type> p2)
{
  int i;
  polynom<p_type> res;
  int min_c = p2.get_min_coefficient();
  int max_c = p2.get_max_coefficient();
  for(i = -MAX_coeff; i <= MAX_coeff; i++)
    if(min_c <= i + MAX_coeff && i + MAX_coeff <= max_c) // Если этой строчки нет, то падает assert выхода за границы полинома
      res = res + p2.coefficients[i + MAX_coeff] * multiply_q(p1, i);
  return res;  
}

// Переход от переменной sqrt(t) к переменной t
template <typename p_type>
polynom<p_type> another_variable(polynom<p_type> p)
{
  polynom<p_type> res;
  int i;
  for(i = - MAX_coeff; i <= MAX_coeff; i++)
    if(p.coefficients[i + MAX_coeff] != 0)
    {
       assert(i * 2 + MAX_coeff >= 0);
       assert(i * 2 + MAX_coeff <= MAX_polynom_size);
       res.coefficients[i * 2 + MAX_coeff] = p.coefficients[i + MAX_coeff];
    }
  return res;
}

template <typename p_type>
bool operator==(polynom<p_type> p1, polynom<p_type> p2)
{
  int i;
  for(i = - MAX_coeff; i <= MAX_coeff; i++)
    if(p1.coefficients[i + MAX_coeff] != p2.coefficients[i + MAX_coeff])
      return false;
  return true;
}
