Матч 37, Нумерация книг (BooksNumbering)

Книги в библиотеке перенумерованы натуральными числами: 1, 2, 3, … . Для нумерации было использовано usedDigits цифр. По значению usedDigits необходимо вычислить количество книг в библиотеке. Если такой нумерации не существует, вернуть -1.

Класс: BooksNumbering

Метод: int numberOfBooks(int usedDigits)

Ограничения: 1 £ usedDigits £ 2*10⁹.

Вход. Количество цифр usedDigits, использованное при нумерации книг библиотеки.

Выход. Количество книг в библиотеке. Если нумерации не существует, вернуть -1.

Пример входа

usedDigits

11

1863927342

1863927343

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

10

219448716

-1

РЕШЕНИЕ

математика

Однозначных натуральных чисел имеется 9, двузначных 90, трехзначных 900 и так далее. В переменной b будем хранить количество c - значных чисел. Изначально положим b = 9, c = 1, на каждой итерации b будем умножать на 10, а к c будем прибавлять 1. Из usedDigits на каждой итерации будем вычитать количество цифр, необходимое для записи всех c - значных чисел. Когда usedDigits станет не больше b * c, то все c - значные числа записать не удастся. Оставшимися usedDigits цифрами можно будет записать только (usedDigits / c) c - значных чисел. Если usedDigits не делится нацело на c, то возвращаем -1. В переменной u накапливаем количество использованных цифр при нумерации.

ПРОГРАММА

#include <stdio.h>

class BooksNumbering

{

public:

int numberOfBooks(int usedDigits)

{

long long b = 9, c = 1, u = 0;

while(usedDigits > b * c)

{

usedDigits -= b * c; u += b;

b *= 10; c++;

}

if(usedDigits % c != 0) return -1;

return u + usedDigits / c;

}

};