Условие:
Найти наибольшее натуральное число, которое не превішает N, сумма цифр которого максимальна.
Входные данные: В первой строке входных данных находится число N (1 <= N <= 2147483647).
Выходные данные: Одно число — ответ на задачу.
Пример входных данных
115
Пример выходных данных
99
Решение
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int numb, x;
scanf("%d", &numb);
if(numb>9){//если число содержит более одной цифрыint sum(0); x = numb;
vector<int> v;
while(numb>0){//вычислить сумму цифр входного числа и создать массив из цифр входного числа
v.push_back(numb%10);
sum += numb%10;
numb /= 10;
}
int sum2(0);//построить наибольшее число на интервале [1; numb]for(unsigned i=0; i<v.size()-1; ++i)
{v[i]=9; sum2 += v[i]; }
if(v[v.size()-1]>1)
{--v[v.size()-1]; sum2 += v[v.size()-1];}
else v.pop_back();
if(sum2>sum)//если построенное число имеет большую сумму - вывести построенное число, иначе вывести numbfor(int i=(int)v.size()-1; i>=0; --i)
printf("%d", v[i]);
else printf("%d", x);
}else printf("%d", numb);
printf("\n");
return 0;
}
Проблема: задача вроде бы и элементарная, и почти решена, но два теста №24 и №25 — не проходит. Закончились идеи: что проверять и какие числа могут быть во входном файле...Подскажите, что еще необходимо проверить или где ошибка в алгоритме. Спасибо.
Здравствуйте, olimp_20, Вы писали:
_>Проблема: задача вроде бы и элементарная, и почти решена, но два теста №24 и №25 — не проходит. Закончились идеи: что проверять и какие числа могут быть во входном файле...Подскажите, что еще необходимо проверить или где ошибка в алгоритме. Спасибо.
Стандартный способ: оформите своё нахождение как функцию, возвращающую искомое число как int, напишите другую функцию, которая делает это честно (перебирает все натуральные числа до N, и находит то, в котором наибольшая сумма цифр), после чего переберите все N до десяти тысяч, вычисляя результат каждой из двух функций, распечатайте те N, для которых результаты разные. Скорее всего такие найдутся даже до тысячи.
Читерский способ: перебираете все числа до N, но не (только) в виде инта, а в виде массива цифр, инкремент обычно будет сводиться к увеличению последней цифры, изредка — к старшим. При каждом инкременте соответственно изменяйте сумму цифр. Всего получите несколько миллиардов тактов, есть шанс уложиться, если сделаете аккуратно.
ЗЫ: большая просьба исходные тексты постить не только в тексте сообщения в блоке code, там съедаются переводы строк при попытке скопировать в файл, но и на хостинге типа ideone.com, там их можно будет сразу и запустить, потестировать.
Upd: для 190 Ваша программа выведет 99, а правильный ответ 189 (сумма цифр тоже равна 18, а само число больше).
Здравствуйте, olimp_20, Вы писали: _>Условие: _>Найти наибольшее натуральное число, которое не превішает N, сумма цифр которого максимальна. _>Входные данные: В первой строке входных данных находится число N (1 <= N <= 2147483647). _>Выходные данные: Одно число — ответ на задачу. _>Пример входных данных _>115 _>Пример выходных данных _>99
А как вам такое?
Решение
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);int n;
scanf("%d", &n);
int res = f(n);
printf("%d", res);
return 0;
}
int f(int n)
{
if (n < 10)
return n;
int base = 1;
while (base <= n)
base *= 10;
base /= 10;
int head = n / base;
int tail = n % base;
int candidate1 = head * base + f(tail);
int candidate2 = (head - 1) * base + (base - 1);
if (sum_of_digits(candidate1) >= sum_of_digits(candidate2))
return candidate1;
else
return candidate2;
}
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Пусть у нас n-разрядное число вида X,YYYYY
Ответами будут два кандидата (надо выяснить, который лучше)
— (X-1),99999 с суммой чисел (X-1)+(n-1)*9
— X,ZZZZZ где ZZZZZ — ответ для YYYYY.
То есть, если бы мы играли в полный перебор, то получили бы такое дерево вариантов
Здравствуйте, Sophist, Вы писали:
S>А как вам такое?
Да, Ваша програма правильно вычисляет, это видно по тому, какие тесты пройдены — в том числе проблемный для меня №25. Однако, не всё так гладко: тесты №21-№24 — "Исчерпан лимит времени". Как я понял: использованная рекурсия существенно "сожрала" время...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, olimp_20, Вы писали:
К><>
К>Пусть у нас n-разрядное число вида X,YYYYY К>Ответами будут два кандидата (надо выяснить, который лучше) К>- (X-1),99999 с суммой чисел (X-1)+(n-1)*9 К>- X,ZZZZZ где ZZZZZ — ответ для YYYYY.
К>То есть, если бы мы играли в полный перебор, то получили бы такое дерево вариантов К>[code] К>вход: ABCDE (5-разрядное)
К>-+- a9999 = A+9+9+9+8
Если возможно, уточните, пожалуйста, откуда берется 8?
Здравствуйте, olimp_20, Вы писали:
_>Да, Ваша программа правильно вычисляет, это видно по тому, какие тесты пройдены — в том числе проблемный для меня №25. Однако, не всё так гладко: тесты №21-№24 — "Исчерпан лимит времени". Как я понял: использованная рекурсия существенно "сожрала" время...
Хм, довольно странно, учитывая, что глубина рекурсии не превосходит 10, а ветка рекурсии всего одна.
Сэкономить время, в принципе, можно, если вычислять сумму цифр у второго кандидата не через функцию, а просто как (head — 1) + 9 * (base — 1). А если еще возвращать одновременно и число, и сумму его цифр, то не придется многократно считать сумму цифр в хвосте.
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Здравствуйте, olimp_20, Вы писали: _>Да, Ваша программа правильно вычисляет, это видно по тому, какие тесты пройдены — в том числе проблемный для меня №25. Однако, не всё так гладко: тесты №21-№24 — "Исчерпан лимит времени". Как я понял: использованная рекурсия существенно "сожрала" время...
Вариант без рекурсии
#include <stdio.h>
int f(int n);
int sum_of_digits(int n);
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
scanf("%d", &n);
int res = f(n);
printf("%d", res);
return 0;
}
int f(int n)
{
int order = 0;
int base = 1;
int current_value = 0;
int current_sum = 0;
while (n > 0)
{
int current_digit = n % 10;
n /= 10;
int value1 = current_digit * base + current_value;
int sum1 = current_digit + current_sum;
int value2 = (current_digit - 1) * base + (base - 1);
int sum2 = (current_digit - 1) + 9 * order;
if (sum1 >= sum2)
{
current_value = value1;
current_sum = sum1;
}
else
{
current_value = value2;
current_sum = sum2;
}
order += 1;
base *= 10;
}
return current_value;
}
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Принцип такой: для числа есть две возможных выигрышных суммы (head-1)+9*tail.Length, достижимая или [head-1]9999(всегда существует) или [head]99998999. И сумма цифр самого числа, если оно уже вида [head]9999 (сюда же случай одноцифрового числа).
Соответственно второй факт можно проверить, а из первого типа надо выбирать — не то первый чар уменьшать, не то выбирать число с одной 8 и остальными 9. Если число уже вида [head]999989999 то оно и есть решение(как и в случае [head]9999), а вот если недевяток кроме заголовка больше одного — то вычитаем единичку из символа перед этим(головного или 9ки) и дальше всё девятки.
using System;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
var c = Console.ReadLine();
Console.WriteLine(Calc(c));
}
static string Calc(string s)
{
var nonninesIntail = s.Substring(1).Replace("9", "");
var nonheadNonnine = s.IndexOfAny("012345678".ToCharArray(), 1);
return (nonninesIntail == "8" || nonninesIntail == "") ?
s :
(nonheadNonnine > 1) ?
(s.Substring(0, nonheadNonnine - 1) + "8").PadRight(s.Length, '9') :
(int.Parse(s[0] + new string('0', s.Length - 1)) - 1).ToString();
}
}
}
Здравствуйте, dead0k, Вы писали: D>Здравствуйте, olimp_20, Вы писали: D>потенциальные кандидаты: (n, f(1,n), f(2,n),,,, ) D>, где f(i,n) = (n/(10^i)) * (10^i) — 1 D>(вычитаем 1-цу из i+1-ого разряда и заменяем младшие разряды на 9-тки) D>всего кандидатов ~ log(n) D>отсеиваем кандидатов с не максимальной суммой, выбираем наибольшее.
Реализация Вашей идеи (удачно выполнились все тесты):
Решение на С++
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> numb;//вектор чисел
vector<int> sNumb;//вектор соответсвующих суммint f(int n, int base);//вычислить кандидатаint sum_of_digits(int n);//вычислить суммуint main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
scanf("%d", &n);
if(n>9){//если число содержит более одной цифрыint base(10);//основа для деления
//само число - как кандидат
numb.push_back(n);
sNumb.push_back(sum_of_digits(n));
//вычисление остальных кандидатовwhile(n/base>0){
int x = f(n,base);
numb.push_back(x);
sNumb.push_back(sum_of_digits(x));
base *= 10;
}
//поиск числа по критериям задачиint res(numb[0]), maxS(sNumb[0]);
for(unsigned i=1; i<numb.size(); ++i)
if(sNumb[i]>maxS){
maxS = sNumb[i];
res = numb[i];
}
printf("%d", res);
}else printf("%d", n);//вывод, если число одноцифровое
printf("\n");
return 0;
}
int f(int n, int base){
return n/base*base-1;
}
int sum_of_digits(int n){
int sum(0);
while(n>0){
sum += n%10;
n /= 10;
}
return sum;
}
Может быть просто начинать с обратного?
Брать N идти от него к нулю, нашли первое попавшееся число которое сумма чисел которого равна 9 и все.
Или сумма числе может быть двузначной и трехзначной и рекурсивное сложение чисел не следует делать?
#include <stdio.h>
inline int PositionsSum(int n)
{
int sum = 0;
while (n)
{
sum += n % 10;
n /= 10;
}
return sum;
}
inline int FindMaxPositionsSumMaxNumber(const int Num)
{
if (Num < 10)
return Num;
int res = 0;
int res_sum = 0;
int pos = 10;
for (int i = Num; i >= 10; i /= 10)
{
int t = Num / pos * pos - 1;
int t_sum = PositionsSum(t);
if (t_sum > res_sum)
{
res = t;
res_sum = t_sum;
}
pos *= 10;
}
return PositionsSum(Num) >= res_sum ? Num : res;
}
int main(void)
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int num = 0;
scanf("%d", &num);
printf("%d\n", FindMaxPositionsSumMaxNumber(num));
return 0;
}