Совсем чуть-чуть
От: olimp_20  
Дата: 12.02.15 23:27
Оценка:
Условие:
Найти наибольшее натуральное число, которое не превішает 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)//если построенное число имеет большую сумму - вывести построенное число, иначе вывести numb
            for(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 — не проходит. Закончились идеи: что проверять и какие числа могут быть во входном файле...Подскажите, что еще необходимо проверить или где ошибка в алгоритме. Спасибо.
Re: Совсем чуть-чуть
От: cures Россия cures.narod.ru
Дата: 13.02.15 03:19
Оценка: 4 (1)
Здравствуйте, olimp_20, Вы писали:

_>Проблема: задача вроде бы и элементарная, и почти решена, но два теста №24 и №25 — не проходит. Закончились идеи: что проверять и какие числа могут быть во входном файле...Подскажите, что еще необходимо проверить или где ошибка в алгоритме. Спасибо.


Стандартный способ: оформите своё нахождение как функцию, возвращающую искомое число как int, напишите другую функцию, которая делает это честно (перебирает все натуральные числа до N, и находит то, в котором наибольшая сумма цифр), после чего переберите все N до десяти тысяч, вычисляя результат каждой из двух функций, распечатайте те N, для которых результаты разные. Скорее всего такие найдутся даже до тысячи.

Читерский способ: перебираете все числа до N, но не (только) в виде инта, а в виде массива цифр, инкремент обычно будет сводиться к увеличению последней цифры, изредка — к старшим. При каждом инкременте соответственно изменяйте сумму цифр. Всего получите несколько миллиардов тактов, есть шанс уложиться, если сделаете аккуратно.

ЗЫ: большая просьба исходные тексты постить не только в тексте сообщения в блоке code, там съедаются переводы строк при попытке скопировать в файл, но и на хостинге типа ideone.com, там их можно будет сразу и запустить, потестировать.

Upd: для 190 Ваша программа выведет 99, а правильный ответ 189 (сумма цифр тоже равна 18, а само число больше).
Отредактировано 13.02.2015 3:32 cures . Предыдущая версия .
Re: Совсем чуть-чуть
От: dead0k  
Дата: 13.02.15 16:38
Оценка:
Здравствуйте, olimp_20, Вы писали:

потенциальные кандидаты: (n, f(1,n), f(2,n),,,, )
, где f(i,n) = (n/(10^i)) * (10^i) — 1
(вычитаем 1-цу из i+1-ого разряда и заменяем младшие разряды на 9-тки)
всего кандидатов ~ log(n)

отсеиваем кандидатов с не максимальной суммой, выбираем наибольшее.
Re: Совсем чуть-чуть
От: Sophist Россия http://freelearner-ru.blogspot.com
Дата: 13.02.15 16:49
Оценка:
Здравствуйте, 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;
}
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Re: Совсем чуть-чуть
От: Кодт Россия  
Дата: 13.02.15 16:56
Оценка:
Здравствуйте, olimp_20, Вы писали:

<>

Пусть у нас n-разрядное число вида X,YYYYY
Ответами будут два кандидата (надо выяснить, который лучше)
— (X-1),99999 с суммой чисел (X-1)+(n-1)*9
— X,ZZZZZ где ZZZZZ — ответ для YYYYY.

То есть, если бы мы играли в полный перебор, то получили бы такое дерево вариантов
вход: ABCDE (5-разрядное)

-+- a9999       = A+9+9+9+8
 |
 +-+- Ab999     = A+B+9+9+8
   |
   +-+- ABc99   = A+B+C+9+8
     |
     +-+- ABCd9 = A+B+C+D+8
       |
       +- ABCDE = A+B+C+D+E

где a,b,c,d — это цифры, уменьшенные на 1 (если какая-то цифра равна 0, то данного варианта просто нет).

при равенстве весов надо отдавать предпочтение вторым вариантам.

Прогуляемся в обратную сторону
....E = +E
...d9 = +D+8 | ...DE = +D+E  -- если E>=8 (т.е. 8 или 9), выбираем второе
..c99 = +C+17 | ..C?? = +C+?? -- если там сумма >=17 (т.е. 89, 98, 99), выбираем второе
.b999 = +B+26 | .B??? = +B+??? -- если там сумма >=26, выбираем второе
a9999 = +A+35 | A???? = +A+???? -- если там сумма >=35, выбираем второе


То есть, можем вообще бежать от младших разрядов. И даже не считать +26, +35 и т.д. — только степень нехватки до 9999

Сейчас немножко подумаю, напишу короткую программу на сях, безо всяких векторов, чисто на арифметике.
Перекуём баги на фичи!
Re[2]: Совсем чуть-чуть
От: olimp_20  
Дата: 13.02.15 17:23
Оценка:
Здравствуйте, Sophist, Вы писали:

S>А как вам такое?


Да, Ваша програма правильно вычисляет, это видно по тому, какие тесты пройдены — в том числе проблемный для меня №25. Однако, не всё так гладко: тесты №21-№24 — "Исчерпан лимит времени". Как я понял: использованная рекурсия существенно "сожрала" время...
Re[2]: Совсем чуть-чуть
От: olimp_20  
Дата: 13.02.15 18:43
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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?
Re[3]: Совсем чуть-чуть
От: Sophist Россия http://freelearner-ru.blogspot.com
Дата: 14.02.15 06:58
Оценка:
Здравствуйте, olimp_20, Вы писали:

_>Да, Ваша программа правильно вычисляет, это видно по тому, какие тесты пройдены — в том числе проблемный для меня №25. Однако, не всё так гладко: тесты №21-№24 — "Исчерпан лимит времени". Как я понял: использованная рекурсия существенно "сожрала" время...


Хм, довольно странно, учитывая, что глубина рекурсии не превосходит 10, а ветка рекурсии всего одна.

Сэкономить время, в принципе, можно, если вычислять сумму цифр у второго кандидата не через функцию, а просто как (head — 1) + 9 * (base — 1). А если еще возвращать одновременно и число, и сумму его цифр, то не придется многократно считать сумму цифр в хвосте.
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Re[3]: Совсем чуть-чуть
От: Sophist Россия http://freelearner-ru.blogspot.com
Дата: 14.02.15 22:32
Оценка:
Здравствуйте, 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;
}
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Re[3]: Совсем чуть-чуть
От: Кодт Россия  
Дата: 15.02.15 13:10
Оценка:
Здравствуйте, olimp_20, Вы писали:

К>>вход: ABCDE (5-разрядное)

К>>-+- a9999 = A+9+9+9+8
_>Если возможно, уточните, пожалуйста, откуда берется 8?

a+9+9+9+9 = A-1+9+9+9+9
Перекуём баги на фичи!
Re: Совсем чуть-чуть
От: Кодт Россия  
Дата: 16.02.15 16:26
Оценка:
Здравствуйте, olimp_20, Вы писали:

Решение на питоне, в несколько приёмов
  Скрытый текст
# серия пар (цифра, порядок)
def digits(n):
    ''' emit pairs (d,t) where d is a digit, t is 10**k '''
    t = 1
    while n>0:
        yield n%10, t
        n//=10
        t*=10

# тупая реализация суммы цифр
def sumdigits(n):
    return sum(d for d,t in digits(n))    

# первая попытка
def maxnum(n):
    qqq = 0 # все девятки
    xyz = 0 # какие-то цифры
    for D,t in digits(n):
        d = D-1
        Dxyz = D*t + xyz # создаём два кандидата
        dqqq = d*t + qqq
        xyz = Dxyz if sumdigits(Dxyz) >= sumdigits(dqqq) else dqqq # выбираем лучшего из них
        qqq = 9*t + qqq
    return xyz

# делаем инкрементный подсчёт цифр
def maxnum(n):
    qqq, Sqqq = 0, 0 # S... - сумма цифр этого числа ...
    xyz, Sxyz = 0, 0
    for D,t in digits(n):
        d = D-1
        Dxyz,SDxyz = D*t + xyz, D + Sxyz
        dqqq,Sdqqq = d*t + qqq, d + Sqqq
        xyz,Sxyz = (Dxyz,SDxyz) if SDxyz >= Sdqqq else (dqqq,Sdqqq)
        qqq,Sqqq = 9*t + qqq, 9+Sqqq
    return xyz

# переходим к разности сумм цифр
def maxnum(n):
    qqq, Sqqq = 0, 0
    xyz, Sxyz = 0, 0
    for D,t in digits(n):
        d = D-1
        Dxyz,SDxyz = D*t + xyz, D + Sxyz
        dqqq,Sdqqq = d*t + qqq, d + Sqqq
        xyz,Sxyz = (Dxyz,SDxyz) if SDxyz >= Sdqqq else (dqqq,Sdqqq)
        qqq,Sqqq = 9*t + qqq, 9+Sqqq
        Sxyz,Sqqq = Sxyz-Sxyz,Sqqq-Sxyz # вычитаем из обеих сумм величину Sxyz (обнуляя Sxyz)
    return xyz

# помня о том, что Sxyz равно 0, избавляемся от него
def maxnum(n):
    qqq = 0
    xyz = 0
    Sqqq = 0
    for D,t in digits(n):
        d = D-1
        Dxyz = D*t + xyz
        dqqq = d*t + qqq
        xyz = Dxyz if D >= d+Sqqq else dqqq
        Sqqq = (9+Sqqq-D) if D >= d+Sqqq else (9-d)
        qqq = 9*t + qqq
    return xyz


# упрощаем - выпиливаем всё лишнее
def maxnum(n):
    xyz = 0
    S = 0 # разность суммы между xyz и всеми девятками
    for D,t in digits(n):
        # кандидаты
        Dxyz = D*t + xyz
        dqqq = D*t - 1
        prefer_xyz = 1 >= S
        xyz = Dxyz if prefer_xyz else dqqq
        S = (9+S-D) if prefer_xyz else (10-D)
    return xyz

Вроде, нигде не ошибся.

Хорошо бы его проверить, а то непонятно, где кейсы взять.
Перекуём баги на фичи!
Re: Совсем чуть-чуть
От: Nuseraro Россия  
Дата: 17.02.15 06:17
Оценка:
У меня решение в одну строчку, O(ln N)

Принцип такой: для числа есть две возможных выигрышных суммы (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();
        }
    }
}
Homo Guglens
Re[2]: Совсем чуть-чуть
От: olimp_20  
Дата: 23.02.15 17:12
Оценка:
Здравствуйте, 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;
}
Re[2]: Совсем чуть-чуть
От: olimp_20  
Дата: 23.02.15 17:33
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Хорошо бы его проверить, а то непонятно, где кейсы взять.


На сайте в разделе "Отправить решение" есть возможность проверить код на Питоне.

Я все-же попробовал реализовать с векторами — все получилось
Автор: olimp_20
Дата: 23.02.15


Спасибо за помощь, особенно за пояснение алгоритмической стороны задачи.
Re: Совсем чуть-чуть
От: -n1l-  
Дата: 23.02.15 17:38
Оценка:
Может быть просто начинать с обратного?
Брать N идти от него к нулю, нашли первое попавшееся число которое сумма чисел которого равна 9 и все.
Или сумма числе может быть двузначной и трехзначной и рекурсивное сложение чисел не следует делать?
Re[2]: Совсем чуть-чуть
От: Warlock78  
Дата: 13.03.15 07:27
Оценка:
#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;
}
Отредактировано 13.03.2015 12:24 Warlock78 . Предыдущая версия . Еще …
Отредактировано 13.03.2015 8:05 Warlock78 . Предыдущая версия .
Re: Совсем чуть-чуть
От: Warlock78  
Дата: 13.03.15 07:30
Оценка:
Отредактировано 13.03.2015 7:31 Warlock78 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.