К-удивительные числа

ЗАДАЧА №309            К-удивительные числа                                                                                           (Время: 3 сек. Память: 16 Мб Сложность: 30%)

Переворотом числа X назовем число, в котором все цифры числа X стоят в обратном порядке. Например, переворотом числа 6372 является число 2736, а числа 7800 — 87. Назовем K-удивительным такое число, которое в сумме со своим переворотом дает число K.

Например, у числа 222 имеется всего два K-удивительных числа: 111 и 210, а у числа 1050 имеется девять K-удивительных числа: 129, 228, 327, 426, 525, 624, 723, 822, 921.

Требуется написать программу, которая по заданному K определит количество K-удивительных чисел.

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число K (1 ≤ K ≤ 106).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число — количество K-удивительных чисел.

Примеры

INPUT.TXT      OUTPUT.TXT

222                                2

1050                             9

Идея алгоритма

При заданных условиях нет смысла искать эффективный алгоритм. Вполне достаточно грубого перебора всех чисел в диапазоне от M до K и проверки числа на «удивительность».

Начальное значение M можно вычислить из условия того, сумма числа и его «переворота» должна давать n-разрядное число, где n – разрядность числа K. В качестве M достаточно взять минимальное число разрядности n-1.

Единственный технический момент при вычислении «переворота» — инверсного числа состоит в преобразовании числа в строку, переворота ее и обратного преобразования строки в число.

Вот как выглядит возможный вариант программы на C#:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Suprise_numbers

{

class Program

{

static void Main(string[] args)

{

int res = 0;

string sk;

Console.WriteLine(«Введите число K»);

sk = Console.ReadLine();

int k = int.Parse(sk);

//поиск начального кандидата – числа m

int n = sk.Length;

string sm = «1″;

for (int i = 0; i < n — 2; i++)

sm += «0″;

int m = int.Parse(sm);

string snum, s_inverse;

int inverse;

//проверка числа num на «исключительность»

for(int num = m; num < k; num++)

{

snum = num.ToString();

n = snum.Length;

s_inverse = snum[n - 1].ToString();

for (int j = n — 2; j >= 0; j—)

s_inverse += snum[j].ToString();

inverse = int.Parse(s_inverse);

if (num + inverse == k)

{

res++;

Console.WriteLine(

«K- удивительным числом является число — » + num);

Console.WriteLine(«Переворот num — » + inverse);

}

}

Console.WriteLine(«У числа {0} удивительных чисел {1}»,

k, res);

}

}