Задача
Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $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 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; bool Cheking(bool arr[]) { bool q = true; for (int i = 0; i < 10; i++) if (arr[i] == false) q = false; if (q == false) return true; else return false; } void Filling(bool arr[], long a) { int b; while (a > 0) { b = a % 10; arr[b] = (bool)1; a = (a - b) / 10; } } int main() { long n, k; bool arr[10]; while (cin >> n) { k = 0; for (int i = 0; i < 10; i++) arr[i] = 0; while (Cheking(arr)) { k++; Filling(arr, k * n); } cout << k << '\n'; } } |
Рішення
Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.