256. Чудные квадраты

 

Если десятичную запись числа 3025 разбить на две подстроки одинаковой длины, то квадрат суммы полученных таким образом чисел будет равен самому числу:

(30 + 25)2 = 3025

Необходимо найти все числа с таким свойством, содержащие четное число цифр.

При рассмотрении чисел ведущие нули берутся во внимание. Например, четырехзначное число 0001 обладает указанным свойством, так как (00 + 01)2 = 1.

 

Вход. Каждая входная строка содержит число цифр n (2, 4, 6 или 8).

 

Выход. Для каждого тестового значения n вывести все n - цифровые чудные квадраты в возрастающем порядке.

 

Пример входа

2
2

 

Пример выхода

00
01
81
00
01
81

 

 

РЕШЕНИЕ

предвычисление

 

Анализ алгоритма

Число n - значных чисел с требуемым свойством невелико, количество разных входных значений n ограничено. Найдем для каждого n = 2, 4, 6, 8 все требуемые n - значные числа и занесем их в массив. Для каждого входного n будем выводить все значения соответствующего массива.

 

Реализация алгоритма

Вычислим методом перебора все n - значные числа (n = 2, 4, 6, 8) с требуемым свойством и занесем их соответственно в массивы s2, s4, s6 и s8.

 

char s2[][3] = {"00","01","81"},

     s4[][5] = {"0000","0001","2025","3025","9801"},

     s6[][7] = {"000000","000001","088209","494209","998001"},

     s8[][9] = {"00000000","00000001","04941729","07441984",

                "24502500","25502500","52881984","60481729","99980001"};

 

Для каждого входного n выводим все числа из соответствующего массива.

 

  while(scanf("%d",&n) == 1)

    switch (n) {

      case 2: for(i = 0; i < 3; i++) printf("%s\n",s2[i]);break;

      case 4: for(i = 0; i < 5; i++) printf("%s\n",s4[i]);break;

      case 6: for(i = 0; i < 5; i++) printf("%s\n",s6[i]);break;

      case 8: for(i = 0; i < 9; i++) printf("%s\n",s8[i]);break;

  }