Не знаю как отладить

@CyberNinjaProg · Регистрация: 10.03.2019

Author24 — интернет-сервис помощи студентам

Здравствуйте. Мне помогли решить задачу на informatics. Но она прошла не все тесты. Какие не знаю. Не получилось ничего.
Пожалуйста помогите

У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково порядочные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.

Миша очень любит рассматривать сумму цифр числа. Для того чтобы привести в порядок число A, он сначала записывает само число. Потом он пишет сумму цифр этого числа. Затем — сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. Он считает, что результатом приведения в порядок числа A является сумма всех выписанных чисел, включая само число A.

Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.

Входные данные
На ввод подаётся единственное целое число B (1 ≤ B ≤ 109 )

Выходные данные
Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.

Примеры тестов
входные данные
42
выходные данные
29
входные данные
20
выходные данные
-1
Примечание
Пояснение к первому примеру. Последовательность сумм цифр для 29 состоит из чисел 29, 11, 2. Соответственно, после приведения в порядок число 29 превращается в число 42 = 29 + 11 + 2.
Вот решение:

C++

#include <iostream>
using namespace std;
long long a = 0, b, c, e, d;
int main()
{
    cin >> b;
    do {
        a++;
        c = a;
        e = a;
        do {
            d = 0;
            while (e > 0) {
                d += e % 10;
                e /= 10;
            }
            e = d;
            c += d;
        } while (e >= 10);
    } while (c != b && a != b);
    if (c != b) {
        cout << -1;
        return 0;
    }
    else {
        cout << a;
    }
 
}

ИЛИ ВОТ

C++

#include <iostream>
void getSumOfNumerals(int i, int& globalSum)
{
    int sum = 0;
    while((double)i / 10)
    {
        sum += i % 10;
        i /= 10;
    }
 
    globalSum += sum;
    if (sum / 10)
        getSumOfNumerals(sum, globalSum);
}
 
void checker(int b)
{
    for(int i = 1; i < b; i++)
    {
        int globalSum = i;
        getSumOfNumerals(i, globalSum);
        if (globalSum == b)
        {
            std::cout  << i << std::endl;
            return ;
        }
    }
    std::cout << -1 << std::endl;
}
 
int main()
{
    int b;
    std::cin >> b;
    checker(b);
    system("pause");
}

У всех 2-их решениях одно и тоже(ФОТО)

@Krokodil9798 · 17.03.2019, 03:19

Сообщение от valen10

Прошу прощения, с функциями ошибся при проверке. Однозначные числа попробуйте на вход подать.

Взаимно прошу прощения, забыл учесть тот факт, что нужно вызывать функцию разложения на число только если текущее число не состоит с одной цифры.
Это прибавило +1 пройденный тест.
Спасибо, что помогли найти неточность

C++

#include <iostream>
void getSumOfNumerals(long i, long& globalSum)
{
    long sum = 0;
    while (i)
    {
        sum += i % 10;
        i *= 0.1;
    }
 
    globalSum += sum;
    if ((int)(sum * 0.1))
        getSumOfNumerals(sum, globalSum);
}
 
void checker(long b)
{
    const long mid = b * 0.5;
    for (long i = b; i > mid; --i)
    {
        long globalSum = i;
        if (i > 9)
            getSumOfNumerals(i, globalSum);
        if (globalSum == b)
        {
            std::cout << i;
            return;
        }
    }
    std::cout << -1;
}
 
int main()
{
    long b;
    std::cin >> b;
    checker(b);
}

@valen10 · 17.03.2019, 04:12

Сообщение от Krokodil9798

Это прибавило +1 пройденный тест

Еще не все тесты что-ли? Если не проходит по времени, то рассмотрите границы поиска. В худшем случае сумма цифр числа A получится 79 (определено опытным путём), следующая сумма 16, а затем 7, итого B = A + 79 + 16 + 7 = A + 102. То есть границы поиска числа A можно сузить до [B - 102; B].

@Krokodil9798 · 17.03.2019, 11:00

Сообщение от valen10

рассмотрите границы поиска

В задании темы неправильно написана правая граница. Она должна быть 10 в степени 9, а не 109 (узнал на сайте). Тогда в худшем случае может быть гораздо большая сумма.
Да и зачем мне пытаться ломать голову над решением - пусть это делает автор темы. Решение есть, не проходит лишь один тест по времени. Поиграться с границами не столь трудно

@valen10 · 17.03.2019, 11:33

Сообщение от Krokodil9798

В задании темы неправильно написана правая граница. Она должна быть 10 в степени 9, а не 109 (узнал на сайте). Тогда в худшем случае может быть гораздо большая сумма.

Это уже с учетом степени, относительно числа B. Если будут все цифры 9, сумма будет 81 + 9. Но это не худший случай. 102 получится из 999999997, 999999988 и подобных.

Сообщение от Krokodil9798

Да и зачем мне пытаться ломать голову над решением - пусть это делает автор темы.

Ради интереса, например. Каждый сам придумывает для себя причины. Впрочем, вы правы, это уже не наша проблема. ТС вообще никакого не принимает участия, похоже ему пофиг, лишь бы готовое решение выложили

@CyberNinjaProg · 17.03.2019, 15:03 **[ТС]**

Нет это не так. Я немного был занят и сегодня я читал все ваши рассуждения и сделал выводы. Огромное вам спасибо!

Добавлено через 26 минут
время 1.003 sec

@outoftime · 17.03.2019, 21:07

CyberNinjaProg, Krokodil9798, Байт, valen10, а мне в кайф было решить. Код самодокумментирующий с пояснениями алгоритма.

C++

// #include <bits/stdc++.h>
#include <cstdio>
 
// узнаём сумму цыфер числа "a"
int next(int a) {
    if (a == 0) return 0;
    return a % 10 + next(a / 10);
}
 
// функция b(a)
int sum(int a) {
    if (a < 10) return a;
    return a + sum(next(a));
}
 
int main()
{
    // std::cout << "int p[]{0,";
    // for (int a = 1; a <= 9*9; ++a)
    //     std::cout << sum(a) << ", ";
    // p[a]=b, a=0..81, { next(999 999 999)=81 }
    int p[]{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  11, // 1-10
                13, 15, 17, 19, 21, 23, 25, 27, 30, 22, // 11-20
                24, 26, 28, 30, 32, 34, 36, 39, 42, 33, // 21-30
                35, 37, 39, 41, 43, 45, 48, 51, 54, 44, // 31-40
                46, 48, 50, 52, 54, 57, 60, 63, 66, 55, // 41-50
                57, 59, 61, 63, 66, 69, 72, 75, 78, 66, // 51-60
                68, 70, 72, 75, 78, 81, 84, 87, 90, 77, // 61-70
                79, 81, 84, 87, 90, 93, 96, 99, 102,88, // 71-80
                90};
    int b;
    std::scanf("%d", &b);
    // b=16574: a=-1
    // b=16575: a=16547 => b-a=28, p[23]=28, sum(a)=23 { a=b-28, a=b-p[23] }
    //          есть ли i=1..81, такой что next(b-p[i])=i
    for (int i = 1; i <= 81; ++i) {
        if (next(b-p[i]) == i) {
            std::printf("%d\n", b-p[i]);
            return 0;
        }
    }
    std::printf("-1\n");
}

@CyberNinjaProg · 17.03.2019, 23:10 **[ТС]**

извините. к сожалению нельзя использовать массивы. так в предисловии сказано....

@CyberNinjaProg · 17.03.2019, 23:13 **[ТС]**

К сожалению....

@outoftime · 17.03.2019, 23:13

Сообщение от CyberNinjaProg

извините. к сожалению нельзя использовать массивы. так в предисловии сказано....

Читайте условие задачи внимательно.

@CyberNinjaProg · 17.03.2019, 23:15 **[ТС]**

Вот

@outoftime · 17.03.2019, 23:53

CyberNinjaProg, 100

C++

#include <bits/stdc++.h>
 
// узнаём сумму цыфер числа "a"
int next(int a) {
    if (a == 0) return 0;
    return a % 10 + next(a / 10);
}
 
int main()
{
    // p[a]=b, a=0..81, { next(999 999 999)=81 }
    int p[]{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  11, // 1-10
                13, 15, 17, 19, 21, 23, 25, 27, 30, 22, // 11-20
                24, 26, 28, 30, 32, 34, 36, 39, 42, 33, // 21-30
                35, 37, 39, 41, 43, 45, 48, 51, 54, 44, // 31-40
                46, 48, 50, 52, 54, 57, 60, 63, 66, 55, // 41-50
                57, 59, 61, 63, 66, 69, 72, 75, 78, 66, // 51-60
                68, 70, 72, 75, 78, 81, 84, 87, 90, 77, // 61-70
                79, 81, 84, 87, 90, 93, 96, 99, 102,88, // 71-80
                90};
    int b;
    std::scanf("%d", &b);
    if (b < 82) {
        auto res = std::find(std::begin(p), std::end(p), b);
        std::printf("%d\n", res == std::end(p) ? -1 : res - p);
        return 0;
    }
    // b=16574: a=-1
    // b=16575: a=16547 => b-a=28, p[23]=28, sum(a)=23 { a=b-28, a=b-p[23] }
    //          есть ли i=1..81, такой что next(b-p[i])=i
    for (int i = 1; i <= 81; ++i) {
        if (next(b-p[i]) == i) {
            std::printf("%d\n", b-p[i]);
            return 0;
        }
    }
    std::printf("-1\n");
}

Добавлено через 3 минуты

Сообщение от CyberNinjaProg

Вот

Это откуда?

@CyberNinjaProg · 18.03.2019, 00:11 **[ТС]**

Вот

@outoftime · 18.03.2019, 01:45

CyberNinjaProg, Как включить в своей среде разработки поддержку определённого стандарта (С++11, С++14, С++17, C++20, C++23)

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	17.03.2019, 04:12	22
	Сообщение от Krokodil9798 Это прибавило +1 пройденный тест Еще не все тесты что-ли? Если не проходит по времени, то рассмотрите границы поиска. В худшем случае сумма цифр числа A получится 79 (определено опытным путём), следующая сумма 16, а затем 7, итого `B = A + 79 + 16 + 7 = A + 102`. То есть границы поиска числа A можно сузить до `[B - 102; B]`. 0

@Krokodil9798 330 / 145 / 56 Регистрация: 17.10.2015 Сообщений: 580
	17.03.2019, 11:00	23
	Сообщение от valen10 рассмотрите границы поиска В задании темы неправильно написана правая граница. Она должна быть 10 в степени 9, а не 109 (узнал на сайте). Тогда в худшем случае может быть гораздо большая сумма. Да и зачем мне пытаться ломать голову над решением - пусть это делает автор темы. Решение есть, не проходит лишь один тест по времени. Поиграться с границами не столь трудно 1

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	17.03.2019, 11:33	24
	Сообщение от Krokodil9798 В задании темы неправильно написана правая граница. Она должна быть 10 в степени 9, а не 109 (узнал на сайте). Тогда в худшем случае может быть гораздо большая сумма. Это уже с учетом степени, относительно числа B. Если будут все цифры 9, сумма будет `81 + 9`. Но это не худший случай. 102 получится из 999999997, 999999988 и подобных. Сообщение от Krokodil9798 Да и зачем мне пытаться ломать голову над решением - пусть это делает автор темы. Ради интереса, например. Каждый сам придумывает для себя причины. Впрочем, вы правы, это уже не наша проблема. ТС вообще никакого не принимает участия, похоже ему пофиг, лишь бы готовое решение выложили 1

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	17.03.2019, 15:03 [ТС]	25
	Нет это не так. Я немного был занят и сегодня я читал все ваши рассуждения и сделал выводы. Огромное вам спасибо! Добавлено через 26 минут время 1.003 sec 0

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	17.03.2019, 23:10 [ТС]	27
	извините. к сожалению нельзя использовать массивы. так в предисловии сказано.... 0

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	17.03.2019, 23:13 [ТС]	28
	К сожалению.... Миниатюры 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	17.03.2019, 23:13	29
	Сообщение от CyberNinjaProg извините. к сожалению нельзя использовать массивы. так в предисловии сказано.... Читайте условие задачи внимательно. 0

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	17.03.2019, 23:15 [ТС]	30
	Вот Миниатюры 0

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	18.03.2019, 00:11 [ТС]	32
	Вот Миниатюры 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	18.03.2019, 01:45	33
	CyberNinjaProg, Как включить в своей среде разработки поддержку определённого стандарта (С++11, С++14, С++17, C++20, C++23) 0