443. Смиренные числа

Числа, простыми делителями которых являются только числа 2, 3, 5 и 7, называются смиренными числами. Например, последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … состоит из первых 20 смиренных чисел.

Вход. Состоит из нескольких строк. Каждая строка содержит число n (1 £ n £ 5842). Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести фразу “The nth humble number is number.”. В зависимости от значения n следует выводить его с одним из суффиксов: “st”, “nd”, “rd”, или “th” как показано в примере.

Пример входа

1

2

3

4

11

12

13

21

22

23

100

1000

5842

0

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

The 1st humble number is 1.

The 2nd humble number is 2.

The 3rd humble number is 3.

The 4th humble number is 4.

The 11th humble number is 12.

The 12th humble number is 14.

The 13th humble number is 15.

The 21st humble number is 28.

The 22nd humble number is 30.

The 23rd humble number is 32.

The 100th humble number is 450.

The 1000th humble number is 385875.

The 5842nd humble number is 2000000000.

РЕШЕНИЕ

полный перебор

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

Смиренные числа имеют вид 2ⁱ * 3^j * 5^k * 7^l, где 0 £ i < 31, 0 £ j < 20, 0 £ k < 14, 0 £ l < 12. Ограничения на переменные i, j, k, l выбраны так, чтобы значения смиренных чисел не превосходили 2*10⁹ (5842-ым смиренным числом будет 2*10⁹). Генерируем в массиве humble[5843] все смиренные числа при помощи четырех вложенных циклов. Сортируем массив humble, после чего humble[i] содержит i - ое смиренное число.

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

Смиренные числа заносятся в массив humble. Переменная ptr содержит указатель на текущую свободную ячейку массива humble. Переменные i, j, k, l используются в for - циклах. Переменные _i, _j, _k, _l содержат соответственно текущие значения 2ⁱ, 3^j, 5^k, 7^l. В переменной suffix генерируется суффикс числа при его выводе.

int n, ptr;

long long humble[5843], i, j, k, l, _i, _j, _k, _l;

char suffix[3];

Если текущее значение _i * _j * _k * _l = 2ⁱ * 3^j * 5^k * 7^l на каком-то уровне вложенности циклов станет большим 2 * 10⁹, то выходим из текущего цикла на уровень выше. Иначе текущее полученное смиренное число заносим в ячейку humble[ptr].

ptr = _i = _j = _k = _l = 1;

for(i = 0; i < 31; i++) // 2

{

for(j = 0; j < 20; j++) // 3

{

for(k = 0; k < 14; k++) // 5

{

for(l = 0; l < 12; l++) // 7

{

humble[ptr++] = _i * _j * _k * _l;

_l *= 7;

if (_i * _j * _k * _l > 2000000000) break;

}

_k *= 5; _l = 1;

if (_i * _j * _k * _l > 2000000000) break;

}

_j *= 3; _k = 1;

if (_i * _j * _k * _l > 2000000000) break;

}

_i *= 2; _j = 1;

if (_i * _j * _k * _l > 2000000000) break;

}

Сортируем массив, после чего humble[i] содержит i - ое смиренное число.

sort(humble,humble+ptr);

Читаем входное число n и выводим humble[n]. В зависимости от последних двух цифр числа n выводим соответствующий ему суффикс (“st”, “nd”, “rd”, или “th”).

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

{

strcpy(suffix,"th");

if ((n % 100 < 10) || (n % 100 > 20))

{

if (n % 10 == 1) strcpy(suffix,"st");

if (n % 10 == 2) strcpy(suffix,"nd");

if (n % 10 == 3) strcpy(suffix,"rd");

}

printf("The %d%s humble number is %d.\n",n,suffix,humble[n]);

}