Кто поможет с идеей решения задачи?

https://nometa.xyz/

есть задача, в которой надо посчитать количество чисел от 0 до определенного числа N, которые имеют в составе цифру "8". Ограничение N от 0 до 10000000000000000 , время 1секунда

#include <bits/stdc++.h> #include <string> using namespace std; int main() { int n, a=0, i; string l; cin>>n; for(i=1; i<=n; i++) { l = to_string(i); if(l.find("8")!=-1 ) {a++; } //если есть 8 в строке (числе) , а++; } cout <<a << endl; return 0; } так неработает из-за время (при числе >1000000000000 виснит )

помогите, пожалуйста

У Вас алгоритмическая проблема. А еще у Вас там знаковое переполнение, что соответствует неопределенному поведению.

уже сижу час и не могу придумать формулу или коротко через условие

Проверь, не виснет ли в любом другом случае, когда 8 отсутствует

вроде не виснет при любом маленьком числе

Читайте.

Ну значит переписать надо.

Сколько чисел, которые необходимо проверить, содержатся в одном тесте?

Сейчас зашел на сайт уточнить от 2 до 10^10

Кароч, попробуй нейронку написать

ля, это не умею)

Тоже начинающий?)

да

Оригинал задачи скинь пожалуйста

Возможно посчитать количество влсьмёрок на одном небольшом участке например до тысячи, и после умножать на сколько данный участок вмещается в заданный , плюс какой то остаток, но посчитать этот остаток до тысячи должно быстро Понятно что 800, 8000 тыс автоматически входят

в лс можно скину?

д

тут фотку нельзя

от 0 до 999 И от 1000 до 1999 Будет одинаковое количество восьмёрок Вроде бы хД

можно так https://telegra.ph/file/649d065e739e080779106.jpg через @MediaDowBot создал

о, круто! ток это вручну надо будет участки смотреть же?

Тебе же задали число Просто умножить сколько участок укладывается его учтя 8000, 80000 ( то что больше участка) И посчитав в остатке Может быть быстрее выдет Но я бы так попробовал на первый взгляд Возможно чото не догоняю

класс, пон, вроде быстрый алгоритм будет, щас подумаю как написать

может тогда сразу не до 1000, а до 10 000 брать как один участок, все равно быстре вроде

Не, хуйня, мой метод лучше

можно отрезок 100000 или даже 100 000

А комбинаторную формулу не вывести?

Мне кажется на это задача

скорее всего на формулу задача, ток вот формулу не могу придумать

Количество всего чисел - количество чисел без 8

и как посчитаешь количество без 8?

integer overflow

Ну для n разрядного числа это 8*9^(n-1)

Тут явно что длинная арифметика в любом случае участвует

?

На первом месте из всех цифр могут стоять все кроме 0 и 8, для всех остальных соответственно все кроме 8

Вейт… умножаем на 8, потому что в переднем числе у нас только 8 возможных чисел != 8, а остальные разряды 9, потому что там 9 возможных чисел != 8?

На 8 домножаем, потому что в начале 0 стоять не может

Ну я про то же, 8 возможных чисел в главном разряде, и 9 в побочных