0 / 0 / 0
Регистрация: 30.05.2020
Сообщений: 10
1

Задача не проходит по времени, слишком долго выполняется

31.05.2020, 15:57. Показов 1867. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Условие:
Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности A. Десятичная запись i-го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая i. Например, A2=12, A11=1234567891011.

При этом, если серийный номер некоторого экземпляра игры делится на 2N, то владельцу этого экземпляра доступны дополнительные уровни.

Вам задано количество экземпляров M некоторой игры и число N. Вычислите, сколько экземпляров содержит дополнительные уровни.

Формат ввода
В единственной строке входа заданы два целых числа M и N (1 ≤ M ≤ 1018, 1 ≤ N ≤ 6).

Формат вывода
Выведите одно целое число — количество экземпляров игры, содержащих дополнительные уровни

Пример 1
Ввод
1 1
Вывод
0

Пример 2
Ввод
10 1
Вывод
5

Пример 3
Ввод
10 2
Вывод
2

Пример 4
Ввод
10 3
Вывод
1

Пример 5
Ввод
10 4
Вывод
1

Пример 6
Ввод
10 5
Вывод
1

Пример 7
Ввод
10 6
Вывод
1

Рабочий код, но превышающий лимит времени
Python
1
2
3
4
5
6
7
8
9
10
c = input().split()
a = int(c[0])
b = 2 ** int(c[1])
itog = 0
number = ''
for i in range(1, a + 1):
    number += str(i)
    if int(number) % b == 0:
        itog += 1
print(itog)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.05.2020, 15:57
Ответы с готовыми решениями:

Слишком долго выполняется задача "ка-тая банка"
Привет. У Никиты есть n банок газировки, каждая из которых имеет свой объём. Известно, что...

Решето Эратосфена выполняется слишком долго
Следующий код... eratosPrimes :: Int -> eratosPrimes n = getEratosPrimes n where ...

Поиск простых чисел выполняется слишком долго
Добрый день, На Лурке в статье Python (http://lurkmore.to/Python) Приводится код скрипта -...

Слишком долго выполняется запрос и возвращаются строки из БД
Здравствуйте. Я переделываю программу для знакомых. У них были исходники и они мне их дали для...

Сохранение страниц выполняется слишком долго, и текст обрезается
Здравствуйте! Помогите пожалуйста решить следующую проблему. Сайт на wp. Сервер apache 2.2...

6
Status 418
Эксперт Python
4575 / 2342 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
31.05.2020, 20:42 2
Цитата Сообщение от Armavia Посмотреть сообщение
но превышающий лимит времени
и с чем это может быть связано?

Добавлено через 1 минуту
Цитата Сообщение от Armavia Посмотреть сообщение
1018
1018 цифр так то не много.
0
0 / 0 / 0
Регистрация: 30.05.2020
Сообщений: 10
31.05.2020, 20:47  [ТС] 3
Опечатка, это 1018
0
Status 418
Эксперт Python
4575 / 2342 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
31.05.2020, 20:51 4
а это много)) Что делать?
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
01.06.2020, 03:27 5
Armavia, eaa, 1 ≤ N ≤ 6, т.е. надо уметь делать проверку на делимость 2, 4, 6, 8, 10, 12

Делимость на 2: Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной.
Делимость на 3: Число делится на 3, когда сумма его цифр делится на 3.
Делимость на 4: Число делится на 4, когда две последние цифры нули или составляют число, делящееся на 4.
Делимость на 6: Число делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3).
Делимость на 8: Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой в разряде десятков и учетверённой цифрой в разряде сотен, делится на 8.
Делимость на 10: Число делится на 10 тогда и только тогда, когда оно оканчивается на ноль.
Делимость на 12: 12 это 4*3, т.е. надо чтобы соблюдались признаки делимости на 4 и на 3.

Остаётся сложность с 1 ≤ M ≤ 10^18

И тут у меня открылись глаза. У нас есть некое число N и ряд чисел до M, нам надо сказать сколько из них делится на N.

Допустим N это 2, тогда каждое 2е число будет делиться на N, т.е. M/2 чисел мы получим в итоге.
Допустим N это 4, тогда каждое 4е число будет делиться на N, т.е. M/4 чисел мы получим в итоге.
Допустим N это 6, тогда каждое 6е число будет делиться на N, т.е. M/6 чисел мы получим в итоге.
...
В общем случае, получается что последовательность чисел до условно бесконечного M будет иметь M/N чисел делимых на N.

И тут я понял что нам то надо не просто делимость i-ого числа к 2n узнать, но числа которое будет склейкой всех чисел от 1 до i.

С делимостью на 2, 4, 8, 10 нам надо знать максимум 3 последних цифры чтобы сказать ответ формулой при росте i от 1000 (чтобы были эти 3 цифры).

Остаётся вопрос с делимостью на 6, 12 (так как нужна делимость на 3) и что делать для i до 1000.

Итоговое число будет склейкой от 1 до i, у нас получается последовательность 1, 12, 123, 1234, ...

И на этом моменте у меня огромное желание посмотреть как ведёт себя последовательность склеек до большого i (чтобы комп мог вычислить) по модулю 3. Есть ли там цикл и повторяется ли он всё время? Более того, туже операцию охота провести для делимости на 4 и 8, так можно решить проблему малых i одним махом.

Добавлено через 40 секунд
Цитата Сообщение от Armavia Посмотреть сообщение
Модераторы удаляют
Личка открыта

Добавлено через 5 минут
Цитата Сообщение от Armavia Посмотреть сообщение
2 ** int(c[1])
Делимость точно на 2N надо проверять или на 2^N?
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
01.06.2020, 04:14 6
Ограничение времени 1 секунда
Ограничение памяти 256Mb

Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности https://www.cyberforum.ru/cgi-bin/latex.cgi?A. Десятичная запись https://www.cyberforum.ru/cgi-bin/latex.cgi?i-го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая https://www.cyberforum.ru/cgi-bin/latex.cgi?i. Например, https://www.cyberforum.ru/cgi-bin/latex.cgi?A_2 = 12,https://www.cyberforum.ru/cgi-bin/latex.cgi? A_{11} = 1234567891011.

При этом, если серийный номер некоторого экземпляра игры делится на https://www.cyberforum.ru/cgi-bin/latex.cgi?2^N, то владельцу этого экземпляра доступны дополнительные уровни.

Вам задано количество экземпляров https://www.cyberforum.ru/cgi-bin/latex.cgi?M некоторой игры и число https://www.cyberforum.ru/cgi-bin/latex.cgi?N. Вычислите, сколько экземпляров содержит дополнительные уровни.

Формат ввода
В единственной строке входа заданы два целых числа https://www.cyberforum.ru/cgi-bin/latex.cgi?M и https://www.cyberforum.ru/cgi-bin/latex.cgi?N (1 ≤ M ≤ https://www.cyberforum.ru/cgi-bin/latex.cgi?10^{18}, 1 ≤ N ≤ 6).

Пример 1
Ввод Вывод
1 1
0
Пример 2
Ввод Вывод
10 1
5
Пример 3
Ввод Вывод
10 2
2
Пример 4
Ввод Вывод
10 3
1
Пример 5
Ввод Вывод
10 4
1
Пример 6
Ввод Вывод
10 5
1
Пример 7
Ввод Вывод
10 6
1

Добавлено через 10 минут
Делимость на 2^N, вроде как, надо в двоичной системе смотреть. Но число мы строим в 10-чной приклеивая новые цифры сзади и как подойти к изменениям 2-чной записи я, пока, ума не приложу.
0
Status 418
Эксперт Python
4575 / 2342 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
01.06.2020, 04:47 7
outoftime, а мне это зачем? я знаю как решать эту задачу. Да и ТС разъяснять это нет смысла, судя по уроню.
вообще это какая то олимпиада как я понял.
0
01.06.2020, 04:47
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.06.2020, 04:47
Помогаю со студенческими работами здесь

Интегрирование заданной функции тремя способами - код выполняется слишком долго
Добрый вечер! Надо сделать лабораторную работу по численным методам. Результат верный, но программа...

Код очень долго выполняется, нужно сократить работу по времени
Анагра́мма (от греч. ανα- — «пере» и γράμμα — «буква») — литературный приём, состоящий в...

Задача не проходит по времени
Доброго времени суток, есть вот такая задача: И мое решения: std::string toB(int n) {...

Задача выполняется долго на одном ядре процессора - можно ли ее распараллелить
Здравствуйте, коллеги! Я с Delphi работаю давно, но монгопоточность не использовал. Сделал пока...

Задача не проходит по времени 2 теста
Решаю задачу на informatics(да, сириус...) Подсчитайте количество натуральных делителей числа x...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru