Задача
Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).
Входные данные
Число [latex]N[/latex] не превышающее [latex]10[/latex].
Выходные данные
В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.
Тесты
| Входные данные | Выходные данные |
| [latex]1[/latex] | [latex]10[/latex] [latex]0[/latex] |
| [latex]2[/latex] | [latex]1[/latex] [latex]22[/latex] |
| [latex]4[/latex] | [latex]12[/latex] [latex]1124[/latex] |
| [latex]5[/latex] | [latex]40[/latex] [latex]11125[/latex] |
| [latex]9[/latex] | [latex]144[/latex] [latex]111111129[/latex] |
Код программы (Цикл)
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <cmath> using namespace std; int Sum(int a) { int sum=0; while(a>0) { sum+=a%10; a/=10; } return sum; } int Mult(int a) { int mult=1; while(a>0) { mult*=a%10; a/=10; } return mult; } int main() { int n,ch=0,sum=0,mult=0,a; bool b=true; cin>>n; if(n==1) cout<<10<<" "<<0; else { if(n>1 and n<8) { for(int i=pow(10,n-1); i<pow(10,n); i++) { sum=Sum(i); mult=Mult(i); if((sum==mult) and b==true) {a=i;ch++;b=false;} else { if(sum==mult) ch++; } } cout<<ch<<" "<<a; } else { if(n==8) cout<<224<<" "<<11111128; if(n==9) cout<<144<<" "<<111111129; } } return 0; } |
Решение задачи (Цикл)
Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.
Код программы (Массив)
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main() { int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129}; int n; cin>>n; cout<<x[2*n-2]<<" "<<x[2*n-1]; return 0; } |
Решение задачи (Массив)
Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)
М-да. Засчитываю, но давайте я Вам эту же задачу дам на массивы. У Вас ведь всего несколько вариантов входа! Можно просчитать все ответы заранее и записать их в массивы.
Решение массивом имеет опечатку
не
int x[18]= {0,10,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
а
int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
ибо при $n=1$ должно вывести 10 0 а не 0 10
Вы правы.
Исправил.