Задача "квадратная страна"

[Dr.RichardFeynman]

(Оффтоп)

В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась целым положительным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок.
Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 × 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась.
Найдите, какое количество квадратных свидетельств он получил.
Исходные данные
В единственной строке стоит целое положительное число N ≤ 60 000 — число квадриков, которое было у жителя.
Результат
В единственной строке стоит число свидетельств, полученных в результате сделки.
Пример: 344 | 3

2 день пытаюсь понять, почему у меня выходят не правильные ответы. Для 344 правильный, для 1, 2, 4 правильно, для 3 и 5 нет.

(Оффтоп)

#include<stdio.h>
#include<iostream>
#include<cmath>

using namespace std;

int minim[128];
int otvet = 1;

int count(double a, int min)
{
   for(double k = floor(sqrt(a)); k>0; k--)
   {
      if(a-k*k == 0)
         return 1;
      otvet +=1;
      /*printf("%lf", k);*/
      for(int i = 0; i<k; i++)
      {
         if(i*i == a-k*k)
         {
            return 1;
         }
      }
      count(k,otvet+1); return 1;
   }
}
int main()
{
   double a;
   scanf("%lf", &a);
   if(a == 2)
      printf("2");
   else
   {
   count(a, otvet);
   printf("%d", otvet);
   }
}

[Dr.RichardFeynman]

Извините, не тот код запостил

#include<stdio.h>
#include<iostream>
#include<cmath>

using namespace std;

int otvet = 1;

int count(double a, int min)
{
   for(double k = floor(sqrt(a)); k>0; k--)
   {
      if(a-k*k == 0)
         return 1;
      otvet +=1;
      /*printf("%lf", k);*/
      for(int i = 0; i<k; i++)
      {
         if(i*i == a-k*k)
         {
            return 1;
         }
      }
      count(k,otvet+1); return 1;
   }
}
int main()
{
   double a;
   scanf("%lf", &a);
   int k = floor(sqrt(a));
   if(a-k*k == 0)
      printf("1");
   else
   {
   count(a, otvet);
   printf("%d", otvet);
   }
}

[venco]

Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

[Dr.RichardFeynman]

venco в сообщении #984224 писал(а):

Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.

[venco]

Dr.RichardFeynman в сообщении #984247 писал(а):

venco в сообщении #984224 писал(а):

Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.

Это потому что у вас запрещены одинаковые квадраты.
Попробуйте $41 = 25+16$. У вас должно получиться $41 = 36+4+1$.
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

[Dr.RichardFeynman]

venco в сообщении #984261 писал(а):

Dr.RichardFeynman в сообщении #984247 писал(а):

venco в сообщении #984224 писал(а):

Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.

Это потому что у вас запрещены одинаковые квадраты.
Попробуйте $41 = 25+16$. У вас должно получиться $41 = 36+4+1$.
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

Да, я понял
Спасибо

[arseniiv]

(Оффтоп)

Dr.RichardFeynman, C++ язык распространённый и поддерживается потому тегом syntax, в котором синтаксис подсвечивается. Так что чуть лучше писать не [​code]...[​/code], а [​syntax lang="cpp"]...[​/syntax], и можно даже не писать, а выбрать в списке «Подсветка синтаксиса» C++, само вставится.

[Dr.RichardFeynman]

arseniiv в сообщении #984331 писал(а):

(Оффтоп)

Dr.RichardFeynman, C++ язык распространённый и поддерживается потому тегом syntax, в котором синтаксис подсвечивается. Так что чуть лучше писать не [​code]...[​/code], а [​syntax lang="cpp"]...[​/syntax], и можно даже не писать, а выбрать в списке «Подсветка синтаксиса» C++, само вставится.

(Оффтоп)

Виноват, не разобрался

[Alexu007]

venco в сообщении #984261 писал(а):

Собственно, конкретная ошибка не важна. Надо алгоритм менять.

А какой алгоритм подойдёт в данном случае? Для большого массива чисел в некоторых случаях может найтись "удачное" совпадение - как его отловить?. Всё еще усложняется, если можно повторно использовать одни и те же цифры.

[venco]

Динамическое программирование - поиск всех возможных значений сумм из 1 квадрата, 2-х квадратов, и т.д.
Сложность:
$N\cdot R < N^{3\over2}$
где $R$ - результат.

(Оффтоп)

Кстати, какая оценка $R$ для всех чисел $<N$.
Как минимум $\ln N$, а то и даже $\ln\ln N$.

[Geen]

Alexu007 в сообщении #985688 писал(а):

А какой алгоритм подойдёт в данном случае?

Например, можно хранить уже найденные ранее (для меньших значений) решения и находить минимум суммы этого массива с его реверсивной версией (за исключением точных квадратов). Для миллиона работает (в Scilab) несколько секунд.

-- 04.03.2015, 23:28 --

venco в сообщении #985699 писал(а):

Кстати, какая оценка $R$ для всех чисел $<N$.

Это Вы не о теореме о четырёх квадратах, случаем?

[venco]

Geen в сообщении #985734 писал(а):

venco в сообщении #985699 писал(а):

Кстати, какая оценка $R$ для всех чисел $<N$.

Это Вы не о теореме о четырёх квадратах, случаем?

Да. Как это я мог про неё забыть.

[Geen]

Кстати, для четвёртой степени график "забавно" выглядит...