Задача.
На днях первоклассник Вася научился складывать числа. Ему этот процесс очень нравится, и он складывает всё подряд. Когда все числа вокруг оказываются сложенными, Вася обращается к своему старшему брату Пете за новыми числами. После нескольких обращений устав работать генератором случайных чисел, Петя придумал для Васи занятие, которое может надолго того занять.
Он предложил Васе находить суммы цифр последовательных чисел — 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 — и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от 1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр последовательных чисел не являются случайными, часто они идут подряд, но полностью закономерность он так и не понял.
Чтобы найти закономерности, Петя решил исследовать крайние случаи, например, какое из чисел даёт максимальную сумму цифр. Данных для чисел до 115 оказалось недостаточно для окончательных выводов, и Пете пришла в голову идея для ускорения вычислений использовать вместо братика компьютер. Поскольку сам он в программировании не очень силён, он обратился за решением этой задачи к Вам.
.
Входные данные
В первой строке входных данных находится число N (1 <= N <= 2 147 483 647).
Выходные данные
Выведите число от 1 до N включительно с максимальной суммой цифр. Если чисел с максимальной суммой цифр несколько, выведите наибольшее из них.
Тесты:
| число N | результат |
| 1 | 1 |
| 98 | 98 |
| 13759 | 9999 |
| 999756 | 998999 |
| 2147483647 | 1999999999 |
Код программы:
|
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 |
#include <iostream> using namespace std; int TheNumberOfDigits(int n)//Количество цифр в числе { int i=1; while ((n/=10)>0) { i++; } return i; } int sc(int a) //Сумма цифр числа { int sum = 0; while (a/1>0) { sum+=a%10; a/=10; } return sum; } int main() { int n, v, t, x; cin>>n; unsigned long long int a=10; t=TheNumberOfDigits(n); x=n; for (int i=1;i<t;i++) { unsigned long long int b = a*10; v=(n/b)*b+(n%b/a-1)*a+a-1; if (sc(v)>sc(x)) x=v; a*=10; } cout<<x<<endl; return 0; } |
Решение.
Идея данного решения задачи заключается в том, что мы получаем число с большей суммой цифр, но меньше данного, заменяя часть цифр справа на девятки, а первую цифру слева от девяток уменьшаем на единицу. Так мы движемся по разрядам от единиц к десяткам, сотням и т.д., каждый раз сравнивая сумму цифр полученного числа с максимальной суммой цифр, которая у нас была до этого.
Сумму цифр и их количество в числе считают две простых в написании функции, степени (i-я и i+1-я)десятки считаются непосредственно в основном цикле.
Задача взята с сайта e-olymp.com
примечание: ссылка на код может выдавать старый вариант кода, где [latex]a[/latex] и [latex]b[/latex] считаются отдельно, а не [latex]b[/latex] выражается через [latex]a[/latex], как в этом коде, в связи с техническими проблемами на ideone. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным.
Хорошее, понятное описание. Есть некоторые недочёты в этом коде:
— В основном рабочем цикле несколько раз вызывается функция возведения в одну и туже степень. Лучше предварительно запомнить значение во временной переменной. Фактически, Вам нужны две такие переменный для i-й и (i+1)-й степеней. Если посмотреть на значения переменных, Вы увидите, что от шага к шагу цикла они просто увеличиваются в 10 раз. Т.е. отдельная функция возведения 10 в i-ю степень вообще не понадобится.
— Хотя мы уже установили, что нам от функции pow10(int n) для вычисления [latex]10^n[/latex] легко можно отказаться, я всё же хочу показать как сделать подобные вычисления быстрее:
Я оставил этот код без оптимизации, чтобы легче было понять как он работает. Конечно при оптимизации рекурсию придётся заменить циклом. Подробнее про быстрое возведение в целую степень можно прочесть, например, здесь.
Зачтено. Но лучше было бы использовать latex для [latex]N[/latex] и в оформлении [latex]1 \le N \le 2 147 483 647[/latex]