Как быстро посчитать?
От: olimp_20  
Дата: 19.10.15 06:11
Оценка:
Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.

Формат входных данных:
Натуральное число n (1≤n≤999).
формат результата:
Если задачу выполнить нельзя то вывести «Impossible». Если задачу выполнить можно — вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.
Примеры

Входные данные в файле input.txt Результат работы в файле output.txt
37 1 3
25 Impossible
Вопрос:
1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?
2) если результата нет, то как выяснить не применяя перебор: возможно есть какая-либо теорема, математическая закономерность? (или все-таки применять перебор вариантов, тогда когда его остановить?)
3) "количество цифр которые может отображать калькулятор считать неограниченным" — это означает, что применяется длинная арифметика?
Re: Как быстро посчитать?
От: T4r4sB Россия  
Дата: 19.10.15 07:50
Оценка: 1 (1)
Для чисел, что не делятся на 2 и 5, далеко перебирать не придётся, чтобы получить число из девяток, потому что есть теорема.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re: Как быстро посчитать?
От: kfmn Россия  
Дата: 19.10.15 08:02
Оценка:
Здравствуйте, olimp_20, Вы писали:

_>Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.


_>Формат входных данных:

_>Натуральное число n (1≤n≤999).
_>формат результата:
_>Если задачу выполнить нельзя то вывести «Impossible». Если задачу выполнить можно — вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.
_>Примеры

_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
Входные данные в файле input.txt Результат работы в файле output.txt
37 1 3
25 Impossible


_>Вопрос:

_>1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?
_>2) если результата нет, то как выяснить не применяя перебор: возможно есть какая-либо теорема, математическая закономерность? (или все-таки применять перебор вариантов, тогда когда его остановить?)
_>3) "количество цифр которые может отображать калькулятор считать неограниченным" — это означает, что применяется длинная арифметика?

Думаю, тут где-то малая теорема Ферма рядом пробегала... Например, число из одних девяток точно можно получить, если n взаимно просто с 10, т.к. 10n-1 = 1 (mod n). Про другие надо подумать.
Re: Как быстро посчитать?
От: StatujaLeha на правах ИМХО
Дата: 19.10.15 08:03
Оценка:
Здравствуйте, olimp_20, Вы писали:

Переберем все цифры от 1 до 9.
Обозначим текущую проверяемую цифру как d.
Тогда нам надо найти некоторое число вида Xm = d*11...1(m единиц) или понять, что такого числа не существует.
Последовательность Ym = Xm % n = (d*11...1(m единиц)) % n — циклична.
Поэтому просто идем начиная с ее первого члена пока не наткнемся на Ym = 0.
Если наткнулись, то восстановить число — не проблема: d*11...1(m единиц).
Если очередной элемент последовательности != 0, то запоминаем его и идем дальше.
Если все возможные значения элементов Ym проверены, а число не нашлось, то для данной цифры искомого числа не существует.
Поскольку последовательность состоит из остатков от деления на n, то для каждой цифры потребуется не более n проверок.
Re[2]: Как быстро посчитать?
От: StatujaLeha на правах ИМХО
Дата: 19.10.15 08:06
Оценка: 3 (1)
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, olimp_20, Вы писали:


SL>Переберем все цифры от 1 до 9.

SL>Обозначим текущую проверяемую цифру как d.
SL>Тогда нам надо найти некоторое число вида Xm = d*11...1(m единиц) или понять, что такого числа не существует.
SL>Последовательность Ym = Xm % n = (d*11...1(m единиц)) % n — циклична.
SL>Поэтому просто идем начиная с ее первого члена пока не наткнемся на Ym = 0.
SL>Если наткнулись, то восстановить число — не проблема: d*11...1(m единиц).
Число не так восстановил: d*11...1(m единиц)/n

SL>Если очередной элемент последовательности != 0, то запоминаем его и идем дальше.

SL>Если все возможные значения элементов Ym проверены, а число не нашлось, то для данной цифры искомого числа не существует.
SL>Поскольку последовательность состоит из остатков от деления на n, то для каждой цифры потребуется не более n проверок.
Re: Как быстро посчитать?
От: Chorkov Россия  
Дата: 19.10.15 08:23
Оценка: 3 (1) +1
Здравствуйте, olimp_20, Вы писали:


_>Вопрос:

_>1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?

Можно ограничить:
10^m

(где m — заданное число, меньшее 999).

Пусть G(k) = 111...1 (k единиц).
G(k) = (10^k-1)/9,
G(k+1) = G(k)*10+1

Рассмотрим последовательность S(k) = G(k) % m.

S(k+1) = (S(k)*10 +1) % m

Очевидно, S(k)<m для любого k.
Следовательно длинна периода S(k), также должна быть не больше m,
(поскольку все числа S(k) в пределах одного периода должны быть уникальны).

P.S.
Для чисел состоящих из других цифр — действует аналогичное ограничение.
Отредактировано 19.10.2015 8:30 Chorkov . Предыдущая версия .
Re: Как быстро посчитать?
От: Буравчик Россия  
Дата: 19.10.15 08:53
Оценка: 3 (1)
Здравствуйте, olimp_20, Вы писали:

_>Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.


Читать про делители репьюнитов
Вот здесь интересно Удивительные приключения периодических дробей

Или так:

Максимальное количество цифр в искомом числе равное N.
Нужно проверить все числа у которых все цифры одинаковые и число цифр не более N. Таких чисел всего порядка 10*N
Для каждого числа (в порядке возрастания) проверяем делится ли оно на N. Первое найденное число — ответ.

Т.к. числа большие (длинная арифметика), то операции с каждым числом занимают O(количество цифр), в нашем случае O(N).
Итого сложность алгоритма O(N^2), где N — заданное число
Best regards, Буравчик
Отредактировано 19.10.2015 9:51 Буравчик . Предыдущая версия .
Re[2]: Как быстро посчитать?
От: cures Россия cures.narod.ru
Дата: 19.10.15 15:39
Оценка: +2
Здравствуйте, Буравчик, Вы писали:

Б>Т.к. числа большие (длинная арифметика), то операции с каждым числом занимают O(количество цифр), в нашем случае O(N).


Нет там длинной арифметики, при дописывании цифры надо произвести простые операции с предыдущим остатком, за константу. Итого полное время O(N).
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.