Условие задачи:
Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?
Задачу также можно найти здесь.
Входные данные:
Во входном файле два числа [latex]M[/latex] и [latex]N[/latex] ( [latex]1\le M\le N\le 1000000[/latex] ) .
Выходные данные:
В выходной файл нужно записать ответ — одно число.
Тесты
№ | M | N | Вывод |
1 | 1 | 100 | 3 |
2 | 2 | 17 | 1 |
3 | 32 | 1024 | 2 |
4 | 1 | 1000000 | 7 |
5 | 10 | 10 | 1 |
Код программы
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 |
#include <iostream> using namespace std; int sumOfDigits(int a){ int sum = 0; while (a > 0){ sum += a%10; a /= 10; } return sum; } int main() { int m, n, sumMin, counter = 1; cin >> m >> n; sumMin = sumOfDigits(m); for(int i = m + 1; i <= n; i++){ if (sumOfDigits(i) < sumMin){ sumMin = sumOfDigits(i); counter = 1; } else if (sumOfDigits(i) == sumMin) counter++; } cout << counter; return 0; } |
Алгоритм решения
Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму (sumMin) сумме цифр первого числа [latex] M [/latex]. Теперь задаём цикл со счётчиком [latex] i [/latex] от [latex] M + 1 [/latex] до [latex]\le N[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex] M [/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.
Код программы можно найти здесь.
Ссылка на полностью засчитанное решение на сайте e-olymp.
Хорошо, что зачтено. Нужно поправить отступы у закрывающих фигурных скобок
Спасибо, исправил