Дек 11 2013
К-удивительные числа
ЗАДАЧА №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);
}
}
