0 / 0 / 0
Регистрация: 30.05.2020
Сообщений: 10
|
||||||
1 | ||||||
Задача не проходит по времени, слишком долго выполняется31.05.2020, 15:57. Показов 1867. Ответов 6
Метки нет (Все метки)
Условие:
Серийные номера игр компании «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 Рабочий код, но превышающий лимит времени
0
|
31.05.2020, 15:57 | |
Ответы с готовыми решениями:
6
Слишком долго выполняется задача "ка-тая банка" Решето Эратосфена выполняется слишком долго Поиск простых чисел выполняется слишком долго Слишком долго выполняется запрос и возвращаются строки из БД Сохранение страниц выполняется слишком долго, и текст обрезается |
0 / 0 / 0
Регистрация: 30.05.2020
Сообщений: 10
|
|
31.05.2020, 20:47 [ТС] | 3 |
Опечатка, это 1018
0
|
║XLR8║
|
|
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 секунд Личка открыта Добавлено через 5 минут Делимость точно на 2N надо проверять или на 2^N?
0
|
║XLR8║
|
|
01.06.2020, 04:14 | 6 |
Ограничение времени 1 секунда
Ограничение памяти 256Mb Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности . Десятичная запись -го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая . Например, ,. При этом, если серийный номер некоторого экземпляра игры делится на , то владельцу этого экземпляра доступны дополнительные уровни. Вам задано количество экземпляров некоторой игры и число . Вычислите, сколько экземпляров содержит дополнительные уровни. Формат ввода В единственной строке входа заданы два целых числа и (1 ≤ M ≤ , 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
|
|
01.06.2020, 04:47 | 7 |
outoftime, а мне это зачем? я знаю как решать эту задачу. Да и ТС разъяснять это нет смысла, судя по уроню.
вообще это какая то олимпиада как я понял.
0
|
01.06.2020, 04:47 | |
01.06.2020, 04:47 | |
Помогаю со студенческими работами здесь
7
Интегрирование заданной функции тремя способами - код выполняется слишком долго Код очень долго выполняется, нужно сократить работу по времени Задача не проходит по времени Задача выполняется долго на одном ядре процессора - можно ли ее распараллелить Задача не проходит по времени 2 теста Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |