e-olymp 6975. Магический Множитель

Задача

Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $n$ металу для виплавки меча, вони вважають, що меч буде найбільш потужним, якщо його товщина $k$ обрана відповідно до наступного правила:

Визнач невід’ємне ціле число $n$. Знайти найменше $k$, для якого десяткове представлення чисел в послідовності

$n, 2n, 3n, 4n, 5n,\ldots, kn$

містить всі десять цифр (від $0$ до $9$) як мінімум один раз?

Лорд Елронд з Рівенделл доручив Вам розробити алгоритм, який знайде оптимальну товщину $k$ для будь-якого заданого кількості металу $n$.

Вхідні дані

Кожен рядок містить одне число $n$ $(1 \leqslant n  \leqslant 200000000)$.

Вихідні дані

Для кожного тесту вивести в окремому рядку необхідне значення $k$ — таке що кожна цифра від $0$ до $9$ зустрічається хоча б один раз.

Тести

Вхідні дані Вихідні дані
1 1

10

123456789

3141592

10

9

3

5

2 200000000 45

Код

Рішення

Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.

Посилання

  • Задача на e-olymp.
  • Код рішення на Replit.
  • Код рішення на Ideone.

Related Images: