Задача с страницами книги

175

17 февраля 2019, 02:00

Есть задача, я ее правильно решил, но на одном из тестов выдает "Time limit error". Перепробовал самые различные варианты решения этой задачи, в том числе написать отдельную функцию которая бы просто делила на 10 и возвращала количество делений (количество цифр на странице), но она всегда падает на тесте с большим количеством вводных данных. Вот сама задача.

Девочка рисует книжки. Каждую книгу она нумерует с X числа. Иными словами, на первой странице есть номер X, написанный на нем, на второй странице есть номер X + 1, написанный на нем, и так далее. Она использовала общее количество цифр, равное N, и начал нумерацию книжек с номера X. Пример: номер 99 имеет 2 цифры на нем. Поэтому, если бы я написал только 2 страницы, начиная с номера 99, я бы использовал 5 цифр для номера моей комиксов: 99, 101.

Вводные данные: Первая строка содержит целое число T, количество тестовых случаев. Каждая строка из следующих T строк описывает один тестовый пример. Каждый тестовый пример содержит 2 пробела, разделенных целыми числами N, X (1 ≤ N, X ≤ 10^15).

Вывод: Для каждого тестового примера печатайте одну строку, содержащую одно целое число, обозначающее количество страниц в комиксе Nour или печатайте -1, если такое невозможно.

Примеры Ввода/Вывода:

+------------------+-------------------+
| стандартный ввод | стандартный вывод |
+------------------+-------------------+
| 2                | 8                 |
| 11 5             | -1                |
| 12 5             |                   |
+------------------+-------------------+

Мой код:

#include <iostream>
#include <string>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    string s;
    int x1, t, len, lap=0;
    long long int n, x;
    cin >> t;
    for(int i=0;i<t;i++)
    {
        cin >> n >> x;
        s = to_string(x);
        len = s.length();
        x1=x%10;
        while(n>0)
        {
            if(x1%10==0 && lap>0){len++;}
            n-=len;
            lap++;
            x1++;
        }
        if(n==0){cout << lap << endl;}
        else{cout << "-1"<<endl;}
        lap = 0;
    }
    return 0;
}

Answer 1

Вряд ли идея подсчитывать все страницы, пока не кончатся цифры, подойдёт для больших чисел. Лучше подумать о более быстром решении, использующем немножко логики и математики.

Все страницы от first, номер которых не превосходит следующую степень десяти tenpow, содержат одинаковое количество цифр ndig.

Таким образом, можно проверить, истратим ли мы все имеющиеся цифры nd в пределах tenpow.
Если да, то нужно убедиться, что не будет остатка.

Если же нет, то уменьшаем nd на количество цифр в данном диапазоне и переходим к следующему диапазону.

Сложность решения логарифмическая O(log(nd))

(Замечу, что мой третий пример подсказывает идею ещё более быстрого решения, но вряд ли это уже понадобится)

def pages(nd, first):
    tenpow = 1
    ndig = 0
    t = first
    while t > 0:
        t = t // 10
        tenpow *= 10
        ndig += 1
    sum = 0
    last = first - 1 + nd // ndig
    while last >= tenpow:
        sum += tenpow - first
        nd -= (tenpow - first) * ndig
        first = tenpow
        tenpow *= 10
        ndig += 1
        last = first - 1 + nd // ndig
    if nd % ndig > 0:
        return -1
    return sum + (last - first + 1)
print(pages(117, 88))
print(pages(118, 88))
print(pages(7*1 + 90 * 2 + 900 * 3 + 9000 * 4 + 33333 * 5, 3))
print(pages(2000000*7 + 66666666 * 8, 8000000))
43
-1
43330
68666666