Матч 62, Уменьшающиеся числа (DecreasingNumbers)

Неотрицательное целое число называется уменьшающимся, если цифры в его десятичной записи расположены в порядке убывания слева направо. Например, числа 321 и 950 являются уменьшающимися, а 322 и 958 нет. Пусть d – список всех уменьшающихся чисел в порядке возрастания. Вернуть n - ый элемент в этом списке (нумерация чисел в списке начинается с нуля) или -1, если такового не существует.

Класс: DecreasingNumbers

Метод: long long getNth(int n)

Ограничения: 0 £ n £ 10⁶.

Вход. Неотрицательное целое число n.

Выход. n - ый элемент в отсортированном списке всех уменьшающихся чисел.

Пример входа

n

0

18

500000

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

0

42

-1

РЕШЕНИЕ

перебор

Уменьшающееся число не может содержать одинаковые цифры. Поскольку цифр всего 10 (от 0 до 9), то наименьшим уменьшающимся числом является 0, а наибольшим 9876543210. Рассмотрим множество цифр {9, 8, 7, …, 1, 0}. Существует взаимно однозначное соответствие между его подмножествами и уменьшающимися числами. Таким образом, количество уменьшающихся чисел равно числу подмножеств множества {9, 8, 7, …, 1, 0} минус 1 (пустое подмножество не дает уменьшающегося числа), то есть 2¹⁰ – 1 = 1023.

Уменьшающиеся числа будем генерировать в массиве v. Занесем все однозначные числа в v (они все являются уменьшающимися). Далее генерацию уменьшающихся чисел сделаем по принципу: если в списке уже есть число , то в список можно добавить числа , , … , . Например, если имеется число 953, то из него можно получить уменьшающиеся числа 9530, 9531 и 9532.

Далее просто возвращаем n - ое число построенного списка уменьшающихся чисел, то есть v[n]. Сгенерированные числа находятся в ячейках от v[0] до v[1022] (всего 1023 числа). Поэтому если n > 1022, то возвращаем -1.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

vector<long long> v;

class DecreasingNumbers

{

public:

long long getNth(int n)

{

int i, j, temp;

for(i = 0; i < 10; i++) v.push_back(i);

for(i = 0; i < 1022; i++)

{

temp = v[i];

for(j = 0; j < temp % 10; j++)

v.push_back((long long)10 * temp + j);

}

return (n > 1022) ? -1 : v[n];

}

};